kruskal_并查集_代码模板_hdu1232

a b
v1 v2 w1
v2 v3 w2
...

1 #include
2 #include<string>
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include

1 using namespace std;
2
3 int add;
4 int f[100010];
5 int n, m;
6
7 int findset(int x)
8 {
9 int set &＃61; x;
10 while(f[set] !&＃61; set)
11 {
12 set &＃61; f[set];
13 }
14 return set;
15 }
16
17 void merge(int a, int b)
18 {
19 int x &＃61; findset(a);
20 int y &＃61; findset(b);
21 if(x !&＃61; y)
22 f[x] &＃61; y;
23 }
24
25 int main()
26 {
27 freopen("in.txt", "r", stdin);
28 while(scanf("%d %d", &n, &m) &＃61;&＃61; 2)
29 {
30 add &＃61; 0;
31 if(n &＃61;&＃61; 0)
32 break;
33 else if(m &＃61;&＃61; 0)
34 {
35 add &＃61; n - 1;
36 printf("%d\n", add);
37 }
38 else
39 {
40 for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) f[i] &＃61; i;
41
42 for(int i &＃61; 0; i )
43 {
44 int a, b;
45 scanf("%d %d", &a, &b);
46 merge(a, b);
47 }
48
49 for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;)
50 if(f[i] &＃61;&＃61; i)
51 add&＃43;&＃43;;
52 add--;
53 printf("%d\n", add);
54 }
55 //
56 memset(f, 0, sizeof(f));
57 }
58 }
59
60 /*
61 4 2
62 1 3
63 4 3
64 3 3
65 1 2
66 1 3
67 2 3
68 5 2
69 1 2
70 3 5
71 999 0
72 0
73
74 */