1134 Vertex Cover （25 分）

判断是否是点覆盖集
主要用入度是否大于0来判断

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1e4+5;
const int INF = 0x3f3f3f3f;
vector<int> edge[maxn];
int n,m;
bool cover(vector<int> v,int dg[]){
	for(int i=0;i<v.size();i++){
		for(int j=0;j<edge[v[i]].size();j++){
			int u = edge[v[i]][j];
			dg[u]--;
			dg[v[i]]--;
		}
	}
	for(int i=0;i<n;i++){
		if(dg[i] > 0) return false;
	}
	return true;
}
int deg[maxn]={0};
int main(){
	cin>>n>>m;
	int u,v;
	for(int i=0;i<m;i++){
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
		deg[u]++;
		deg[v]++;
	}
	int t,k;
	cin>>t;
	vector<int> cur;
	for(int i=0;i<t;i++){
		cin>>k;
		int newd[maxn];
		for(int x=0;x<n;x++){
			newd[x]=deg[x];
		}
		cur.clear();
		for(int j=0;j<k;j++){
			cin>>u;
			cur.push_back(u);
		}
		//判断是不是点覆盖集 
		if(cover(cur,newd))
		 	printf("Yes\n");
		else 
			printf("No\n");
	}
	
	return 0;
}