title: PAT1134
date: 2021-01-22 20:03:07
tags: PAT

1134

题目：

检查子图是否能够满足顶点覆盖

定点覆盖

即图的所有的边两端的结点，是否至少一个结点出自顶点集合中

范围:

1. 顶点 <= 10^4
2. 边 <= 10^4
3. 子集数 <= 100
4. 子集元素数 未说明 可能是 <= 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; 
    }

}