poj 2524_Ubiquitous Religions_并查集

发布于 2019-04-27  9 次阅读


题目大意

求出一堆关系中集合的个数

思路

用并查集存每一个状态,最后判断一下有多少个f[i]为0的点
O(n)
这里注意要输出题目给的全部东西

#include 
int f[100001];
int find(int x)
{
    if (!f[x]) return x;
    f[x]=find(f[x]);
    return f[x];
}
int insert(int x,int y)
{
    if (find(x)!=find(y))
    {
        f[find(x)]=find(y);
        return 1;
    }
    return 0;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int o=0;
    while (n!=0||m!=0)
    {
        o++;
        for (int i=1;i<=100000;i++)
            f[i]=0;
        for (int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            insert(x,y);
        }
        int ans=0;
        for (int i=1;i<=n;i++)
            if (f[i]==0) ans++;
        printf("Case %d: %d\n",o,ans);
        scanf("%d%d",&n,&m);
    }   
}
]]>