Ubiquitous Religions

最新推荐文章于 2022-01-09 04:15:32 发布

Techay

最新推荐文章于 2022-01-09 04:15:32 发布

阅读量475

点赞数

分类专栏：并查集

本文链接：https://blog.csdn.net/Techay/article/details/48835593

版权

并查集专栏收录该内容

10 篇文章

订阅专栏

本文介绍了一种通过询问部分学生来推断大学内不同宗教信仰数量的方法。利用图论中的并查集算法，解决了如何确定校园内可能存在多少种不同宗教的问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

当今世界有很多不同的宗教,很难通晓他们。你有兴趣找出在你的大学里有多少种不同的宗教信仰。
你知道在你的大学里有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
10 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
10 4
2 3
4 5
4 8
5 8
0 0
Sample Output
Case 1: 1
Case 2: 7
Hint
输入巨大,推荐使用scanf。
同上一题，秒过。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1005;
int n,k,p[50005],r[50005];
void init()
{
    for(int i = 1;i <= n;i++)
    {
        p[i] = i;r[i] = 0;
    }
}
int find(int x)
{
    if(x != p[x])
    {
        int pp = find(p[x]);
        r[x] = (r[x] + r[p[x]])%3;
        p[x] = pp;
    }
    return p[x];
}
bool union_set(int x,int y,int type)
{
    int fx,fy;
    fx = find(x);fy = find(y);
    if(fx == fy)
    {
        if((r[y] - r[x] + 3)%3 != type)return true;
        else return false;
    }
    p[fy] = fx;
    r[fy] = (r[x] - r[y] + type + 3)%3;
    return false;
}
int main()
{
    #ifdef LOCAL
    freopen("C:\\Users\\ΡΡ\\Desktop\\in.txt","r",stdin);
    //freopen("C:\\Users\\ΡΡ\\Desktop\\out.txt","w",stdout);
    #endif // LOCAL
    scanf("%d%d",&n,&k);
        init();
        int temp,x,y;
        int ans = 0;
        while(k--)
        {
            scanf("%d%d%d",&temp,&x,&y);
            if(x > n||y > n||(x == y&&temp == 2))ans++;
            else if(union_set(x,y,temp - 1))ans++;
        }
        printf("%d\n",ans);
    return 0;
}