1134. Vertex Cover (25)
A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Now given a graph with several vertex sets, you are supposed to tell if each of them is a vertex cover or not.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 104), being the total numbers of vertices and the edges, respectively. Then M lines follow, each describes an edge by giving the indices (from 0 to N-1) of the two ends of the edge.
After the graph, a positive integer K (<= 100) is given, which is the number of queries. Then K lines of queries follow, each in the format:
Nv v[1] v[2] ... v[Nv]
where Nv is the number of vertices in the set, and v[i]'s are the indices of the vertices.
Output Specification:
For each query, print in a line "Yes" if the set is a vertex cover, or "No" if not.
Sample Input:10 118 76 84 58 48 11 21 49 89 11 02 454 0 3 8 46 6 1 7 5 4 93 1 8 42 2 87 9 8 7 6 5 4 2Sample Output:
NoYesYesNoNo
这道题的关键是容易超时，自己写的代码仔细想想确实会超时，再参考了别人的代码，感觉妙哉。将每条边编号，记录每个顶点相关的边，将询问的顶点相关的边都标记了，再遍历所有的边，发现没有标记的说明没有全覆盖。
也可以使用set容器，将所有询问顶点放入set中，遍历所有的边，判断set中是否有边的两个任意一个顶点，若没有则没有全覆盖。
#includeusing namespace std;int N, M, K;struct Node { int x; int y;};vector nodVec, nodVec1;void deleteNode(int x, vector nodV) {}int main(){ cin>> N>> M; int x, y; for(int i = 0; i < M; i++) { //10^4 scanf("%d%d", &x, &y); Node node; node.x = x; node.y = y; nodVec.push_back(node); } cin>> K; nodVec1 = nodVec; for(int i = 0; i < K; i++) { //10^2 scanf("%d", &x); for(int j = 0; j < x; j++) { //10^4 scanf("%d", &y); vector ::iterator it = nodVec1.begin(); while(it != nodVec1.end()) { //10^4每次都会遍历所有的边，虽然有erase，但是总量还是很大。 if(y == it->x || y == it->y) { it = nodVec1.erase(it); } else { it++; } } } if(nodVec1.empty()) { printf("Yes\n"); } else { printf("No\n"); } nodVec1 = nodVec; } return 0;}
#includeusing namespace std;#define MAX 10004int N, M, K;vector nodes[MAX];int flag[MAX];int main() { cin>> N>> M; int x, y; for(int i = 0; i < M; i++) { //10^4 scanf("%d%d", &x, &y); nodes[x].push_back(i); nodes[y].push_back(i); } cin>> K; for(int i = 0; i < K; i++) { //10^2 for(int j = 0; j < M; j++) { //10^4 flag[j] = 0; } scanf("%d", &x); for(int j = 0; j < x; j++) { //10^4*2;这里每次遍历一个顶点的所有边，总共最多遍历两次所有的边 scanf("%d", &y); vector ::iterator it; for(it = nodes[y].begin(); it != nodes[y].end(); it++) { flag[*it] = 1; } } int flag2 = 1; for(int j = 0; j < M; j++) { if(flag[j] == 0) { flag2 = 0; printf("No\n"); break; } } if(flag2 == 1) { printf("Yes\n"); } } return 0;}
#includeusing namespace std;int N, M, K;#define MAX 10004struct Node { int x, y;}nodes[MAX];set nodeSet;int main() { cin>>N>>M; for(int i = 0; i < M; i++) { //10^4 scanf("%d%d", &nodes[i].x, &nodes[i].y); } cin>>K; int x, y; for(int i = 0; i < K; i++) { //10^2 cin>> x; nodeSet.clear(); for(int j = 0; j < x; j++) { //10^4 scanf("%d", &y); nodeSet.insert(y); } int flag = 1; for(int i = 0; i < M; i++) { //10^4*log10^4 if(nodeSet.find(nodes[i].x) == nodeSet.end() && nodeSet.count(nodes[i].y) == 0) { flag = 0; break; } } if(!flag) { printf("No\n"); } else { printf("Yes\n"); } } return 0;}