hdu 5971 Wrestling Match

时间：2023-03-09 05:48:54
hdu 5971 Wrestling Match

题目链接： 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

相关文章