PAT_甲级_1134 Vertex Cover (25point(s)) (C++)【散列】

目录

1，题目描述

题目大意

2，思路

3，AC代码

4，解题过程

第二搏

1，题目描述

• vertex cover：顶点覆盖; 点集覆盖问题；
• incident：发生的事情(尤指不寻常的或讨厌的); 严重事件，暴力事件(如犯罪、事故、袭击等); (两国间的) 摩擦，冲突; (常指) 军事冲突； 

Sample Input:

10 11
8 7
6 8
4 5
8 4
8 1
1 2
1 4
9 8
9 1
1 0
2 4
5
4 0 3 8 4
6 6 1 7 5 4 9
3 1 8 4
2 2 8
7 9 8 7 6 5 4 2

Sample Output:

No
Yes
Yes
No
No

题目大意

 判断给定的序列是否为vertex cover（一个特殊的顶点集，要求图中每条边中至少有一个顶点在此集合中），输出Yes或输出No。

2，思路

声明一个unordered_map<int, unordered_set<int>> data存放每个顶点连接的边，查询时，将所有顶点在data中对应的值存入set中，若set.size()==M就输出Yes，否则输出No。

3，AC代码

#include<bits/stdc++.h>
using namespace std;unordered_map<int, unordered_set<int>> data;
int main(){
#ifdef ONLINE_JUDGE
#elsefreopen("1.txt", "r", stdin);
#endif // ONLINE_JUDGEint N, M, K, v1, v2, num;//N顶点数 M边数 K查询数scanf("%d%d", &N, &M);for(int i = 0; i < M; i++){scanf("%d%d", &v1, &v2);data[v1].insert(i);data[v2].insert(i);}scanf("%d", &K);unordered_set<int> temp;for(int i = 0; i < K; i++){scanf("%d", &num);temp.clear();// !!!for(int j = 0; j < num; j++){scanf("%d", &v1);for(auto it : data[v1])temp.insert(it);}if(temp.size() == M)printf("Yes\n");elseprintf("No\n");}return 0;
}

4，解题过程

本想着先来一套最朴实的做法

然后准备想着怎么优化了。。。

然而

 题目限制600ms

苟过了一题。。。

第二搏

欣赏了一位大佬的做法，时间快了一倍，占用内存还比较少。

精彩

@日沉云起【pat甲级1134. Vertex Cover (25)】

#include<bits/stdc++.h>
using namespace std;
int N,M,K;
bool vertex[10005];//散列数组
int main(){scanf("%d%d",&N,&M);pair<int,int>edge[M];//边的数组for(int i=0;i<M;++i)//读取边scanf("%d%d",&edge[i].first,&edge[i].second);scanf("%d",&K);while(K--){int A,a;scanf("%d",&A);memset(vertex,0,sizeof(vertex));//将vertex元素均置falsewhile(A--){//读取点集scanf("%d",&a);vertex[a]=true;//将vertex数组中对应元素置true}bool f=true;//标志输出应该为true还是falsefor(int i=0;i<M&&f;++i)//遍历边的数组if(!vertex[edge[i].first]&&!vertex[edge[i].second])//有边两个端点在vertex中均为falsef=false;//置f为falseprintf("%s\n",f?"Yes":"No");//输出}return 0;
}