大连2016A - Wrestling Match HDU

大连2016A - Wrestling Match HDU - 5971（二分图）

本文主要是介绍大连2016A - Wrestling Match HDU - 5971（二分图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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个人，其中有x+y个人的身份确定了。有m场比赛，每场比赛只能好运动员与坏运动员打。试问能否把所有人分成两堆，一堆好运动员，一堆坏运动员。

思路： 感觉题意不是很清楚，存在一个人身份不确定，也没有比过赛的情况怎么办呢？应该可以是任意一个身份，然后可以分在一堆里面的。但是本题不行，有这种情况就是no（样例1）

所以算法就是，二分图染色，对于初始有颜色的人，直接染本身的颜色。所有初始有颜色的人染完了以后，再去染没有颜色的人（随便染一个初始颜色就可以了）。染色中间出问题或者出现有人没有被染色，输出NO。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;
typedef long long ll;
const int MX = 2e6 + 7;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double pi = 3.1415926535;int head[20005],nex[20005],to[20005],tot,color[20005];
int flag;void add(int x,int y)
{to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void init(int m,int n)
{tot = 0;for(int i = 1;i <= max(n * 2,m * 2);i++){head[i] = nex[i] = 0;color[i] = 0;}
}void dfs(int x,int ccolor)
{if(flag == 0)return;for(int i = head[x];i;i = nex[i]){color[x] = ccolor;int v = to[i];if(color[v] == 0)dfs(v,3 - ccolor);else if(color[v] == ccolor){flag = 0;break;}}
}int main()
{int n,m,x,y;while(~scanf("%d%d%d%d",&n,&m,&x,&y)){init(n,m);flag = 1;for(int i = 1;i <= m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}for(int i = 1;i <= x;i++){int tmp;scanf("%d",&tmp);color[tmp] = 1;}for(int i = 1;i <= y;i++){int tmp;scanf("%d",&tmp);color[tmp] = 2;}if(x == 0 && y == 0){for(int i = 1;i <= n;i++){if(color[i])continue;dfs(i,1);if(flag == 0)break;}}else{for(int i = 1;i <= n;i++){if(color[i])dfs(i,color[i]);if(flag == 0)break;}for(int i = 1;i <= n;i++){if(color[i])continue;dfs(i,1);if(flag == 0)break;}}for(int i = 1;i <= n;i++){if(color[i] == 0){flag = 0;break;}}if(flag == 0){printf("NO\n");}else printf("YES\n");}return 0;
}