L2-025 分而治之

L2-025 分而治之

链接：题目详情 - L2-025 分而治之 (pintia.cn)

思路：这题最开始没仔细想，直接使用了并查集，并根据输入的被攻打的城市是否是根结点城市判断进攻是否可行，但是这个方法不行，因为在并查集时，会把每个城市间的链连结关系简化，而题中要求的是把城市间的连结关系全部断掉才算可行的进攻方案，所以不能用并查集。

1.根据题意，较为简单的方法是储存连结信息，然后看连结关系是否会被全部消除，如果会则进攻可行，否则不可行。

2.由于数据范围较大，所以用vector，由于连结关系是二元关系，所以用pair捆绑起来，用 typedef pair<int,int> lian; 定义一个类型lian， vector容器定义为lian类型的。

3.输入时储存连结关系，同时要标记城市出现true。进攻城市的时候，让城市的出现情况标记为没出现false，然后遍历vector，只有第一第二两个元素都还存在的时候，此连结情况还存在，那么即可判定进攻不可行。

4.每一轮进攻都会改变出现情况的标记，所以要有两个bool数组，在每次进攻前进行初始化，这样就可防止数据只能一次性使用。

#include<iostream>
#include<map>
#include<vector>
using namespace std;
const int N=10010;
typedef pair<int,int> lian;
vector<lian> vi;
bool shan1[N]={false},shan[N]={false};
int main(){
    int i,j,n,m;
    cin>>n>>m;
    int x,y,num=0;
    for(i=0;i<m;i++){
        cin>>x>>y;
        vi.push_back(lian(x,y));
        shan1[x]=true;
        shan1[y]=true;
    }
    int K,k,q,z,Y;
    cin>>K;
    for(i=0;i<K;i++){
        Y=0;
        for(j=1;j<=n;j++){
            shan[j]=shan1[j];
        }
        cin>>k;
        for(j=0;j<k;j++){
            cin>>z;
            shan[z]=false;
        }
        for(j=0;j<m;j++){
            if(shan[vi[j].first]&&shan[vi[j].second]){
                Y=1;
                break;
            }
        }
        if(Y==1)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
}