无聊的写了一个水题，发现 Timus 的题目很好玩啊
判断一个图是不是二分图。bfs 染色即可。
1 #include<stdio.h>
2 #include<iostream>
3 #include<string.h>
4 #include<queue>
5 #include<vector>
6 #define N 108
7 #define inf 0x3ffffff
8 using namespace std;
9 vector<int>g[N];
10 int clor[N];
11 int n;
12 int bfs(int s)
13 {
14 queue<int>q;
15 q.push(s);
16 clor[s]=0;
17 while(!q.empty())
18 {
19 int p=q.front(); q.pop();
20 for(int i=0;i<g[p].size();i++)
21 {
22 if(clor[g[p][i]]==-1)
23 {
24 clor[g[p][i]]=1-clor[p];
25 q.push(g[p][i]);
26 }
27 else if(clor[g[p][i]]!=1-clor[p]) return 0;
28 }
29 }
30 return 1;
31 }
32
33 int main()
34 {
35 while(scanf("%d",&n)!=EOF)
36 {
37 for(int i=0;i<=n;i++) g[i].clear();
38 for(int i=0;i<n;i++)
39 {
40 int k;
41 while(scanf("%d",&k),k)
42 {
43 g[i].push_back(k-1);
44 g[k-1].push_back(i);
45 }
46 }
47 memset(clor,-1,sizeof(clor));
48 int i;
49 for(i=0;i<n;i++)
50 if(clor[i]==-1) if(bfs(i)==0) break;
51 if(i<n) puts("-1");
52 else for(int i=0;i<n;i++)printf(i==n-1?"%d\n":"%d",clor[i]);
53 }
54 return 0;
55 }