思路：开一个bool数组st，st[i]=true表示第i号城市被摧毁。对于每一个询问，遍历所有没有被摧毁的城市，判断该城市的所有相邻城市是否被摧毁，若有一个没有被摧毁则输出NO，否者输出YES
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n, m, T; // n：城市个数、m：边数、T：T组询问
vector<int> v[N]; // 邻接表
bool st[N]; // st[i]：true表示第i号城市被摧毁
int main(){
// 处理输入
cin >> n >> m;
for(int i = 0; i < m; i ++ ) {
int a, b; cin >> a >> b;
v[a].push_back(b); v[b].push_back(a); // 题意为无向图，要建双向的边
}
cin >> T;
while(T -- ) {
memset(st, 0, sizeof st); // 清空st
int k; cin >> k;
while(k -- ) {
int t; cin >> t;
st[t] = true;
}
bool flag = true; // flag = false 表示某个城市至少有一个相邻城市没有被摧毁
for(int i = 1; i <= n; i ++ ) {
if(st[i]) continue;
if(flag == false) break;
for(int j = 0; j < v[i].size(); j ++ ) {
int t = v[i][j];
if(st[t] == false) {
flag = false;
break;
}
}
}
cout << (flag ? "YES" : "NO") << endl;
}
return 0;
}
文章为作者独立观点，不代表股票配资公司观点
股民评论