计科余定成

解题思路：使用并查集来处理这个问题，将每个人都作为一个初始的集合，然后将每个家庭的成员通过并查集合并在一起，最后将所有家庭的大小求出来并记录下最大的家庭大小即可。
详细步骤：
```cpp
定义一个数组pre来记录每个人所在的集合，最初每个人自成一个独立的集合。
初始化并查集数组，每个人所在的集合都是其本身。
输入k个关系，将每个关系中的两个人所在的集合合并，即将其中一个人所在集合的根节点的父节点修改为另一个人所在集合的根节点。
遍历每个人，找到其所在集合的根节点，并更新该集合中的成员数量。
用哈希表mp来统计每个集合的成员数量，并统计最大家庭的人数。
输出家庭的数量和最大家庭的人数。
```

注意事项：
```cpp
输入的人员编号从1开始，而不是从0开始。
并查集的根节点需要在查询时进行路径压缩，避免树的深度过大影响查询效率。
并查集的复杂度为O(alpha(n))，其中alpha(n)是Ackermann函数的反函数，其增长非常缓慢，理论上可以认为是常数级别的时间复杂度，因此在本题数据范围内，并查集的效率是足够高的。
使用哈希表mp来计算家庭数量，避免遍历并查集数组的时候出现重复的集合。

```

参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int pre[105] = {};//并查集数组
int n, k;
unordered_map<int, int>mp;//使用哈希表来计算家庭
void init() {
    // 初始化并查集数组，每个人最初都是一个独立的集合
    for (int i = 1; i <= n; i++) {
        pre[i] = i;
    }
}
int find(int x) {
    // 寻找x所在集合的根节点
    if (pre[x] != x) {
        return pre[x] = find(pre[x]);
        // 在路径压缩的同时返回根节点
    } else return x;
    // 如果x的父节点是自己，说明已经到达根节点，返回x
}
void merge(int x, int y) {
    // 将x所在集合和y所在集合合并
    pre[find(x)] = find(y);
    // 将x所在集合的根节点的父节点修改为y所在集合的根节点
}
void output() {
    for (int i = 1; i <= n; i++) cout << pre[i] << ' ';
    // 输出并查集数组，调试用
}
int main() {
    cin >> n >> k;
    init();
    int a, b;
    while (k--) {
        cin >> a >> b;
        merge(a, b);
        // 合并a和b所在的集合
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        find(i);
        // 找到i所在集合的根节点
    }
    for (int i = 1; i <= n; i++) {
        mp[pre[i]]++;
        // 统计每个集合中的成员数量
        ans = max(ans, mp[pre[i]]);
        // 更新最大家庭的人数
    }
    cout << mp.size() << ' ' << ans;
    // 输出家庭的数量和最大家庭的人数
    return 0;
}
```

0.0分

2 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言训练-亲密数（C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

家庭问题(并查集+哈希表计数)

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

wu-淘淘的名单（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

Manchester-A+B for Input-Output Practice

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言训练-亲密数 （C语言代码）

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

家庭问题(并查集+哈希表计数)

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

wu-淘淘的名单 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

A+B for Input-Output Practice (IV) （C语言代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

Manchester-A+B for Input-Output Practice

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言训练-亲密数（C语言代码）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C二级辅导-进制转换（C语言代码）

wu-淘淘的名单（C++代码）