PAT A1134 Vertex Cover ——悲欢离合总无情，一任阶前、点滴到天明

PAT A1134 Vertex Cover ——悲欢离合总无情，一任阶前、点滴到天明

PAT A1134 Vertex Cover

• 判断所给集合中的点有没有cover到所有的边。在存储图的二维数组中，每个一维数组可以看作与某个顶点相关的所有边，所以当一个顶点出现时，就表示能cover到她的一维数组中的所有边
• so二维数组存储输入的图(边)，再搞一个顶点的hash数组，之后开始判断，对于每个输入的集合，在hash数组中标记其中的点——每标记一个点就相当于划掉了二维数组中此顶点对应的一维数组，标记完看一下那些没被标记的顶点，遍历其一维数组，看与之相邻的顶点是否被标记了，如果没有，就发现了一条没cover到的边，输出No；如果全部遍历过后都没有No，那就Yes
• 注意判断每个集合前重置hash数组

#include<iostream>
#include<vector>using namespace std;vector<bool> shot;
vector<vector<int> > vv;int main(){int N,M;scanf("%d %d",&N,&M);vv.resize(N);size(N,false);for(int i = 0;i < M;i ++){int a,b;scanf("%d %d",&a,&b);vv[a].push_back(b);vv[b].push_back(a);}int K;scanf("%d",&K);for(int i = 0;i < K;i ++){int num;scanf("%d",&num);for(int j = 0;j < shot.size();j ++) shot[j] = false;for(int j = 0;j < num;j ++){int tmp;scanf("%d",&tmp);shot[tmp] = true;}bool flag = false;for(int j = 0;j < vv.size();j ++){if(shot[j]) continue;for(int k = 0;k < vv[j].size();k ++){if(!shot[vv[j][k]]){printf("Non");flag = true;break;}}if(flag) break;}if(!flag) printf("Yesn");}return 0;
}