Posted on 2008-09-04 21:12
Hero 閱讀(176)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 // 1003 C++ Accepted 0.093 261 KB Ural
2
3 //非此即彼思想的應用
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 10000 ;
10
11 int father[size*2] ;
12 int table[size] ;
13
14 char cmd[20] ;//輸入的even或者odd
15 int inlen ;
16 int inn ;
17
18
19 int Hash( int x )
20 {//輸進去的是大數,返回的該大數在table[]中的下標
21 int posi = x % size ;
22 while( table[posi]!=-1 && table[posi]!=x )
23 posi = (posi+1) % size ;
24 table[posi] = x ;
25
26 return posi ;//用下標來代替(hash)大數
27 }
28
29 int Find( int x )
30 {
31 if( father[x] < 0 ) return x ;
32 int fx = Find( father[x] ) ;
33 father[x] = fx ;
34
35 return fx ;
36 }
37
38 void Union( int a, int b )
39 {
40 int fa = Find( a ) ;
41 int fb = Find( b ) ;
42
43 if( fa != fb )
44 {
45 if( father[fa] <= father[fb] )
46 {
47 father[fa] += father[fb] ;
48 father[fb] = fa ;
49 }
50 else
51 {
52 father[fb] += father[fa] ;
53 father[fa] = fb ;
54 }
55 }
56 }
57
58 void input()
59 {
60 scanf( "%d", &inn ) ;
61
62 memset( father, -1, sizeof(father) ) ;
63 memset( table, -1, sizeof(table) ) ;
64 }
65
66 void process()
67 {
68 int x, y ; int fx, fy ; int i ;
69
70 for( i=1; i<=inn; i++ )
71 {
72 scanf( "%d %d", &x, &y ) ; getchar() ;
73 x = Hash( x-1 ) ; fx = Find( x ) ;
74 y = Hash( y ) ; fy = Find( y ) ;
75
76 scanf( "%s", cmd ) ;
77 //注意判斷在不在同一個集合中要用 "=="
78 if( 'e' == cmd[0] )//even--說明 x 和 y 同奇偶
79 {
80 //if( Find(x) != Find(y) )//不能說明一定在兩個不同的集合中
81 //--可能存在尚未分配x和y的情況--可能在一個集合中
82 //而Find(x)==Find(x+size)一定可以說明在兩個不同的集合中--由初始化決定
83 if( Find(x)==Find(y+size) )//如果不在同一個集合--該cmd不成立
84 {
85 break ;
86 }
87 else
88 {
89 Union( x, y ) ; Union( x+size, y+size ) ;
90 }
91 }
92 else//odd--說明 x 和 y 不同奇偶
93 {
94 if( Find(x)==Find(y) )//在同一個集合中
95 {
96 break ;
97 }
98 else
99 {
100 Union( x, y+size ) ; Union( x+size, y ) ;
101 }
102 }
103 }//for
104
105 printf( "%d\n", i-1 ) ;
106
107 for( i=i+1; i<=inn; i++ )
108 {
109 scanf( "%d %d", &x, &y ) ;//捕捉剩余輸出
110 scanf( "%s", cmd ) ;
111 }
112 }
113
114
115 int main()
116 {
117 //freopen( "in.txt", "r", stdin ) ;
118
119 while( scanf( "%d", &inlen ) != EOF && (inlen!=-1) )
120 {
121 input() ;
122
123 process() ;
124
125 //output() ;
126 }
127
128 return 0 ;
129 }