描述：
分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。
输入：
输入在第一行给出两个正整数 N 和 M（均不超过10 000），分别为敌方城市个数（于是默认城市从 1 到 N 编号）和连接两城市的通路条数。随后 M 行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数 K （≤ 100）和随后的 K 行方案，每行按以下格式给出：
Np v[1] v[2] ... v[Np]
1
其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。
输出:
对每一套方案，如果可行就输出YES，否则输出NO。
思路：
把图存储下来，对于每次询问把攻下的城市记录下来，然后根据记录去图中做判断即可
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e5+100; const int p = 1e4+10; const double eps = 1e-8; vector<int>ve[10001];//建图 int n,m; int a,b; int k,cnt,ms; bool vis[p]; int judge() { for(int i=1;i<=n;i++) { if(!vis[i]) { int len=ve[i].size(); for(int j=0;j<len;j++) { if(vis[ve[i][j]]!=1) return 0; } } }//所有的非标记点中，出现相邻点非标记点，即非孤立 return 1; } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { cin>>a>>b; ve[a].push_back(b); ve[b].push_back(a); }//建图 cin>>k; while(k--) { memset(vis,0,sizeof(vis));//每一次把标记数组清空 cin>>cnt; for(int i=1;i<=cnt;i++) { cin>>ms; vis[ms]=1; }//输入所有标记点 if(judge()==1) printf("YES\n"); else printf("NO\n"); } }
