hdu 4751(dfs染色)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4751

思路：构建新图，对于那些两点连双向边的，忽略，然后其余的都连双向边，于是在新图中，连边的点是能不在同一个图中的，于是我们可以用dfs染色的方法来判断是否存矛盾。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 using namespace std;

 int map[][];

 int color[];

 int n;

 vector<vector<int> >g;

 bool dfs(int u,int father,int state)

 {

     color[u]=state;

     for(int i=;i<g[u].size();i++){

         int v=g[u][i];

         if(v==father)continue;

         if(color[v]&&color[u]==color[v]){

             return false;

         }else if(!color[v]&&!dfs(v,u,-state)){

             return false;

         }

     }

     return true;

 }

 int main()

 {

     int x;

     while(~scanf("%d",&n)){

         memset(map,,sizeof(map));

         memset(color,,sizeof(color));

         for(int i=;i<=n;i++){

             while(true){

                 scanf("%d",&x);

                 if(x==)break;

                 map[i][x]=;

             }

         }

         g.clear();

         g.resize(n+);

         for(int i=;i<=n;i++){

             for(int j=i+;j<=n;j++){

                 if(map[i][j]&&map[j][i])continue;

                 g[i].push_back(j);

                 g[j].push_back(i);

             }

         }

         int flag=;

         for(int i=;i<=n;i++){

             if(g[i].size()>&&!color[i]){

                 if(!dfs(i,i,)){

                     flag=;

                     break;

                 }

             }

         }

         flag?puts("YES"):puts("NO");

     }

     return ;

 }