直接合并，合并完以后看一共存在幾個集合，我再查有幾個集合的時候有點兒蛋疼捉急，哪位大神有好方法告訴一下哈～
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 50010
9 int p[N];
10 int find(int x)
11 {
12 return p[x] != x ? p[x] = find(p[x]) : x;
13 }
14 int main()
15 {
16 int n, m;
17 int x, y;
18 int r1, r2;
19 int t = 1;
20 int rr[N];
21 while (scanf("%d%d", &n, &m) != EOF)
22 {
23 memset(rr, 0, sizeof(rr));
24 if (n == 0 && m == 0) break;
25 for (int i = 1; i <= n; i++)
26 p[i] = i;
27 while (m--)
28 {
29 scanf("%d%d", &x, &y);
30 r1 = find(x); r2 = find(y);
31 if (r1 != r2)
32 p[r2] = r1;
33 }
34 for (int i = 1; i <= n; i++)
35 {
36 rr[i] = find(i);
37 }
38 sort(rr + 1, rr + n + 1);
39 int ans = 1;
40 for (int i = 2; i <= n; i++)
41 if (rr[i] != rr[i - 1]) ans++;
42 printf("Case %d: %d\n", t++, ans);
43 }
44 return 0;
45
|