UVa 459

　　题目大意：给你一个无向图的顶点和边集，让你求图中连通分量的个数。使用并查集解决。

 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAXN 30
 4 
 5 bool G[MAXN][MAXN];
 6 int p[MAXN];
 7 
 8 int find(int x)
 9 {
10     return x == p[x] ? x : p[x]=find(p[x]);
11 }
12 
13 int main()
14 {
15 #ifdef LOCAL
16     freopen("in", "r", stdin);
17 #endif
18     int T;
19     scanf("%d", &T);
20     getchar();
21     char str[20];
22     gets(str);
23     while (T--)
24     {
25         memset(G, 0, sizeof(G));
26         gets(str);
27         int n = str[0] - 'A' + 1;
28         for (int i = 0; i < n; i++)
29             p[i] = i;
30         int cnt = n;
31         while (gets(str))
32         {
33             if (str[0] == 0)  break;
34             int a = str[0] - 'A';
35             int b = str[1] - 'A';
36             int pa = find(a);
37             int pb = find(b);
38             if (pa != pb)
39             {
40                 p[pb] = pa;
41                 cnt--;
42             }
43         }
44         printf("%d
", cnt);
45         if (T)  printf("
");
46     }
47     return 0;
48 }

View Code