poj 2524 Ubiquitous Religions(简单并查集)

对与知道并查集的人来说这题太水了，裸的并查集，如果你要给别人讲述并查集可以使用这个题当做例题，代码中我使用了路径压缩，还是有一定优化作用的。

#include <stdio.h>

#include <string.h>

const int maxn = 500005;

int n, m;

int pa[maxn];

void init()

{

    for (int i = 1; i <= n; i++)

    {

        pa[i] = i;

    }

}

int find(int x)

{

    if (x == pa[x])

        return x;

    return pa[x] = find(pa[x]);   //路径压缩，与不压缩的代码差一点点，很神奇。

}

int main()

{

    int a, b, fa, fb;

    int kase = 1;

    while (scanf("%d %d", &n, &m) != EOF)

    {

        if (!(m+n))

            break;

        init();

        int ans = n;

        while (m--)

        {

            scanf("%d %d", &a, &b);

            fa = find(a);

            fb = find(b);

            if (fa != fb)

            {

                ans--;

                pa[fb] = fa;

            }

            else

                continue;

        }

        printf("Case %d: %d\n", kase++, ans);

    }

    return 0;

}

巴特西

poj 2524 Ubiquitous Religions(简单并查集)

最新文章

热门文章