【HDOJ5971】Wrestling Match（二分图，并查集）

题意：有n个人，m场比赛，x个人为good player，y个人为bad player，

每场比赛两个人分分别为good和bad，问good和bad是否会冲突

1 ≤ N≤ 1000，1 ≤M ≤ 10000

思路：二分图

根据已有的点暴力遍历，判有没有冲突即可

并查集也能写，队友写的搜索

 1 #include <stdio.h>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <string.h>
 5 #include <limits.h>
 6 #include <string>
 7 #include <iostream>
 8 #include <queue>
 9 #include <math.h>
10 #include <map>
11 using namespace std;
12 typedef long long int lint;
13 
14 const int MAXN = 1e3 + 10;
15 const int MAXM = 1e4 + 10;
16 
17 vector<int> g[MAXN];
18 queue<int> a,b;
19 
20 int n,m,x,y;
21 int color[MAXN];
22 
23 void init(){
24     memset(color,-1,sizeof(color));
25     for(int i = 1; i <= n; ++i){ g[i].clear();}
26     while(!a.empty()){ a.pop();}
27     while(!b.empty()){ b.pop();}
28 }
29 
30 bool solve(){
31     while(!a.empty() || !b.empty()){
32         while(!a.empty()){
33             int now = a.front(); a.pop();
34             for(int i = 0; i < g[now].size(); ++i){
35                 if(color[g[now][i]] == -1){
36                     color[g[now][i]] = 1; b.push(g[now][i]);
37                 }else if(color[g[now][i]] == 0){
38                     return false;
39                 }
40             }
41         }
42         while(!b.empty()){
43             int now = b.front(); b.pop();
44             for(int i = 0; i < g[now].size(); ++i){
45                 if(color[g[now][i]] == -1){
46                     color[g[now][i]] = 0; a.push(g[now][i]);
47                 }else if(color[g[now][i]] == 1){
48                     return false;
49                 }
50             }
51         }
52     }
53     return true;
54 }
55 
56 int main(){
57     while(scanf("%d%d%d%d",&n,&m,&x,&y)!=EOF){
58         init();
59         for(int i = 1; i <= m; ++i){
60             int u,v; scanf("%d%d",&u,&v);
61             g[u].push_back(v); g[v].push_back(u);
62         }
63         for(int i = 1; i <= x; ++i){
64             int num; scanf("%d",&num); a.push(num); color[num] = 0;
65         }
66         for(int i = 1; i <= y; ++i){
67             int num; scanf("%d",&num); b.push(num); color[num] = 1;
68         }
69         if(!solve()){
70             printf("NO
"); continue;
71         }
72         bool flag = true;
73         for(int i = 1; i <= n; ++i){
74             if(color[i] == -1 && g[i].size() != 0){
75                 a.push(i);
76                 if(!solve()){
77                     flag = false; break;
78                 }
79             }else if(color[i] == -1 && g[i].size() == 0){
80                 flag = false; break;
81             }
82         }
83         if(!flag){
84             printf("NO
"); continue;
85         }else{
86             printf("YES
"); continue;
87         }
88     }
89     return 0;
90 }