PAT甲级1134.

目录

A1134

题目

样例

输入:

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

输出:

No
Yes
Yes
No
No

思路和坑点

　　思路：
　　vertex cover的概念：图结点的某一个集合，图中每一条边至少涉及集合中一个点。
　　所以，将点集中点涉及到的所有边都进行标记，然后如果图的边未被全部标记，则不是vertex cover，否则是。

AC代码

#include<bits/stdc++.h>
#define MAXN 10004
using namespace std; 
vector<int> v[MAXN];                //二维数组，每一个一维数组存放每一个顶点链接的边的编号
int n,m;                            //顶点数n和边数m
bool vis[MAXN]={false};             //边的访问标记
void Judge();
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){           //读入数据
        int a,b;
        scanf("%d%d",&a,&b);
        v[a].push_back(i);
        v[b].push_back(i);
    }
    int k;
    scanf("%d",&k);
    for(int i=0;i<k;i++)            //依次判断每一组数据
        Judge();
    return 0;    
}
void Judge()
{
    int num,temp;
    fill(vis,vis+m,false);          //初始化vis数组
    bool flag=true;
    scanf("%d",&num);
    for(int i=0;i<num;i++){         //依次读入num个顶点
        scanf("%d",&temp);    
        for(int j=0;j<v[temp].size();j++){
            vis[v[temp][j]]=true;   //将每一个点所联系的边进行标记
        }
    }
    for(int i=0;i<m;i++){           //遍历标记数组
        if(vis[i]==false){
            flag=false; break;      //如果某条边未被访问过，则不构成vertex vocer
        }
    }
    puts(flag?"Yes":"No");           //输出判定结果
}