PAT 1134

题目 ： Vertex Cover

分值 ： 25
难度 ： 中等题
思路 ： 一开始想每个节点出度和 - 两两之间边数 == 总边数来判断，不幸超时
       后来参考别人才有下面解法:  每个点 记录下他相连的边 一次输入后，看是否每个边都标记 
坑点 ： 暂未发现

具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int N , M ;
    cin >> N >> M ;
    vector<int> v[N] ;
    for(int i = 0 ; i< M ; i++)
    {
        int c1 ,c2 ;
        cin >> c1 >> c2 ;
        v[c1].push_back(i) ;
        v[c2].push_back(i) ;
    }
    int K ,cur ;
    cin >> K ;
    for(int i = 0 ;i< K ; i++)
    {
        int Nv ,count = 0 ;
        cin >> Nv ;
        vector<int> flag(M, 0 );
        for(int j = 0 ; j< Nv ;j++)
        {
            int temp ;
            cin >> temp ;
            for(int ii = 0 ; ii < v[temp].size() ; ii++)
            {
                flag[ v[temp][ii] ] = 1 ;
            }
        }
        for(int ii = 0 ; ii < M ;ii++)
        {
            if(flag[ii]) count ++ ;
        }
        if(count == M )
            cout <<"Yes"<<endl ;
        else cout <<"No"<<endl ;
    }
}