SWF不再：探索Adobe Flash Player下新世代媒体格式的未来

04-2. File Transfer (25)

解题报告：

裸并查集，不过好久不写，路径压缩写漏了，一个点错了一次。。。。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int father[maxn];
//int findroot(int x) {
//    if(x != father[x]) {
//        x = findroot(father[x]);
//    }
//    return x;
//}
int findroot(int x) {
    if(x != father[x]) {
        father[x] = findroot(father[x]);
    }
    return father[x];
}
int main() {
    int n, a, b;
    char s[2];
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) {
        father[i] = i;
    }
    while (scanf("%s", s) != EOF && s[0] != 'S') {
        scanf("%d%d", &a, &b);
        if(s[0] == 'C') {
            if(findroot(a) != findroot(b)) {
                printf("no\n");
            } else {
                printf("yes\n");
            }
        }
        if(s[0] == 'I') {
            int ar = findroot(a);
            int br = findroot(b);
            if(ar != br) {
                father[ar] = br;
                n --;
            }
        }
    }
    if(n == 1) {
        printf("The network is connected.\n");
    } else {
        printf("There are %d components.\n", n);
    }
    return 0;
}