并查集：连通性、按秩合并与路径压缩

并查集（Disjoint Set Union）支持两类操作：Find（查根）与 Union（合并集合）。配合按秩合并与路径压缩，均摊复杂度近乎常数。

实现骨架

type DSU struct {
    parent, rank []int
}

func NewDSU(n int) *DSU {
    p := make([]int, n)
    for i := range p {
        p[i] = i
    }
    return &DSU{parent: p, rank: make([]int, n)}
}

func (d *DSU) Find(x int) int {
    if d.parent[x] != x {
        d.parent[x] = d.Find(d.parent[x]) // 路径压缩
    }
    return d.parent[x]
}

func (d *DSU) Union(a, b int) bool {
    ra, rb := d.Find(a), d.Find(b)
    if ra == rb {
        return false
    }
    if d.rank[ra] < d.rank[rb] {
        ra, rb = rb, ra
    }
    d.parent[rb] = ra
    if d.rank[ra] == d.rank[rb] {
        d.rank[ra]++
    }
    return true
}

应用速览

• 判断无向图连通分量 / 环（加边前已同根则成环）。
• Kruskal 最小生成树的边筛选。
• 等价关系的传递闭包式查询（账户合并、岛屿数量变体等）。

小结

结构简单，威力在「动态」。下次遇到不断加关系、反复问是否连通，优先想到并查集，而不是每次 DFS。