亲戚 - 题目列表

题意

给出 n 个人之间的 m 条亲戚关系。亲戚关系可以传递，回答 p 次询问：两个人是否属于同一个亲戚群体。

思路

把每个人看成一个集合。读到关系 (a,b) 时合并两人的集合；询问时比较两人的代表元：

代表元相同，说明存在一条关系链把两人连在一起，输出 Yes；
代表元不同，输出 No。

代码同时使用路径压缩和按集合大小合并，使并查集操作的均摊代价接近常数。

Python 知识

parent = list(range(n + 1)) 简洁地建立“每个人最初以自己为根”的数组。
a, b = find(a), find(b) 用解包同时取得两个代表元。
"Yes" if 条件 else "No" 适合表达二选一答案，再用列表收集后一次输出。
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：批量读入和字符串输出。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：避免深递归，使用循环版 find。

代码

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
41import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m, q = data[:3]
    parent = list(range(n + 1))
    size = [1] * (n + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a, b = find(a), find(b)
        if a == b:
            return
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]

    pos = 3
    for _ in range(m):
        union(data[pos], data[pos + 1])
        pos += 2

    answer = []
    for _ in range(q):
        answer.append("Yes" if find(data[pos]) == find(data[pos + 1]) else "No")
        pos += 2
    print("\n".join(answer))


if __name__ == "__main__":
    main()

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/**
 * P1551 亲戚
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;

int fa[MAXN], sz[MAXN];

int find(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]]; // 路径压缩
        x = fa[x];
    }
    return x;
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y); // 按大小合并
    fa[y] = x;
    sz[x] += sz[y];
}

int main() {
    int n, m, p;
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1;
    for (int i = 1; i <= m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        unite(a, b);
    }
    for (int i = 1; i <= p; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        puts(find(a) == find(b) ? "Yes" : "No");
    }
    return 0;
}

复杂度

共有 m+p 次并查集操作，时间复杂度为 $O((m+p)\alpha(n))$ ，空间复杂度为 $O(n)$ 。

总结

“关系可以传递，反复询问是否属于同一组”是并查集的直接使用场景。查询的关键不是保存完整关系链，而是比较最终代表元。

亲戚

目录

题意

思路

Python 知识

代码

复杂度

总结