Posted on 2009-08-14 16:29
Hero 閱讀(285)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 // URAL 1080 C++ Accepted 0.031 233 KB
2
3 //DFS
4
5 #include <iostream>
6 using namespace std ;
7
8 const int size = 100 ;
9 int edge[size][size] ;
10 int out[size] ;
11 int inn ;
12 int inm ;
13 bool OK ;
14
15 void DFS( int sn )
16 {
17 if( false == OK ) return ;
18
19 for( int i=1; i<=inn; i++ )
20 {
21 if( edge[sn][i] )
22 {
23 if( -1 == out[i] )
24 {
25 out[i] = (out[sn]+1)&1 ;
26 DFS( i ) ;
27 }
28 else if( out[sn] == out[i] )
29 {
30 OK = false ; return ;
31 }
32
33 //DFS( i ) ;
34 }
35 }
36 }
37
38 int main()
39 {
40 while( cin >> inn )
41 {
42 OK = true ;
43 memset( edge, 0, sizeof(edge) ) ;
44 memset( out, -1, sizeof(out) ) ;
45
46 for( int i=1; i<=inn; i++ )
47 {
48 while( cin >> inm && inm )
49 {
50 edge[i][inm] = edge[inm][i] = 1 ;
51 }
52 }//data input
53
54 for( int i=1; i<=inn; i++ )
55 {
56 if( -1 == out[i] )
57 {
58 out[i] = 0 ;
59 DFS( i ) ;
60 }
61 }
62
63 if( OK )
64 {
65 for( int i=1; i<=inn; i++ )
66 printf( "%d", out[i] ) ;
67 printf( "\n" ) ;
68 }
69 else
70 {
71 printf( "-1\n" ) ;
72 }
73 }
74 return 0 ;
75 }