Posted on 2008-09-04 18:31
Hero 阅读(126)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 //Accepted 1856 312MS 39024K 979 B C++ HDU
2
3 //并查集
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 10000010 ;
10 int father[size] ;
11
12 int inn ;
13
14 int Find( int x )
15 {
16 if( father[x] < 0 ) return x ;
17
18 int fx = Find( father[x] ) ; father[x] = fx ;
19
20 return fx ;
21 }
22
23 void Union( int a, int b )
24 {
25 int fa = Find( a ) ; int fb = Find( b ) ;
26
27 if( fa != fb )
28 {
29 if( father[fa] <= father[fb] )
30 {
31 father[fa] += father[fb] ; father[fb] = fa ;
32 }
33 else
34 {
35 father[fb] += father[fa] ; father[fa] = fb ;
36 }
37 }
38 }
39
40 void input()
41 {
42 for( int i=0; i<size; i++ ) father[i] = -1 ;
43
44 int a, b ; int fa, fb ;
45 for( int i=1; i<=inn; i++ )
46 {
47 scanf( "%d %d", &a, &b ) ; Union( a, b ) ;
48 }
49 }
50
51 void output()
52 {
53 int out = size ;
54 for( int i=1; i<size; i++ ) if( out > father[i] ) out = father[i] ;
55
56 printf( "%d\n", -1*out ) ;
57 }
58
59 int main()
60 {
61 while( scanf( "%d", &inn ) != EOF )
62 {
63 input() ;
64
65 //process() ;
66
67 output() ;
68 }
69
70 return 0 ;
71 }