PAT甲级1134题（顶点覆盖）

图论题

PAT

发布日期: 2021-02-19

文章字数: 374

阅读时长: 2 分

阅读次数:

1.题目介绍

1134

2.考察点，难度

图论题，Vector容器使用方法，顶点与边考虑角度变换，难度中

3.解题代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, k, nv, a, b, num;
    scanf("%d%d", &n, &m);
    vector<int> v[n];
    for (int i = 0;i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(i);
        v[b].push_back(i);
    }
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &nv);
        int flag = 0;
        vector<int> hash(m, 0);
        for (int j = 0; j < nv; j++) {
            scanf("%d", &num);
            for (int t = 0; t < v[num].size(); t++)
                hash[v[num][t]] = 1;
        }
        for (int j = 0; j < m; j++) {
            if (hash[j] == 0) {
                printf("No\n");
                flag = 1;
                break;
            }
        }
        if (flag == 0) printf("Yes\n");
    }
    return 0;
}

//// ******************** 超时版 从节点角度考虑 *****************************
//#include <bits/stdc++.h>
//using namespace std;
//
//int main(){
//
//    freopen("D:\\PAT\\Clion\\in.txt","r",stdin);
//    int N,M,a,b;
//    cin>>N>>M;
//    vector<int> v[N];
//    for(int i=0;i<M;i++){
//        cin>>a>>b;
//        v[a].push_back(b);
//        v[b].push_back(a);
//    }
//    int K;
//    cin>>K;
//    for(int i=0;i<K;i++){
//        int x,input,flag=0;
//        cin>>x;
//        vector<int> result(N),loss;
//        for(int j=0;j<x;j++){
//            scanf("%d",&input);
//            result[input]=1;
//        }
//        for(int j=0;j<N;j++){
//            if(result[j]==0)
//                loss.push_back(j);
//        }
//        for(int p=0;p<loss.size();p++){
//            for(int q=p+1;q<loss.size();q++){
//                if(count(v[loss[p]].begin(),v[loss[p]].end(),loss[q])!=0){
//                    flag=1;
//                    break;
//                }
//            }
//            if(flag==1)break;
//        }
//        flag?cout<<"No"<<endl:cout<<"Yes"<<endl;
//    }
//    return 0;
//}