并查集怎样实现？适合解决什么问题？

简答

有 5 个人，告诉你“0 和 1 是朋友”“1 和 2 是朋友”“3 和 4 是朋友”，朋友的朋友也算一个圈子，问一共有几个圈子、0 和 2 是不是一个圈子。并查集就是专门回答这类“谁和谁属于同一组”问题的结构，名字来自它的两个操作：查找（find）和合并（union）。

实现只要一个 parent 数组。一开始每个人的 parent 指向自己，各自是一组。每组组织成一棵树，树根当作这一组的代表；find(x) 顺着 parent 一路往上找到根，两个元素的根相同就在同一组；union(a, b) 找到两边的根，把一个根挂到另一个根下面，两组就合成一组。

只这样写，树可能退化成一条长链，find 变成 O(n)。两个优化：路径压缩，find 时把路过的节点直接挂到根上，下次一步就到；按大小合并，总是把小树挂到大树下，让树保持矮。两个一起用，每次操作的均摊时间是 O(α(n))，α 是反阿克曼函数，增长极慢，实际可以当成常数。

适合的场景是连通关系只增不减、需要反复查询的问题：朋友圈或岛屿数量、无向图里有没有环、Kruskal 最小生成树。要注意它不支持“拆开”一组，也不能直接回答两点之间的路径是什么，需要路径时还是要用 BFS 或 DFS。

实现和用法

先看 find 里的路径压缩：递归找到根以后，回来的路上把每个节点的 parent 都改成根。

JavaScript

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.count = n; // 当前有几个集合
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // 路径压缩
    }
    return this.parent[x];
  }
  union(a, b) {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA === rootB) return false; // 本来就在一组，没有合并
    if (this.size[rootA] < this.size[rootB]) [rootA, rootB] = [rootB, rootA];
    this.parent[rootB] = rootA; // 小树挂到大树下
    this.size[rootA] += this.size[rootB];
    this.count--;
    return true;
  }
  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
console.log(uf.count); // 2
console.log(uf.connected(0, 2), uf.connected(0, 3)); // true false
console.log(uf.union(2, 0)); // false
uf.union(2, 4);
console.log(uf.count, uf.connected(0, 4)); // 1 true
console.log(new UnionFind(0).count); // 0

union(2, 0) 为什么返回 false？0、1、2 已经通过前两次合并成为一组，两边的根相同，没有发生合并，count 也不减。这个返回值很有用：在无向图里逐条加边时，如果某条边两端已经连通，再加这条边就形成了环。

count 为什么只在真正合并时减 1？一开始 n 个元素是 n 组，每次成功合并两组变一组，所以合并成功的次数就是减少的组数。查询“有几个朋友圈”直接读 count，不用再遍历。

find 用了递归，链很长时会不会爆栈？加了按大小合并以后，树高最多是 log₂n，即使 n 是一百万也只有 20 层左右，不会爆栈。只做路径压缩、不做按大小合并时，第一次 find 之前的链可能很长，这时可以改成循环写法。

用并查集检测环、数岛屿

下面这段用上面的 union 返回值找出无向图中第一条造成环的边。

JavaScript

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }
  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]]; // 隔一层压缩，循环写法不怕深链
      x = this.parent[x];
    }
    return x;
  }
  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return false;
    this.parent[rootB] = rootA;
    return true;
  }
}

function findRedundantEdge(n, edges) {
  const uf = new UnionFind(n);
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return [a, b];
  }
  return null;
}

console.log(JSON.stringify(findRedundantEdge(3, [[0, 1], [0, 2], [1, 2]]))); // [1,2]
console.log(JSON.stringify(findRedundantEdge(4, [[0, 1], [1, 2], [2, 3]]))); // null
console.log(JSON.stringify(findRedundantEdge(2, [[0, 1], [1, 0]]))); // [1,0]
console.log(JSON.stringify(findRedundantEdge(1, []))); // null

[[0, 1], [0, 2], [1, 2]] 为什么是 [1, 2]？前两条边把 0、1、2 连成一组。第三条边的两端 1 和 2 已经连通，再加就绕成一个圈，union 返回 false。

循环版的 find 叫路径减半：每走一步，把当前节点的 parent 改成祖父节点，效果和递归的完全压缩接近，不需要递归栈。

岛屿数量也是同样的套路：把网格里每个格子编号为 行 × 列数 + 列，每块陆地先算一组，再和右边、下边相邻的陆地合并，最后陆地组数就是岛屿数。这题用 DFS 也能做，并查集的优势在于陆地是一块块动态加进来、每加一块都要回答当前岛屿数的场景。

常见追问

路径压缩和按大小合并只用一个行不行？

行，只是保证不同。只用按大小合并，树高不超过 log n，每次 O(log n)；只用路径压缩，均摊也是对数级别。两个一起用才能达到 O(α(n))。面试里写路径压缩通常就够了，被问到时再补上按大小或按秩合并。

并查集能删除元素或拆分集合吗？

标准并查集不支持。合并以后树的结构已经被压缩改写，无法知道原来是哪些边连起来的。需要拆分时，常见做法是把操作反过来：先把最终状态建好，倒着处理“删除”，就变成了“添加”。