POJ - Ubiquitous Religions

Description

当今世界有很多不同的宗教,很难通晓他们。你有兴趣找出在你的大学里有多少种不同的宗教信仰。

你知道在你的大学里有n个学生(0 < n <= 50000) 。你无法询问每个学生的宗教信仰。此外,许多学生不想说出他们的信仰。避免这些问题的一个方法是问m(0 <= m <= n(n - 1)/ 2)对学生, 问他们是否信仰相同的宗教( 例如他们可能知道他们两个是否去了相同的教堂) 。在这个数据中,你可能不知道每个人信仰的宗教，但你可以知道校园里最多可能有多少个不同的宗教。假定每个学生最多信仰一个宗教。

Input

有多组数据。对于每组数据：

第一行：两个整数n和m。

以下m行：每行包含两个整数i和j，表示学生i和j信仰相同的宗教。学生编号从1到n。

输入的最后一行中,n = m = 0。

Output

对于每组测试数据，输出一行，输出数据序号( 从1开始) 和大学里不同宗教的最大数量。（参见样例）

Sample Input

Sample Output

Case 1: 1

Case 2: 7

Hint

输入巨大,推荐使用scanf

这一题在初步掌握并查集之后也不难，我之所以还是要写上来是因为我之前犯了一个错误，就是节点的更新问题，我妄想用题目所给的数据完成合并之后通过统计不同数字的个数来得到答案

事实证明那是错的，因为有的节点还没来得及更新，比如在合并时先把1指向了0，然后数据给了1，2，合并时2指向了1，因为没有继续查找（如果调用FindRoot（2）就可以使2指向0了，仔细

想象就是因为路径压缩的原因），所以让他们变成了不同的集合

#include<cstdio>

#include<cstring>

#include<queue>

#include<cmath>

#include<algorithm>

using namespace std;

const int MX = 55555;

int stu[MX];

int n, m;

void ini() {

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

        stu[i] = i;

    }

}

int FindRoot(int pos) {

    return stu[pos] == pos ? pos : (stu[pos] = FindRoot(stu[pos]));

}

int main() {

    //freopen("input.txt", "r", stdin);

    int sign = 1;

    while (scanf("%d %d", &n, &m), n || m) {

        ini();

        int a, b;

        for (int i = 0; i < m; i++) {

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

            int root1 = FindRoot(a);

            int root2 = FindRoot(b);

            if (root1 != root2) {

                n--;//正是为了避免由于没有更新节点的问题，才用这种办法来求最后还有几个集合，合并一次集合就少一个

                stu[root2] = root1;

            }

        }

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

    }

    return 0;

}

巴特西

POJ - Ubiquitous Religions

最新文章

热门文章