Posted on 2008-12-15 20:46
Hero 阅读(150)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 // 1272 C++ Accepted 0.031 169 KB URAL
2
3 //并查集
4
5 #include <iostream>
6 #include <set>
7
8 using namespace std ;
9
10 const int size = 12010 ;
11
12 int father[size] ;
13
14 int inn, ink, inm ;
15 int ina, inb ;
16
17 int Find( int x )
18 {
19 if( father[x] < 0 ) return x ;
20
21 int fx = Find( father[x] ) ;
22 father[x] = fx ;
23
24 return fx ;
25 }
26
27 void Union( int a, int b )
28 {
29 int fa = Find( a ) ; int fb = Find( b ) ;
30 if( fa != fb )
31 {
32 if( father[fa] < father[fb] )
33 {
34 father[fa] += father[fb] ;
35 father[fb] = fa ;
36 }
37 else
38 {
39 father[fb] += father[fa] ;
40 father[fa] = fb ;
41 }
42 }
43 }
44
45 int main()
46 {
47 while( scanf( "%d %d %d", &inn, &ink, &inm ) != EOF )
48 {
49 memset( father, -1, sizeof(father) ) ;
50
51 for( int i=1; i<=ink; i++ )
52 {
53 scanf( "%d %d", &ina, &inb ) ;
54 Union( ina, inb ) ;
55 }
56
57 int out = 0 ;
58 for( int i=1; i<=inm; i++ )
59 {
60 scanf( "%d %d", &ina, &inb ) ;
61 int fa = Find( ina ) ; int fb = Find( inb ) ;
62 if( fa != fb )
63 {
64 Union( ina, inb ) ;
65 out++ ;
66 }
67 }
68
69 printf( "%d\n", out ) ;
70 }
71 return 0 ;
72 }