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 105
18 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
");
56 else printf("NO
");
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 105
18 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
");
60 else printf("YES
");
61 }
62 return 0;
63 }
