题目大意:给出一张图,判断给出的顶点序列是否满足“vertex cover"。所谓"vertex cover",是指图中任意一条边,至少有一个端点被包含在这个顶点序列里。
根据题意,只要图中有一条边,它的两个顶点都不在给出的序列里,那么这个序列就不满足"vertec cover"。反过来,如果不在序列里的两个顶点之间有一条边,那么这个序列就不是vertex cover。所以可以在输入序列之后查找不在序列里的顶点,判断两两之间是否存在边。但是这样会超时,因为顶点数10^5,双重循环遍历的时间复杂大太高。所以对于一个不在序列里的顶点,只需要遍历它在邻接表中记录的邻接顶点,看它们是否在序列里即可。这样很大程度地降低了时间复杂度。用hashTable来记录顶点是否在序列里。
AC代码:
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 10010;
vector<int> G[MAXN];
bool inq[MAXN] = {0};
int main()
{
int N, M;
scanf("%d%d", &N, &M);
for (int i = 0; i < M; ++i)
{
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
int K;
scanf("%d", &K);
for (int i = 0; i < K; ++i)
{
fill(inq, inq + MAXN, 0);
int cnt;
scanf("%d", &cnt);
vector<int> notInQ;
for (int j = 0; j < cnt; ++j)
{
int num;
scanf("%d", &num);
inq[num] = true;
}
bool flag = true;
for (int k = 0; flag && k < N; ++k)
{
if(!inq[k])
{
for (int j = 0; j < G[k].size(); ++j)
{
if(!inq[G[k][j]])
{
printf("No\n");
flag = false;
break;
}
}
}
}
if(flag) printf("Yes\n");
}
return 0;
}