07 并查集与最小生成树

userId_undefined
吴老师
7月全勤卷王8月全勤卷王10月全勤卷王倔强青铜时间刺客空间掌握者

2026-06-30 18:57:00

发布于：广东

2阅读
0回复
0点赞

07 并查集与最小生成树

一、本阶段目标

学完本阶段，学生要能做到：

1. 理解并查集解决集合合并与连通性查询。
2. 掌握 find、merge、路径压缩。
3. 会用并查集判断两个点是否在同一连通块。
4. 理解最小生成树问题。
5. 掌握 Kruskal 算法。

二、并查集解决什么问题

并查集适合处理：

合并两个集合
查询两个元素是否属于同一集合
动态加边后的连通性

常见题面：

亲戚关系
朋友关系
帮派关系
城市连通
村村通
合并学校社团
判断两点是否连通

三、并查集的核心思想

每个集合选一个代表，叫根节点。

find(x)：找到 x 所在集合的代表
merge(a,b)：把 a 和 b 所在集合合并

如果：

find(a) == find(b)

说明 a 和 b 在同一个集合。

四、并查集模板

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

const int N = 100005;
int f[N];

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

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

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) f[i] = i;

    while (m--) {
        char op;
        int a, b;
        cin >> op >> a >> b;

        if (op == 'M') {
            merge(a, b);
        } else if (op == 'Q') {
            cout << (find(a) == find(b) ? "Yes" : "No") << '\n';
        }
    }

    return 0;
}

五、路径压缩

没有路径压缩时，find 可能一层一层往上找，很慢。

路径压缩：

return f[x] = find(f[x]);

含义：

找到根以后，顺便把 x 直接挂到根上。

这样以后再查 x 就很快。

六、按秩合并/按大小合并

基础阶段只用路径压缩就够。

如果想更稳，可以按集合大小合并：

int siz[N];

void merge(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa == fb) return;
    if (siz[fa] > siz[fb]) swap(fa, fb);
    f[fa] = fb;
    siz[fb] += siz[fa];
}

初始化：

for (int i = 1; i <= n; i++) {
    f[i] = i;
    siz[i] = 1;
}

七、并查集常见错误

错误 后果 修正
忘记初始化 f[i]=i find 错误 每组数据初始化
合并时不用 find 只改了一个点，不是集合 合并根节点
查询时直接比较 f[a]==f[b] 路径未压缩时可能错 比较 find(a)==find(b)
并查集用于删边 不适合 普通并查集只支持合并，不支持删除
多组数据不清空 数据污染 重置 f、siz

八、最小生成树问题

给一个无向连通带权图，要选一些边，使得：

1. 所有点连通。
2. 没有环。
3. 边权总和最小。

这样的边集叫最小生成树。

如果 n 个点连通且没有环，一定有：

n - 1 条边

常见题面：

修路
铺网线
连接所有村庄
通信网络最小成本

九、Kruskal 算法

Kruskal 思想：

1. 把所有边按权值从小到大排序。
2. 依次考虑每条边。
3. 如果这条边连接了两个不同集合，就选它。
4. 如果两端已经连通，选它会成环，跳过。
5. 选到 n-1 条边结束。

为什么要用并查集？

快速判断一条边的两个端点是否已经连通。

十、Kruskal 模板

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

struct Edge {
    int u, v, w;
    bool operator < (const Edge& other) const {
        return w < other.w;
    }
};

const int N = 100005;
int f[N];
vector<Edge> edges;

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

bool merge(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa == fb) return false;
    f[fa] = fb;
    return true;
}

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) f[i] = i;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }

    sort(edges.begin(), edges.end());

    long long ans = 0;
    int cnt = 0;

    for (auto e : edges) {
        if (merge(e.u, e.v)) {
            ans += e.w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }

    if (cnt == n - 1) cout << ans << '\n';
    else cout << "orz\n"; // 图不连通

    return 0;
}

十一、Kruskal 的复杂度

主要耗时是排序：

O(m log m)

其中 m 是边数。

十二、最小生成树变式

1. 图不连通

如果选不到 n-1 条边，说明无法连接所有点。

2. 最小瓶颈路

有些题问从 A 到 B 的路径上最大边权尽量小。

可以：

按边权排序，用并查集不断加边，直到 A 和 B 连通。
当前边权就是答案。

3. 分成 k 个连通块

如果要把 n 个点连成 k 个块，Kruskal 只需要选：

n - k 条边

十三、课堂例题

例题 1：亲戚关系

合并亲戚关系，查询两个人是否属于同一家族。

模型：并查集

例题 2：修路最小成本

把所有村庄连起来，费用最小。

模型：最小生成树
算法：Kruskal

例题 3：营救路径风险

道路有危险值，希望路径上最大危险值最小。

模型：最小瓶颈路
做法：排序加边，直到起点终点连通

十四、练习题

题号 题名 训练点 建议
P3367 并查集 模板 必做
P1551 亲戚 并查集入门 必做
P1536 村村通 连通块 + 并查集 必做
P3366 最小生成树 Kruskal 模板 必做
P1195 口袋的天空 生成 k 个连通块 提高
P1396 营救 最小瓶颈路 提高
P1111 修复公路 按时间加边 提高
P1546 最短网络 MST 入门 选做

链接：

https://www.luogu.com.cn/problem/P3367
https://www.luogu.com.cn/problem/P1551
https://www.luogu.com.cn/problem/P1536
https://www.luogu.com.cn/problem/P3366
https://www.luogu.com.cn/problem/P1195
https://www.luogu.com.cn/problem/P1396
https://www.luogu.com.cn/problem/P1111
https://www.luogu.com.cn/problem/P1546

十五、本阶段作业

  1. 手写并查集模板。
  2. 解释路径压缩的作用。
  3. 完成 P3367、P1551。
  4. 手写 Kruskal 模板。
  5. 完成 P3366。
  6. 选做 P1195，解释为什么选 n-k 条边。

十六、本阶段小结

并查集关键词：

合并
同组
连通
动态加边

最小生成树关键词：

所有点连通
总代价最小
无向图
n-1 条边
Kruskal + 并查集
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论