并查集模板

一句话说明

并查集（Union-Find）用于处理动态连通性问题，支持快速合并和查询操作。

💻 模板代码

🎯 经典应用

💡 优化技巧

优化	效果	复杂度
路径压缩	查找时将节点直接连到根	α(n) ≈ O(1)
按秩合并	小树合并到大树	α(n) ≈ O(1)
两者结合	最优	α(n) ≈ O(1)

注：α(n)是阿克曼函数的反函数，增长极慢

适用场景

• ✅ 动态连通性问题
• ✅ 最小生成树（Kruskal算法）
• ✅ 检测环
• ✅ 社交网络分组
• ✅ 等价关系问题

Go 代码

type UnionFind struct {
    parent []int
    rank   []int
    count  int
}
 
func NewUnionFind(n int) *UnionFind {
    parent := make([]int, n)
    rank := make([]int, n)
 
    for i := 0; i < n; i++ {
        parent[i] = i
        rank[i] = 1
    }
 
    return &UnionFind{
        parent: parent,
        rank:   rank,
        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.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }
 
    uf.count--
    return true
}
 
func (uf *UnionFind) Connected(x, y int) bool {
    return uf.Find(x) == uf.Find(y)
}

---

返回：算法模板