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("YESn");56 else printf("NOn");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("NOn");60 else printf("YESn");61 }62 return 0;63 }

 

 

转载于:https://www.cnblogs.com/hujunzheng/p/3942077.html