学步园

http://poj.org/problem?id=1611

题目大意:

有n个学生（标号为0 to n-1),m个学生社团，给出每个社团里所有学生的标号，并假设0号学生患有SARS（社团里只要用一个学生患病，则整个社团里的学生都会被隔离），问最后一共会有多少学生被隔离？

这是一个最基础的并查集的应用，扫描每一个社团，只要两个学生出现在同一个社团，则将这两个集合合并起来，最后输出0号点所在集合的rank值集合（rank值记录这个集合中的元素个数并用一个flag值跟踪0号元素所在集合标号）即可。
这是并查集问题的第一种应用：集合合并，判断两点是不是在同一个集合，求某一个集合上的元素个数等。

code1:

#include <stdio.h>
#include <string.h>
int f[30005];
int total[30005];


int find(int x) {
    while(x!=f[x]) x=f[x];
    return x;
}
int main() {
    int n, m, k, a, b, x, y ,i, ans, root;
    while(scanf("%d%d",&n,&m),n+m) {
        for(i=0; i<=n; i++) {f[i] = i; total[i]=1;}
        while(m--) {
            scanf("%d",&k);
            scanf("%d",&a);
            while(--k) {
                scanf("%d",&b);
                x = find(a);
                y = find(b);
                if(x!=y)
                {
                    total[x] +=total[y];
                f[y] = x;
                }


            }
        }
        printf("%d\n",total[find(0)]);
    }
    return 0;
}

code2:(一样的思路)

#include <stdio.h>
#include <string.h>
int f[30005];
int find(int x) {
    return f[x]==x? x: f[x]=find(f[x]);
}
int main() {
    int n, m, k, a, b, x, y ,i, ans, root;
    while(scanf("%d%d",&n,&m),n+m) {
        for(i=0; i<=n; i++) f[i] = i;
        while(m--) {
            scanf("%d",&k);
            scanf("%d",&a);
            while(--k) {
                scanf("%d",&b);
                x = find(a);
                y = find(b);
                f[y] = x;
            }
        }
        ans = 0;
        root = find(f[0]);
        for(i=0; i<n; i++) {
            f[i]=find(f[i]);
            if(f[i]==root) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}