BFS，确定每个结点的颜色，发生冲突时输出－1
1 #include <iostream>
2 using namespace std;
3 int n;
4 int link[100][100];
5 bool v[100];
6 int c[100];
7 int q[100],st,en;
8 bool fail=false;
9 void bfs(){
10 st=0; en=1;
11 q[1]=1;
12 c[1]=0;
13 v[1]=true;
14 while (st<en){
15 ++st;
16 int nx=q[st];
17 for (int i=1;i<=link[nx][0];++i){
18 if (v[link[nx][i]]&&c[link[nx][i]]==c[nx]) fail=true;
19 if (!v[link[nx][i]]){
20 ++en;
21 q[en]=link[nx][i];
22 c[link[nx][i]]=1-c[nx];
23 v[link[nx][i]]=true;
24 }
25 }
26 }
27 }
28 int main(){
29 scanf("%d",&n);
30 for (int i=1;i<=n;++i){
31 int x;
32 scanf("%d",&x);
33 while (x>0){
34 link[i][++link[i][0]]=x;
35 link[x][++link[x][0]]=i;
36 scanf("%d",&x);
37 }
38 }
39 bfs();
40 if (fail) cout<<-1;
41 else for (int i=1;i<=n;++i) printf("%d",c[i]);
42 }
43
posted on 2008-11-12 11:52
Joseph 阅读(203)
评论(0) 编辑 收藏 引用