当前位置:首页 > 题解目录 > 正文内容

【题解】家庭问题

亿万年的星光3个月前 (09-27)题解目录338

【题目描述】

有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




【题目分析】

  1. 并查集思路


【参考答案】


#include <bits/stdc++.h>

using namespace std;
int f[105];
int a[105];//结点下的孩子数量
int n, k, cnt, mx;

void init() {
    //由于从1编号的,所以for就不从0了
    for (int i = 1; i <= n; ++i) {
        f[i] = i;
    }
}

int find(int x) {
    if (f[x] == x)
        return x;
    //递归返回时,不断将根节点作为每一个结点的父亲
    return f[x] = find(f[x]);
}

//合并两个结点
void merge(int a, int b) {
    a = find(a);
    b = find(b);
    f[a] = b;
}

int main() {
    cin.tie(0);
    cin >> n >> k;
    init();
    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        merge(x, y);
    }
    for (int i = 1; i <= n; ++i) {
        a[find(i)]++;
        if (f[i] == i) {
            //这是查根节点的数目,可以说明有几个家庭数
            cnt++;
        }
    }
    for (int i = 1; i <= n; ++i) {
        mx = max(mx, a[i]);
    }
    cout << cnt << " " << mx;
    return 0;
}



扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】光荣的梦想

【题目描述】Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平...

【题解】公式成绩

【题目描述】学校的期中考试到了。 gp 老师一共收集到 n 个学生的成绩,每个学生有 5 科成绩,分别是语文、数学、英语、政治、历史。(ai,bi,ci,di,ei) gp 老师突发奇想,他用 m...

【题解】放苹果(1)

【题目描述】把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。【输入】第一行是测试数据的数目t(0≤t≤20)。以下...

【题解】跳格子2

【题目描述】地面上有一排长度为n的格子1-n,每个格子上都有一个数xi,开始时你在位置0,每次你可以向前跳1-2格,然后取走格子上的数,直到跳到位置n+1。取走的数的和就是你的得分,现在你想知道你可能...

【题解】车辆管理

【题目描述】交通管理局长氓氓现在需要一个管理汽车的系统,每一辆汽车都有许多信息需要去记录。 首先,每一辆汽车都有一个独一无二的车牌号 S,车牌号由 7 个字符组成。 然后,对于每一辆车要记录它的排...

大象喝水

【题目描述】上课的时候老师问了小蒜蒜和同学们一个问题:一只大象口渴了,要喝 20 升水才能解渴,但现在只有一个深 h 厘米,底面半径为 r厘米的小圆桶...