L2-025 分而治之 (25分)

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：
Np v[1] v[2] … v[Np]
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

输出格式：
对每一套方案，如果可行就输出YES，否则输出NO。

输入样例：

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 10
2 4
5
4 10 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

输出样例：

NO
YES
YES
NO
NO

题目解析： 首先建立二维数组存储每个节点所关联的边。对于每一种输入的方案，设置方案里面的节点不可访问（这里设置vis数组的节点值为1），遍历二维数组，判断当前未被攻占的城市，是否仍和其他城市有关联，如果有，那么这个方案不可行，否则可行。

并查集思想： 首先建立连通关系，对于每次输入的方案，也是采用以设置 vis 数组为不可访问，最终对于原来输入的边建立的连通性，可访问的节点上在重新建立连通关系，最后比较连通集合的个数与城市个数是否相等即可。
相关思路可以借鉴：L2-013 红色警报 (25分) 题目解析 并查集做法
但是本题不太适用，因为每次都需要以结构体的方式设置两端的城市的编号，以供重新建立。然后比对，那么在此处，建立并查集就比较多余，因为直接可以遍历二维数组，就无需再次重新建立连通关系。

代码如下：

#include<bits/stdc++.h>
#define Inf 0x3f3f3f
const int N = 10005;
using namespace std;

int n, m, k;
int sum;
vector<int> ve[N];
int vis[N], flag;

void solve(){
	for(int i = 1; i <= n; i ++)
		for(int j = 0; j < ve[i].size(); j ++)
			if(vis[i]==0 && vis[ve[i][j]]==0){//当前未被攻占的城市，仍和其他城市有关联
				flag = 1; return;
			}
}

int main(){
	int x, y;
	cin >> n >> m;
	while(m--){
		cin >> x >> y;
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	
	int np, ans;
	cin >> k;
	while(k--){
		cin >> np;
		memset(vis, 0, sizeof(vis));
		while(np--){
			cin >> ans;
			vis[ans]=1;//设置该节点不能访问
		}
		flag = 0;
		solve();
		if(flag == 1){
			cout << "NO" << endl;
		}else{
			cout << "YES" << endl;
		}
	}
	return 0;
}