hdoj1232 畅通工程（并查集）

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1232

思路

使用并查集求解。

代码

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 1000 + 10;
 7 int p[N];
 8 
 9 void make_set(int n)
10 {
11     for (int i = 1; i <= n; i++)
12         p[i] = -1;
13 }
14 
15 int find_root(int i)
16 {
17     if (p[i] == -1)
18         return i;
19     else
20     {
21         int t = find_root(p[i]);    //路径压缩
22         p[i] = t;
23         return t;
24     }
25 }
26 
27 void union_set(int a, int b)
28 {
29     int ra = find_root(a);
30     int rb = find_root(b);
31     if (ra != rb)
32         p[ra] = rb;
33 
34 }
35 
36 int main()
37 {
38     //freopen("hdoj1232.txt", "r", stdin);
39     int n, m;
40     while (scanf("%d%d", &n, &m) == 2 && n)
41     {
42         make_set(n);
43         int a, b;
44         for (int i = 0; i < m; i++)
45         {
46             scanf("%d%d", &a, &b);
47             union_set(a, b);
48         }
49         int ans = 0;
50         for (int i = 1;i <= n;i++)
51             if (p[i] == -1) ans++;
52         printf("%d
", ans - 1);
53     }
54     return 0;
55 }