title: PAT1134
date: 2021-01-22 20:03:07
tags: PAT
1134
题目:
检查子图是否能够满足顶点覆盖
定点覆盖
即图的所有的边两端的结点,是否至少一个结点出自顶点集合中
范围:
- 顶点 <= 10^4
- 边 <= 10^4
- 子集数 <= 100
- 子集元素数
未说明
可能是 <= 10^4
分析:
- 好像没啥坑,一遍过,做的时候想得复杂了点把整个图都存起来了,实际上没有什么必要
解法:
将边全部存起来,子集中查找边,最多 10000 * 10000 次,但是可以哈希存储节点,使查找存储的节点复杂度为常数级
代码:
#include<iostream>
#include<set>
using namespace std;
#define INF 0x7fffffff
set<int> edge[10005];
int main(){
int n, m;
int edge_s, edge_e;
freopen("./1134_in", "r", stdin);
cin>>n>>m;
for(int i = 0; i < m; i++){
cin>>edge_s>>edge_e;
edge[edge_s].insert(edge_e);
// edge[edge_e].insert(edge_s);
}
int k, num, tmp_vertex;
cin>>k;
for(int i = 0; i < k; i++){
cin>>num;
set<int> tmp_graph;
for(int j = 0; j < num; j++){
cin>>tmp_vertex;
tmp_graph.insert(tmp_vertex);
// cout<<tmp_vertex<<' ';
}
// cout<<endl;
bool flag = true;
for(int j = 0; j < n; j++){
if(edge[j].size() == 0) continue;
else if(tmp_graph.count(j) != 0) continue;
else {
for(set<int>::iterator iter = edge[j].begin(); iter != edge[j].end(); iter++){
// cout<<*iter<<":"<<tmp_graph.count(*iter)<<" ";
if(tmp_graph.find(*iter) == tmp_graph.end() ){
flag = false;
break;
}
}
// cout<<endl;
}
if(!flag) break;
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}