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=; 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+, la+, lb)) return true;
    bool flagy=true;
    for(int i=; 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+, la, lb+)) return true;
    return false;
 } int main(){
    while(scanf("%d", &n)!=EOF){
       memset(g, , sizeof(g));
       for(int i=; i<=n; ++i){
          int v;
          vis[i]=;
          while(scanf("%d", &v) && v)
            g[i][v]=;
       }
      flag=dfs(, , );
      if(flag)
          printf("YES\n");
      else printf("NO\n");
    }
    return ;
 }

 /*************************************************************************
     > 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=; y<=n; ++y){
            if(x==y || g[x][y]&&g[y][x]) continue;
            if(coll[y]==-){
                 coll[y]=coll[x]^;
                 q.push(y);
            }
            else if(coll[y]==coll[x])
                 return true;
         }
     }
     return false;
 } int main(){
    while(scanf("%d", &n)!=EOF){
        memset(g, , sizeof(g));
        for(int i=; i<=n; ++i){
             int v;
             while(scanf("%d", &v) && v)
                 g[i][v]=;
             coll[i]=-;
        }
        int i;
        for(i=; i<=n; ++i){
            if(coll[i]==-){
                coll[i]=;//默认是在集合0中
                if(bfs(i)) break;
            }
        }
        if(i<=n) printf("NO\n");
        else printf("YES\n");
    }
    return ;
 }