题目链接: hdu 5971 Wrestling Match

题意:N个选手,M场比赛,已知x个好人,y个坏人,问能否将选手划分成好人和坏人两个阵营,保证每场比赛必有一个好人和一个坏人参加。

题解:dfs染色。听说题意模糊?从样例来看,第一个例子应该是因为2可能是好人可能是坏人,所以不确定就NO了...

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#define CLR(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long ll;
const int N = ;
const int inf = 0x3f3f3f3f;
int n, m , x, y, flag;
vector<int> g[N];
int vis[N];
void dfs(int u) {
int f = ;
if(vis[u]==-) {vis[u] = ;f = ;}
for(int i = ; i < g[u].size(); ++i) {
int v = g[u][i];
if(vis[v]==vis[u] && f==) {f=; vis[u] = -vis[v];}
if(vis[v]==vis[u]) flag = ;
if(vis[v]==-) {vis[v] = -vis[u]; dfs(v);}
}
}
int main() {
int i, j, t, u, v;
while(~scanf("%d%d%d%d", &n, &m, &x, &y)) {
for(i = ; i <= n; ++i) g[i].clear();
CLR(vis, -); flag = ;
while(m--) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
while(x--) {
scanf("%d", &u);
vis[u] = ;
}
while(y--) {
scanf("%d", &v);
vis[v] = ;
}
for(i = ; i <= n; ++i){
if(g[i].size()) dfs(i);
}
for(i = ; i <= n; ++i)if(vis[i]==-){flag = ;break;}
if(flag) puts("YES");
else puts("NO");
}
return ;
}

62ms

05-13 23:42