信息学奥赛一本通T1362：队列 家庭问题

【题目描述】有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｝单独为一个家庭，第一个家庭的人数为最多。

信息学奥赛一本通T1362：家庭问题

【题目描述】

有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｝单独为一个家庭，第一个家庭的人数为最多。

【输入】

第一行为n,k二个整数（1≤n≤100）（用空格分隔）;

接下来的k行，每行二个整数（用空格分隔）表示关系。

【输出】

二个整数（分别表示家庭个数和最大家庭人数）。

【输入样例】

6  3
1  2
1  3
4  5

【输出样例】

3 3

【源程序】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 301
#define MOD 123
#define E 1e-6
using namespace std;
int father[N];
int a[N];
int Find(int x)
{
    if(father[x]==x)
        return x;
    return father[x]=Find(father[x]);
}
void Union(int x,int y)
{
    int f1=Find(x);
    int f2=Find(y);
    if(f1!=f2)
        father[f2]=f1;
}
int main()
{
    int n,k;

    cin>>n>>k;
    for(int i=1;i<=n;i++)
        father[i]=i;
    for(int i=1;i<=k;i++)
    {
        int x,y;
        cin>>x>>y;
        Union(x,y);
    }

    for(int i=1;i<=n;i++)
        a[Find(i)]++;

    int cnt_1=0,cnt_2=0;
    for(int i=1;i<=n;i++)
        if(a[i]>cnt_2)
            cnt_2=a[i];
    for(int i=1;i<=n;i++)
        if(father[i]==i)
            cnt_1++;

    cout<<cnt_1<<" "<<cnt_2<<endl;
    return 0;
}

 

信息学奥赛一本通T1362：队列 家庭问题 归属于 队列，更多同类题解源程序见：队列 和 家庭问题

你可能感兴趣的文章

相关问题

0 条评论

请先 登录 后评论
不写代码的码农
轩爸

0 篇文章

作家榜 »

  1. admin 2 文章
  2. 张芳 0 文章
  3. hanna 0 文章
  4. Jason 0 文章
  5. lixiaioqian 0 文章
  6. GeraldWrora 0 文章
  7. 董伟 0 文章
  8. 信奥达人 0 文章

轩爸

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！