家庭问题

题目描述

有 $n$ 个人（编号 $1 \sim n$ ）和 $k$ 个关系 $(a,b)$ ，表示 $a$ 与 $b$ 是同一家庭的成员，关系可传递。输入第一行 $n,k$ （ $1 \le n \le 100$ ），后接 $k$ 行每行两个整数；输出两个整数，即家庭个数与最大家庭人数。

样例输入

text

样例输出：3 3。

思路

把每个人看作点、每个关系看作无向边，同一连通块的人就是一家人，问题即求连通块个数与最大连通块大小。用并查集依次合并每个关系中的两人，再对每个人查代表元统计各家庭人数，人数非零的家庭数就是答案第一部分，其中的最大值是第二部分。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 07:05
# update_at: 2026-10-04 13:21

import sys
from collections import defaultdict


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:                                        # 空输入：直接返回
        return
    k = next(data)
    edges = [(next(data), next(data)) for _ in range(k)]  # 每次顺序消费一对关系 (α, β)

    parent = list(range(n + 1))                          # 并查集：每个人的代表元

    def find(x: int) -> int:
        """带路径压缩查找 x 所在集合的代表元。"""
        while parent[x] != x:
            parent[x] = parent[parent[x]]                  # 路径减半
            x = parent[x]
        return x

    def union(x: int, y: int) -> None:
        """把 x、y 所在家庭合并。"""
        rx, ry = find(x), find(y)
        if rx != ry:
            parent[ry] = rx

    for x, y in edges:
        union(x, y)

    size = defaultdict(int)                              # 每个家庭代表元 → 人数
    for i in range(1, n + 1):
        size[find(i)] += 1

    families = len(size)                                 # 家庭总数
    largest = max(size.values()) if size else 0          # 最大家庭人数
    print(f"{families} {largest}")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:00
 * update_at: 2026-10-05 12:00
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

typedef long long ll;

ll n, k;
ll parent[MAXN]; // parent[i] 表示第 i 个人所在家庭的代表元
ll cnt[MAXN];    // cnt[代表元] = 该家庭的人数

// 查找 x 所在家庭的代表元，路径减半压缩。
ll find_root(ll x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

// 把 x、y 所在的两个家庭合并。
void union_family(ll x, ll y) {
    ll rx = find_root(x);
    ll ry = find_root(y);
    if (rx != ry) {
        parent[ry] = rx;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;

    // 最初每个人自己就是一个家庭。
    for (ll i = 1; i <= n; i++) {
        parent[i] = i;
    }

    // 每读入一个关系就把它看作一条无向边，合并两个家庭。
    for (ll i = 1; i <= k; i++) {
        ll x, y;
        cin >> x >> y;
        union_family(x, y);
    }

    ll families = 0;  // 家庭个数
    ll largest = 0;   // 最大家庭人数
    for (ll i = 1; i <= n; i++) {
        cnt[find_root(i)]++;
    }
    for (ll i = 1; i <= n; i++) {
        if (cnt[i] > 0) {
            families++;
            if (largest < cnt[i]) {
                largest = cnt[i];
            }
        }
    }

    cout << families << " " << largest << "\n";
    return 0;
}

目录

题目描述

思路

参考代码