常见算法题型之并查集。附模板题+两道真题

依然鸣

712人浏览 · 2026-08-06 10:26:55

依然鸣 · 2026-08-06 10:26:55 发布

并查集讲解，附模板题，两道真题（PTA，蓝桥杯）

并查集是一种专门处理不相交集合的动态合并与查询问题的数据结构，核心解决「两个元素是否属于同一集合」「合并两个集合」「统计连通分量数量」等连通性问题。优化后单次操作均摊时间复杂度接近 (O(1))，是算法竞赛中最高频的数据结构之一。

一、核心原理

并查集通过父节点数组表示集合关系：每个元素有一个父节点，集合的代表元是树的根节点（父节点指向自身），只要两个元素的根节点相同，就说明它们属于同一个集合。

它只包含两个核心操作：

查找（Find）：找到元素所属集合的根节点
合并（Union）：将两个不相交的集合合并为一个

二、基础实现

1. 初始化

初始状态下每个元素独立成一个集合，父节点指向自己。

const int N = 1e5 + 10;
int p[N]; // 父节点数组
// 初始化：编号从1到n
for(int i = 1; i <= n; i++)
    p[i] = i;

2. 基础查找

递归向上遍历父节点，直到找到根节点。

int find(int x) {
    if(p[x] != x) return find(p[x]);
    return p[x];
}

3. 基础合并

找到两个元素的根节点，若根不同则将一棵树挂到另一棵树上。

void unite(int a, int b) {
    int fa = find(a), fb = find(b);
    if(fa != fb)
        p[fa] = fb;
}

三、优化策略

基础版并查集在极端情况下会退化成链表，查找效率骤降。通过优化可以让操作效率接近常数。

路径压缩

核心思想：在查找过程中，把路径上所有节点的父节点直接指向根节点，让树结构扁平化，后续查找可以一步直达根节点。

实现只需要修改一行代码：

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]); // 路径压缩：当前节点直接连到根
    return p[x];
}

这是并查集最核心的优化，几乎零成本，做题时必加。

说明：仅路径压缩就足以应对绝大多数题目；

四、模板题：AcWing 836. 合并集合

836. 合并集合 - AcWing题库

题目描述

一共有 $n$ 个数，编号 $\sim n$ ，初始每个数各在一个集合中。
共 $m$ 个操作，分为两种：

M a b：合并 $a$ 和 $b$ 所在的集合，已在同一集合则忽略
Q a b：询问 $a$ 和 $b$ 是否在同一集合中

解题思路

并查集纯模板题，直接实现带路径压缩的并查集，按指令执行对应操作即可。

完整代码

#include<iostream>
using namespace std;

const int N = 1e5 + 9;
int n, m, p[N];

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;
    
    while(m--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if(op == 'M') {
            p[find(a)] = find(b);
        } else {
            cout << (find(a) == find(b) ? "Yes\n" : "No\n");
        }
    }
    return 0;
}

五、真题实战1：部落问题（PTA L2-024）

https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7

题目描述

社区中有多个小圈子，朋友的朋友属于同一个部落。统计互不相交的部落总数，以及查询任意两人是否同属一个部落。

解题思路

同一个小圈子的人属于同一部落，将圈子内所有元素合并到同一集合
用 set 统计所有出现过的编号，得到总人数
统计所有出现过的人的根节点数量，即为部落总数
查询时直接判断两人根节点是否相同

完整代码

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

const int N = 1e4 + 9;
int p[N];
set<int> people; // 记录所有出现过的人

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n;
    cin >> n;
    for(int i = 1; i < N; i++) p[i] = i;
    
    for(int i = 0; i < n; i++) {
        int k, first;
        cin >> k >> first;
        people.insert(first);
        int root = find(first);
        for(int j = 1; j < k; j++) {
            int y;
            cin >> y;
            people.insert(y);
            p[find(y)] = root;
        }
    }
    
    // 统计部落数量
    set<int> tribes;
    for(auto x : people) tribes.insert(find(x));
    cout << people.size() << ' ' << tribes.size() << '\n';
    
    int q;
    cin >> q;
    while(q--) {
        int a, b;
        cin >> a >> b;
        cout << (find(a) == find(b) ? "Y\n" : "N\n");
    }
    return 0;
}

六、真题实战2：P16237 [蓝桥杯 2026 省 B] 应急布线

[P16237 蓝桥杯 2026 省 B] 应急布线 - 洛谷

题目描述

$N$ 台计算机通过 $M$ 条残存网线连接，分裂为多个连通区域。添加最少的应急跳线让全网连通，且在跳线总数最少的前提下，让单台计算机接入的跳线数量的最大值尽可能小。
输出最少跳线数、单台最大跳线数的最小值。

解题思路

第一问：最少跳线数

经典结论： $k$ 个连通块连成整体，最少需要 $k - 1$ 条跳线。用并查集统计连通块总数 cnt，答案即为 cnt-1。

第二问：单台最大跳线数的最小值

分类讨论：

cnt == 1：无需跳线，答案为 0
cnt == 2：只需 1 条跳线，最大值为 1
cnt >= 3：将连通块分为两类
- 孤立点（大小为1的连通块）：数量 c1
- 非孤立连通块（大小≥2）：数量 c2 = cnt - c1，总点数 c3 = n - c1
先将非孤立连通块连成链，消耗 c2-1 条跳线，占用 $2\times(c2-1)$ 个接口，剩余可用接口 c4 = c3 - 2*(c2-1)。
- 若 c4 >= c1：所有孤立点可直接接在非孤立块上，每点仅1条线，最大值为1
- 若 c4 < c1：部分孤立点需要串联，会出现接2条线的节点，最大值为2

完整代码

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

const int N = 1e5 + 9;
int p[N], sz[N];

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        sz[i] = 1;
    }
    
    while(m--) {
        int u, v;
        cin >> u >> v;
        int fu = find(u), fv = find(v);
        if(fu != fv) {
            p[fu] = fv;
            sz[fv] += sz[fu];
        }
    }
    
    int cnt = 0, c1 = 0;
    for(int i = 1; i <= n; i++) {
        if(find(i) == i) {
            cnt++;
            if(sz[i] == 1) c1++;
        }
    }
    
    if(cnt == 1) {
        cout << "0 0";
        return 0;
    }
    
    int ans1 = cnt - 1;
    cout << ans1 << ' ';
    
    if(cnt == 2) {
        cout << 1;
        return 0;
    }
    
    int c2 = cnt - c1;
    int c3 = n - c1;
    int c4 = c3 - 2 * (c2 - 1);
    cout << (c4 >= c1 ? 1 : 2);
    
    return 0;
}