hdu4751Divide Groups（dfs枚举完全图集合或者bfs染色）

/*************************************************************************
    > File Name: j.cpp
    > Author: HJZ
    > Mail: 2570230521@qq.com
    > Created Time: 2014年08月28日 星期四 12时26分13秒
 ************************************************************************/

//提議：能否將一個給定的有向圖，變成兩個完全圖（任意兩點都直接相連，雙向邊）

#include <queue>
#include <string>
#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;

int a[N], b[N];
//a， b集合初始化爲空！
int g[N][N];
int n;

bool flag;

bool dfs(int u, int la, int lb){
   if(u>n && la+lb==n) return true;//如果a ，b集合中的元素數目恰好是n，則說明可以形成兩個完全圖！
   bool flagx=true;
   for(int i=0; i<la && flagx; ++i)
       if(!(g[a[i]][u] && g[u][a[i]]))
           flagx=false;
   if(flagx) a[la]=u;//如果u節點可以放入a集合中
   if(flagx && dfs(u+1, la+1, lb)) return true;
   bool flagy=true;
   for(int i=0; i<lb && flagy; ++i)
       if(!(g[b[i]][u] && g[u][b[i]]))
            flagy=false;
   if(flagy) b[lb]=u;//如果u節點可以放入b集合中
   if(flagy && dfs(u+1, la, lb+1)) return true;
   return false;
}

int main(){
   while(scanf("%d", &n)!=EOF){
      memset(g, 0, sizeof(g));
      for(int i=1; i<=n; ++i){
         int v;
         vis[i]=0;
         while(scanf("%d", &v) && v)
           g[i][v]=1;
      }
     flag=dfs(1, 0, 0);
     if(flag)
         printf("YES\n");
     else printf("NO\n");
   }
   return 0;
}
/*************************************************************************
    > File Name: j.cpp
    > Author: HJZ
    > Mail: 2570230521@qq.com
    > Created Time: 2014年08月28日 星期四 12时26分13秒
 ************************************************************************/
//思路：bfs，和判断二分图差不多，将图分成两个集合，如果a和b都有g[a][b]&&g[b][a]说明
//a和b一定在同一个集合中，如果有a，b不在一个集合中，a，c不在同一个集合中，b，c也不在同一个
//集合中，出现矛盾！也就是这个图不能分成两个完全图！
#include <queue>
#include <string>
#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 105
using namespace std;
queue<int>q;
int g[N][N];
int coll[N];
int n;

bool bfs(int u){
    while(!q.empty())  q.pop();
    q.push(u);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int y=1; y<=n; ++y){
           if(x==y || g[x][y]&&g[y][x]) continue;
           if(coll[y]==-1){
                coll[y]=coll[x]^1;
                q.push(y);
           }
           else if(coll[y]==coll[x])
                return true;
        }
    }
    return false;
}

int main(){
   while(scanf("%d", &n)!=EOF){
       memset(g, 0, sizeof(g));
       for(int i=1; i<=n; ++i){
            int v;
            while(scanf("%d", &v) && v)
                g[i][v]=1;
            coll[i]=-1;
       }
       int i;
       for(i=1; i<=n; ++i){
           if(coll[i]==-1){
               coll[i]=0;//默认是在集合0中
               if(bfs(i)) break;
           }
       }
       if(i<=n) printf("NO\n");
       else printf("YES\n");
   }
   return 0;
}