SSL 1662_家庭问题_并查集

发布于 2019-05-18  31 次阅读


题目描述

有n个人,编号为1,2,……n,另外还知道存在K个关系。一个关系的表达为二元组(α,β)形式,表示α,β为同一家庭的成员。
问题:当n,k和k个关系给出之后,求出其中共有多少个家庭、最大的家庭中有多少人?
例如:
n=6,k=3,三个关系为(1,2),(1,3),(4,5)
此时,6个人组成三个家庭,即:{1,2,3}为一个家庭,{4,5}为一个家庭,{6}单独为一个家庭,第一个家庭的人数为最多。


思路

并查集存一下,然后再跑一次路径压缩,重新枚举求解即可


#include 
#define maxn 101
int f[maxn],fl[maxn];
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);
    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++) find(i);
    for (int i=1;i<=n;i++)
    {
        if (f[i]==0) f[i]=i;
        if (fl[f[i]]==0) ans++;
        fl[f[i]]++;
    }
    int t=0;
    for (int i=1;i<=n;i++)
        if (fl[i]>t) t=fl[i];
    printf("%d %d\n",ans,t);
}
]]>