首页 > 代码库 > hdu4751Divide Groups(dfs枚举完全图集合或者bfs染色)

hdu4751Divide Groups(dfs枚举完全图集合或者bfs染色)

 1 /************************************************************************* 2     > File Name: j.cpp 3     > Author: HJZ 4     > Mail: 2570230521@qq.com  5     > Created Time: 2014年08月28日 星期四 12时26分13秒 6  ************************************************************************/ 7  8 //提議:能否將一個給定的有向圖,變成兩個完全圖(任意兩點都直接相連,雙向邊) 9 10 #include <queue>11 #include <string>12 #include <cstdio>13 #include <stack>14 #include <cstring>15 #include <iostream>16 #include <algorithm>17 #define N 10518 using namespace std;19 20 int a[N], b[N];21 //a, b集合初始化爲空!22 int g[N][N];23 int n;24 25 bool flag;26 27 bool dfs(int u, int la, int lb){28    if(u>n && la+lb==n) return true;//如果a ,b集合中的元素數目恰好是n,則說明可以形成兩個完全圖!29    bool flagx=true;30    for(int i=0; i<la && flagx; ++i)31        if(!(g[a[i]][u] && g[u][a[i]]))32            flagx=false;33    if(flagx) a[la]=u;//如果u節點可以放入a集合中34    if(flagx && dfs(u+1, la+1, lb)) return true;35    bool flagy=true;36    for(int i=0; i<lb && flagy; ++i)37        if(!(g[b[i]][u] && g[u][b[i]]))38             flagy=false;39    if(flagy) b[lb]=u;//如果u節點可以放入b集合中40    if(flagy && dfs(u+1, la, lb+1)) return true;41    return false;42 }43 44 int main(){45    while(scanf("%d", &n)!=EOF){46       memset(g, 0, sizeof(g));47       for(int i=1; i<=n; ++i){48          int v;49          vis[i]=0;50          while(scanf("%d", &v) && v)51            g[i][v]=1;52       }53      flag=dfs(1, 0, 0);54      if(flag)55          printf("YES\n");56      else printf("NO\n");57    }58    return 0;59 }

 1 /************************************************************************* 2     > File Name: j.cpp 3     > Author: HJZ 4     > Mail: 2570230521@qq.com  5     > Created Time: 2014年08月28日 星期四 12时26分13秒 6  ************************************************************************/ 7 //思路:bfs,和判断二分图差不多,将图分成两个集合,如果a和b都有g[a][b]&&g[b][a]说明 8 //a和b一定在同一个集合中,如果有a,b不在一个集合中,a,c不在同一个集合中,b,c也不在同一个 9 //集合中,出现矛盾!也就是这个图不能分成两个完全图!10 #include <queue>11 #include <string>12 #include <cstdio>13 #include <stack>14 #include <cstring>15 #include <iostream>16 #include <algorithm>17 #define N 10518 using namespace std;19 queue<int>q;20 int g[N][N];21 int coll[N];22 int n;23 24 bool bfs(int u){25     while(!q.empty())  q.pop();26     q.push(u);27     while(!q.empty()){28         int x=q.front();29         q.pop();30         for(int y=1; y<=n; ++y){31            if(x==y || g[x][y]&&g[y][x]) continue;32            if(coll[y]==-1){33                 coll[y]=coll[x]^1;34                 q.push(y);35            }36            else if(coll[y]==coll[x])37                 return true;38         }39     }40     return false;41 }42 43 int main(){44    while(scanf("%d", &n)!=EOF){45        memset(g, 0, sizeof(g));46        for(int i=1; i<=n; ++i){47             int v;48             while(scanf("%d", &v) && v)49                 g[i][v]=1;50             coll[i]=-1;51        }52        int i;53        for(i=1; i<=n; ++i){54            if(coll[i]==-1){55                coll[i]=0;//默认是在集合0中56                if(bfs(i)) break;57            }58        }59        if(i<=n) printf("NO\n");60        else printf("YES\n");61    }62    return 0;63 }

 

 

hdu4751Divide Groups(dfs枚举完全图集合或者bfs染色)