2016 ICPC 大连 区域赛 A Wrestling Match （交叉染色法判断二分图）
题意：
给出n个点m条边，以及已知的好点和坏点。一个边连接的2个点一定是一好一坏，问是否有合法方案，使得每个点被确定好坏。
思路：
判断二分图。
先染已知的，再染未知的。
注意判掉没有出现的点。
注意有多个联通块。
1
2 /* ***********************************************
3 Author :111qqz
4 Created Time :2017年10月26日 星期四 12时53分06秒
5 File Name :A.cpp
6 ************************************************ */
7
8 #include <bits/stdc++.h>
9 #define PB push_back
10 #define fst first
11 #define sec second
12 #define lson l,m,rt<<1
13 #define rson m+1,r,rt<<1|1
14 #define ms(a,x) memset(a,x,sizeof(a))
15 typedef long long LL;
16 #define pi pair < int ,int >
17 #define MP make_pair
18
19 using namespace std;
20 const double eps = 1E-8;
21 const int dx4[4]={1,0,0,-1};
22 const int dy4[4]={0,-1,1,0};
23 const int inf = 0x3f3f3f3f;
24 const int N=1005;
25 const int M=1E4+7;
26 int n,m,a,b;
27 vector <int>edge[N];
28 int col[N];
29 set<int>se;
30 bool dfs( int u,int x)
31 {
32 col[u] = x;
33 int siz = edge[u].size();
34 for ( int i = 0 ;i < siz ; i++)
35 {
36 int v = edge[u][i];
37 if (col[v]==1-x) continue;
38 if (col[v]==x) return false;
39 if (!dfs(v,1-x)) return false;
40 }
41 return true;
42 }
43 void pr(int a[])
44 {
45 for ( int i = 1 ; i <= n ; i++) printf("%d%c",a[i],i==n?'\n':' ');
46 }
47 vector <int> A,B;
48 bool appear[N];
49 bool ran[N];
50 int main()
51 {
52 #ifndef ONLINE_JUDGE
53 freopen("./in.txt","r",stdin);
54 #endif
55 while (~scanf("%d %d %d %d",&n,&m,&a,&b))
56 {
57
58 bool die = false;
59 ms(col,-1);
60 A.clear();
61 B.clear();
62 ms(appear,false);
63 ms(ran,false);
64 for ( int i = 0 ; i <= n ; i++) edge[i].clear();
65 for ( int i = 1 ; i <= m ; i++)
66 {
67 int u,v;
68 scanf("%d %d",&u,&v);
69 appear[u]=appear[v] = true;
70 edge[u].PB(v);
71 edge[v].PB(u);
72 }
73 for ( int i = 1 ; i <= a ; i++)
74 {
75 int x;
76 scanf("%d",&x);
77 appear[x] = true;
78 A.PB(x);
79 col[x] = 0 ; //0 for good player
80 }
81 for ( int i =1 ; i <= b ; i++)
82 {
83 int x;
84 scanf("%d",&x);
85 appear[x] = true;
86 B.PB(x);
87 col[x] = 1;
88 }
89
90 for ( int i = 1 ; i <= n ; i++) if (!appear[i])
91 {
92 die = true;
93 break;
94 }
95 if (die)
96 {
97 puts("NO");
98 continue;
99 }
100
101 //可能有多个联通块
102 //
103 int siz = A.size();
104 for ( int i = 0 ; i < siz; i++)
105 {
106 int v = A[i];
107 if (!dfs(v,0))
108 {
109 die = true;
110 break;
111 }
112 }
113 if (die)
114 {
115 puts("NO");
116 continue;
117 }
118
119 siz = B.size();
120 for ( int i = 0 ; i < siz; i++)
121 {
122 int v = B[i];
123 if (!dfs(v,1))
124 {
125 die = true;
126 break;
127 }
128 }
129 if (die)
130 {
131 puts("NO");
132 continue;
133 }
134
135 for ( int i = 1 ; i <= n ; i++ )
136 {
137 if (col[i]==-1)
138 {
139 if (!dfs(i,0))
140 {
141 die = true;
142 break;
143 }
144 }
145 }
146
147 if (die)
148 {
149 puts("NO");
150 continue;
151 }
152 puts("YES");
153 }
154
155
156 #ifndef ONLINE_JUDGE
157 fclose(stdin);
158 #endif
159 return 0;
160 }
161