题目链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805346428633088
题目大意:给出一个无向图,再给出k组点的集合,问每一组点的集合能不能把每条边都包含(只要某条边的一个顶点在集合当中就算包含)。
分析:对于每一组集合,遍历每一条边,只要某一条边的两个顶点都不在集合里面,那么这条边就一定是不被包含的。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, k, cnt, a[N];
bool vis[N];
struct Edge {int a, b;
}edge[2 * N];
void add(int x, int y) {edge[cnt].a = x;edge[cnt].b = y;cnt++;
}
bool check() {int x, y;for(int i = 0; i < cnt; i++) {x = edge[i].a;y = edge[i].b;if(!vis[x] && !vis[y]) return false;}return true;
}
int main() {cnt = 0;scanf("%d %d", &n, &m);int x, y;for(int i = 0; i < m; i++) {scanf("%d %d", &x, &y);add(x, y);add(y, x);}scanf("%d", &k);int num;while(k--) {memset(vis, 0, sizeof vis);scanf("%d", &num);for(int i = 1; i <= num; i++) {scanf("%d", &a[i]);vis[a[i]] = 1;}if(check()) printf("Yes\n");else printf("No\n");}return 0;
}