并查集
一句话说明
并查集专门解决“谁和谁属于同一组”这一类动态连通性问题，核心只有两件事：找根、合并根。
先把并查集想成“帮派系统”
开始时每个人自成一派：
{0} {1} {2} {3} {4} {5}执行：
union(0, 1)
union(2, 3)
union(0, 2)最后会得到：
{0, 1, 2, 3} {4} {5}所以并查集最擅长的问题就是：
- 两个点是否连通
- 合并两个集合
- 动态维护连通块数量
Go 代码：标准模板
这版包含两个关键优化：
- 路径压缩
- 按大小合并
type UnionFind struct {
parent []int
size []int
count int
}
func NewUnionFind(n int) *UnionFind {
parent := make([]int, n)
size := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
size[i] = 1
}
return &UnionFind{
parent: parent,
size: size,
count: n,
}
}
func (uf *UnionFind) Find(x int) int {
if uf.parent[x] != x {
uf.parent[x] = uf.Find(uf.parent[x])
}
return uf.parent[x]
}
func (uf *UnionFind) Union(x, y int) bool {
rootX := uf.Find(x)
rootY := uf.Find(y)
if rootX == rootY {
return false
}
if uf.size[rootX] < uf.size[rootY] {
rootX, rootY = rootY, rootX
}
uf.parent[rootY] = rootX
uf.size[rootX] += uf.size[rootY]
uf.count--
return true
}
func (uf *UnionFind) Connected(x, y int) bool {
return uf.Find(x) == uf.Find(y)
}
func (uf *UnionFind) Count() int {
return uf.count
}
func (uf *UnionFind) Size(x int) int {
return uf.size[uf.Find(x)]
}为什么路径压缩这么重要
如果不压缩，树可能长这样：
1 -> 2 -> 3 -> 4 -> 5每次 find(1) 都要一路爬到 5。
路径压缩后，会变成：
1
\
5
/
2 3 4也就是：
- 查一次，顺手把路径上的点全挂到根上
- 后面再查就快很多
为什么按大小合并
如果总把大树挂到小树下面，树会越来越高。
按大小或按秩合并的目标就是：
- 尽量别让树长得太深
这和路径压缩配合后，单次操作复杂度可以看成近似 O(1)。
Go 代码：判断无向图是否有环
func hasCycle(n int, edges [][]int) bool {
uf := NewUnionFind(n)
for _, edge := range edges {
u, v := edge[0], edge[1]
if uf.Connected(u, v) {
return true
}
uf.Union(u, v)
}
return false
}思路很直接：
- 如果一条边连接的两个点已经连通，再连一次就会成环。
Go 代码：省份数量
func findCircleNum(isConnected [][]int) int {
n := len(isConnected)
uf := NewUnionFind(n)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if isConnected[i][j] == 1 {
uf.Union(i, j)
}
}
}
return uf.Count()
}Go 代码：冗余连接
func findRedundantConnection(edges [][]int) []int {
uf := NewUnionFind(len(edges) + 1)
for _, edge := range edges {
u, v := edge[0], edge[1]
if uf.Connected(u, v) {
return []int{u, v}
}
uf.Union(u, v)
}
return nil
}Go 代码：等式方程的可满足性
func equationsPossible(equations []string) bool {
uf := NewUnionFind(26)
for _, eq := range equations {
if eq[1] == '=' {
x := int(eq[0] - 'a')
y := int(eq[3] - 'a')
uf.Union(x, y)
}
}
for _, eq := range equations {
if eq[1] == '!' {
x := int(eq[0] - 'a')
y := int(eq[3] - 'a')
if uf.Connected(x, y) {
return false
}
}
}
return true
}并查集最适合的题型
- 连通性判断
- 连通块计数
- 无向图判环
- Kruskal 最小生成树
- 等价类合并
不适合的题型
- 需要删除边
- 需要具体路径
- 有向图强连通问题
- 想知道某个集合里都有哪些元素
易错点
union的对象应该是两个根，不是原始节点直接乱改父亲。- 下标是否从
0还是1开始要统一。 - 题目如果节点编号从
1开始，通常要多开一个位置。 - 并查集擅长“是否连通”，不擅长“怎么连过去”。