题目

源地址：

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

理解

POJ上最简单的一道关于并查集的题目，没有使用路径压缩，没有进行优化，直接水过。

代码


#include <cstdio>

int f[50005], sum;

int find(int x)
{
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}

void make(int a, int b)
{
    int f1 = find(a);
    int f2 = find(b);
    if (f1 != f2)
    {
        f[f2] = f1;
        sum--;
    }
}

int main(int argc, char const *argv[])
{
    int n, m, p = 1, i;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        if (n == 0 && m == 0)  break;
        for (i = 1; i <= n; i++)    f[i] = i;
        sum = n;
        for (i = 1; i <= m; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            make(a, b);
        }
        printf("Case %d: %d\n", p++, sum );
    }
    return 0;
}

更新日志

  • 2014年07月22日 已AC。