亲戚 - 题目列表

题目描述

$n$ 个人（ $n \leqslant 100\,000$ ），编号 $1 \dots n$ ，初始每人自成一家族。 $m$ 条操作：

M a b： $a$ 与 $b$ 是亲戚，合并两个家族；
Q a：输出 $a$ 所在家族的人数。

思路

并查集维护每个家族的根，根上记录 sz（家族人数）。合并时按大小合并，小家族挂到大家族根下并累加人数；查询时先 find(a) 找到根，再输出 sz[根]（sz 只在根上有效）。路径压缩保证均摊近似常数。

参考代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#!/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 08:29
# update_at: 2026-10-13 22:28

import sys


class DSU:
    """并查集 (Disjoint Set Union)"""

    def __init__(self, n: int):
        # 1-indexed, fa 初始指向自己，sz 初始为 1
        self.fa = list(range(n + 1))
        self.sz = [1] * (n + 1)

    def find(self, x: int) -> int:
        """查找根节点，两趟路径压缩：先走到根，再把整条路径挂到根上"""
        root = x
        while self.fa[root] != root:
            root = self.fa[root]
        while self.fa[x] != root:
            self.fa[x], x = root, self.fa[x]
        return root

    def same(self, x: int, y: int) -> bool:
        """判断 x 和 y 是否属于同一个集合"""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> bool:
        """按大小合并两个集合 (小树挂大树)；已在同一集合返回 False"""
        fx, fy = self.find(x), self.find(y)
        if fx == fy:
            return False
        if self.sz[fx] < self.sz[fy]:
            fx, fy = fy, fx
        self.fa[fy] = fx
        self.sz[fx] += self.sz[fy]
        return True


def solve() -> None:
    """M a b 合并两个家族，Q a 输出 a 所在家族的人数。"""
    # token 里整数与操作符 M/Q 混排，没法整体 map(int)，按位置顺序消费、用到时再转 int
    data = iter(sys.stdin.buffer.read().split())
    n, m = int(next(data)), int(next(data))
    dsu = DSU(n)  # sz 只在根上有效，取人数要先 find 到根

    out: list[str] = []
    for _ in range(m):
        op = next(data)  # 操作符 token：b"M" 合并 / b"Q" 查询
        if op == b"M":
            a, b = int(next(data)), int(next(data))
            dsu.unite(a, b)  # 按大小合并，小家族整棵挂到大家族的根下
        elif op == b"Q":
            a = int(next(data))
            out.append(str(dsu.sz[dsu.find(a)]))

    print("\n".join(out))


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/**
 * 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:30
 * update_at: 2026-10-13 22:33
 */
#include <iostream>
using namespace std;

typedef long long ll;

// 并查集竞赛精简版（不用 struct）：路径压缩 + 按大小合并
// 口诀：find 找根压到底，unite 小树挂大树
// 易错点：init 别只写 fa[i] = i，sz[i] 也要置 1；合并后 sz 只在新根上有效
// 和别的模板一起用时 maxn 只留一份

const int maxn = 100005;
int fa[maxn], sz[maxn];  // sz[x] 仅在根上有效

void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}

// 查 x 的根，顺手把整条链压到根上
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

bool same(int x, int y) { return find(x) == find(y); }

// 小树挂大树，返回是否真的发生了合并
bool unite(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return false;
    if (sz[fx] < sz[fy]) swap(fx, fy);
    fa[fy] = fx;
    sz[fx] += sz[fy];
    return true;
}

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

    int n, m;
    cin >> n >> m;
    init(n);

    for (int i = 0; i < m; ++i) {
        char op;
        cin >> op;
        if (op == 'M') {
            int a, b;
            cin >> a >> b;
            unite(a, b); // 按大小合并，小家族整棵挂到大家族的根下
        } else if (op == 'Q') {
            int a;
            cin >> a;
            cout << sz[find(a)] << '\n'; // sz 只在根上有效，必须先 find 再取 sz
        }
    }
    return 0;
}

亲戚

目录

题目描述

思路

参考代码