当前位置：首页 > news >正文

20251206 - 并查集总结

news 2026/5/26 14:18:06

并查集介绍

正常情况下我们维护一棵树，存储了每条边、每个点的具体信息，因为我们需要知道一棵树的完整面貌。

但是如果我们只想知道这棵树，或者说这个森林的连通情况，就完全没必要这么麻烦了。

假设我们只存储每个节点的父亲节点 \(fa_u\)，那么该如何判断 \(u\) 和 \(v\) 是否处在同一棵树中呢？很简单，只需要沿着 \(u\) 和 \(v\) 的父亲 \(fa\) 不断往上爬找到根，判断根是否相等即可。

合并 \(u\) 和 \(v\) 的时候，找到它们分别的根 \(fu\) 和 \(fv\)，让 \(fa_{fv} = fu\) 即可。

这就是并查集。

需要一个 Find_Father 函数去找节点对应的根节点，这边为了简写就简称 FF 函数了。以及需要一个 Merge 函数用作合并。

朴素实现的代码如下：

int FF(int u){if(fa[u]==u)return u;return FF(fa[u]);
}
void Merge(int u,int v){int fu=FF(u),fv=FF(v);if(fu!=fv)fa[fv]=fu;return;
}

时间复杂度是多少呢？发现当最坏情况下，树呈链状，一次 FF 可能就需要 \(O(n)\) 的时间。如果需要连 \(m\) 条边，时间复杂度 \(O(nm)\)，太差了。这就完全失去并查集的意义了，跑 BFS 都比这快。

刚才我们发现并查集的朴素实现，时间复杂度极差。需要对它进行优化。

一般有以下两种优化方案：

路径压缩
- 由于在并查集中，我们只关心连通情况，其实并不关心你具体的父节点究竟是谁，也就是不关心树的具体形态。
- 那么我们完全可以考虑在查询根节点的同时，把路径上的节点的父节点修改成根节点。
- 这样就可以大大加快后续的查询速度，均摊每次操作时间复杂度 \(O(\log n)\)。
- 代码实现：
```
int FF(int u){if(fa[u]==u)return u;return fa[u]=FF(fa[u]);
}
/*
可以使用三目运算符压行
int FF(int u){return (fa[u]=u?u:fa[u]=FF(fa[u]));}
*/
```
- 一般的题目只需要用到这个优化就可以过得去了。
启发式合并
- 在合并时，我们考虑把节点数量较少的树的根节点合并到节点数量较多的树的根节点下面。
- 也可以根据树的深度来合并。
- 这样就能使新树的每个节点到根节点的总距离尽可能小。
- 这个优化会大大提升速度，均摊一次操作 \(O(\alpha(n))\)，其中 \(\alpha(n)\) 可以看做一个不超过 \(4\) 的小常数，几乎可以忽略不计。
- 代码实现：
```
void Merge(int u,int v){int fu=FF(u),fv=FF(v);if(fu==fv)return;if(sz[fv]>sz[fu])swap(fu,fv);fa[fv]=fu,sz[fu]+=sz[fv];return;
}
```
- 启发式合并是一个很通用的优化方法，它的作用不仅在于并查集。