并查集模板与复杂度

一、面试常考点

1. 为什么快

路径压缩后，均摊复杂度近似常数。

2. 容易错点

find 必须递归压缩；union 要先找根再合并。

二、细节介绍

1. parent 数组

parent[x] 指向父节点，根节点满足 parent[x] === x。

2. size/rank

尽量把小树挂到大树上，降低树高。

三、示例代码

class DSU {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i)
    this.size = Array(n).fill(1)
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x])
    }
    return this.parent[x]
  }

  union(a, b) {
    let pa = this.find(a)
    let pb = this.find(b)
    if (pa === pb) return false

    if (this.size[pa] < this.size[pb]) [pa, pb] = [pb, pa]
    this.parent[pb] = pa
    this.size[pa] += this.size[pb]
    return true
  }
}

四、常用应用场景

1. 连通分量维护

动态加边场景下快速判连通。

2. 关系归类

账号合并、社交群组聚类。