UVa 793

　　题目大意：给出计算机之间的连接配置，询问某两台计算机是否相连。判断两个点是否在同一个连通分量里，用并查集处理。

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

View Code