【例4-7】亲戚(relation)

题目描述

给出 $N$ 个人（编号 $1 \sim N$ ）与 $M$ 条已知亲戚关系（亲戚关系可以传递），再给 $Q$ 次询问，每次问两人是否是亲戚。输入：第一行 $N, M$ ；接下来 $M$ 行每行 $a_i, b_i$ 表示 $a_i$ 和 $b_i$ 是亲戚；然后一行 $Q$ ，接下来 $Q$ 行每行 $c_i, d_i$ 表示一次询问， $1 \le N \le 20000$ ， $1 \le M, Q \le 10^6$ 。输出：对每个询问输出一行，是亲戚输出 Yes，否则输出 No。样例：输入 10 7 / 2 4 / 5 7 / 1 3 / 8 9 / 1 2 / 5 6 / 2 3 / 3 / 3 4 / 7 10 / 8 9（/ 表示换行），输出 Yes / No / Yes。

思路

「是亲戚」具有传递性，本题就是无向图连通性问题：把每条关系看成一条边，用按大小合并加路径压缩的并查集把全部关系合并完，之后每次询问只需比较两人的代表元是否相同。

参考代码

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 06:22
# 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 main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)  # 首 token 是人数；空输入按原样直接返回
    if n is None:
        return
    m = next(data)     # 关系条数
    dsu = DSU(n)       # 初始各自成块

    for _ in range(m):
        a, b = next(data), next(data)  # 一条关系连接 a、b
        dsu.unite(a, b)

    q = next(data)  # 询问次数
    out: list[str] = []
    for _ in range(q):  # 代表元相同即为亲戚
        c, d = next(data), next(data)
        out.append("Yes" if dsu.same(c, d) else "No")
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()

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/**
 * 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 11:15
 * update_at: 2026-10-13 22:33
 */

#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;

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

const int maxn = 20005;
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() {
    int n, m;
    scanf("%d %d", &n, &m);
    // 初始化：每个人自成一个集合
    init(n);
    // 读入 M 条亲戚关系，逐条合并
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        unite(a, b);
    }
    int q;
    scanf("%d", &q);
    // 每次询问只需比较两人的代表元
    for (int i = 1; i <= q; i++) {
        int c, d;
        scanf("%d %d", &c, &d);
        if (same(c, d))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

【例4-7】亲戚(relation)

目录

题目描述

思路

参考代码