Wrestling Match

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3243    Accepted Submission(s): 1150

 

Problem Description

Nowadays, at least one wrestling match is held every year in our country. There are a lot of people in the game is "good player”, the rest is "bad player”. Now, Xiao Ming is referee of the wrestling match and he has a list of the matches in his hand. At the same time, he knows some people are good players,some are bad players. He believes that every game is a battle between the good and the bad player. Now he wants to know whether all the people can be divided into "good player" and "bad player".

Input

Input contains multiple sets of data.For each set of data,there are four numbers in the first line:N (1 ≤ N≤ 1000)、M(1 ≤M ≤ 10000)、X,Y(X+Y≤N ),in order to show the number of players(numbered 1toN ),the number of matches,the number of known "good players" and the number of known "bad players".In the next M lines,Each line has two numbersa, b(a≠b) ,said there is a game between a and b .The next line has X different numbers.Each number is known as a "good player" number.The last line contains Y different numbers.Each number represents a known "bad player" number.Data guarantees there will not be a player number is a good player and also a bad player.

Output

If all the people can be divided into "good players" and "bad players”, output "YES", otherwise output "NO".

Sample Input

5 4 0 0 
1 3 
1 4 
3 5 
4 5 
5 4 1 0 
1 3 
1 4 
3 5 
4 5 
2

Sample Output

NO 
YES

题意：有n名选手，m个对局，每局比赛都是有good player 和 bad player 对打。有x名选手和y名选手已经表明身份，问能否推出每个人是good player 还是 bad player。

第一次学习染色，借鉴大神的代码，把理解的地方都注释出来了，如有不对还请评论区斧正

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)

int n,m,x,y;
vector<int>g[20005];
int color[20005];

int dfs(int s) {
	int i;
	for(i=0; i<g[s].size(); i++) {
		int v=g[s][i];
		if(color[v]==0) {		  //染色 
			color[v]=-color[s];
			if(!dfs(v))	         //若后续染色中断则失败 
				return 0;
		} 
		else if(color[s]==color[v])      //同为bad player或good player，冲突 
			return 0;
	}
	return 1;
}

int main() {
	int i,a,b;
	while(~scanf("%d%d%d%d",&n,&m,&x,&y)) {
		mem(color,0);
		for(i=0; i<20005; i++)			//对vector g[]初始化 
			g[i].clear();
		for(i=0; i<m; i++) {
			scanf("%d%d",&a,&b);
			g[a].push_back(b);              //g[a]中包含的所有元素都与a为对手 
			g[b].push_back(a);
		}
		for(i=0; i<x; i++) {
			scanf("%d",&a);
			color[a]=1;
		}
		for(i=0; i<y; i++) {
			scanf("%d",&b);
			color[b]=-1;
		}
		if((x==0&&y==0)||n==1) {		//1.当x,y都等于0时无法染色，每个人都可能是bad或good player 
			printf("NO\n");			//2.当n==1时，只有1名选手 ，不考虑 
			continue;
		}
		int flag=0;
		for(i=1; i<=n; i++) {
			if(color[i]!=0&&dfs(i)==0) {	//由被x和y标识出的选手为突破口开始染色，dfs(i)==0b表示染色中断，自动结束 
				flag=1;
				break;
			}
		}
		for(i=1; i<=n; i++) {
			if(color[i]==0) {		//【注释1】对于没有被染色的选手， 默认为good player，往下染色，判定有无冲突 
				color[i]=1;
				if(dfs(i)==0) {
					flag=1;
					break;
				}
			}
		}
		if(!flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

注释1：

对于数据：

5 3 1 0
1 2
3 4
4 5
5

1和2的身份并不能确定谁是good谁是bad，但是oj判对，默认1为good player，判定染色能够通过即可

OS：要开始组队打比赛了，所以代码规范要协同一下，大括号不换行对于强迫症真难受TAT