Posted on 2008-09-04 19:36
Hero 閱讀(153)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //Accepted 1829 578MS 0K 1455 B C++ HDU
2
3 //雙集合問題--
非此即彼思想的運用
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 3000 ;
10
11 int father[size*3] ;
12
13 int innum ;
14 int inn, ink ;
15
16 void input()
17 {
18 memset( father, -1, sizeof(father) ) ;
19
20 scanf( "%d %d", &inn, &ink ) ;
21 }
22
23 int Find( int x )
24 {
25 if( father[x] < 0 ) return x ;
26 int fx = Find( father[x] ) ;
27 father[x] = fx ;
28
29 return fx ;
30 }
31
32 void Union( int a, int b )
33 {
34 int fa = Find( a ) ;
35 int fb = Find( b ) ;
36
37 if( fa != fb )
38 {
39 if( father[fa] <= father[fb] )
40 {
41 father[fa] += father[fb] ;
42 father[fb] = fa ;
43 }
44 else
45 {
46 father[fb] += father[fa] ;
47 father[fa] = fb ;
48 }
49 }
50 }
51
52 void process()
53 {
54 int x, y ; int fx, fy ; bool found = false ; int i ;
55 for( i=1; i<=ink; i++ )
56 {
57 scanf( "%d %d", &x, &y ) ;
58
59 fx = Find( x ) ; fy = Find( y ) ;
60
61 if( fx == fy )
62 {
63 found = true ; printf( "Suspicious bugs found!\n" ) ; break ;
64 }
65 else
66 {
67 Union( x, y+size ) ; Union( x+size, y ) ;
68 }
69 }
70
71 for( i=i+1; i<=ink; i++ ) scanf( "%d %d", &x, &y ) ;
72
73 if( false == found )
74 {
75 printf( "No suspicious bugs found!\n" ) ;
76 }
77
78 printf( "\n" ) ;
79 }
80
81 int main()
82 {
83 //freopen( "in.txt", "r", stdin ) ;
84
85 //while( scanf( "%d", &innum ) != EOF )
86 scanf( "%d", &innum ) ;
87 {
88 for( int ct=1; ct<=innum; ct++ )
89 {
90 printf( "Scenario #%d:\n", ct ) ;
91
92 input() ;
93
94 process() ;
95
96 //output() ;
97 }
98 }
99
100 return 0 ;
101 }