并查集

讲解

并查集（Union-Find / DSU）只回答一个问题：两个元素在同一个集合里吗？它支持两个操作——find(x) 返回 x 所在集合的代表元（根），union(a, b) 把两个集合合并。它的舞台是「动态连通性」：边一条条加入，随时查询两点是否连通、图里有几个连通分量、新加的边是否构成环。DFS/BFS 也能数连通分量，但那是「图给全了算一次」；边流式到达、需要反复查询的场景，并查集才是正解。

朴素并查集用 parent 数组表示一片森林：每个节点存父亲，根的父亲是自己。find 沿父亲链走到根，union 把一个根挂到另一个根下。问题是链可能退化成一条长链，find 变成 O(n)。两个优化让它快得近乎常数。路径压缩：find 路上把沿途节点直接挂到根（或隔代挂），下次查找一步到位。按秩合并：union 时把矮树挂到高树下，避免树高无谓增长。两者合力，单次操作的均摊复杂度是 O(α(n))——反阿克曼函数，对任何现实规模都可视为常数。

并查集的典型题型三连。判环 / 冗余连接：逐条加边，union 返回 false（两端已连通）时，这条边就是多余的。连通分量计数：维护 count，初始为 n，每成功 union 一次减一。网格上的连通（岛屿数量的并查集解法）：把每个陆格子映射成一维编号，向右、向上与邻居 union，最后数陆格子的不同根个数——和 BFS 解法对照看，能体会两种「连通性」思路的异同。

示例

带路径压缩 + 按秩合并的完整实现，然后两道题：冗余连接（找成环边）、岛屿数量的并查集解法：

import assert from 'node:assert/strict';

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(1);
    this.count = n; // 连通分量数
  }
  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 ra = this.find(a);
    const rb = this.find(b);
    if (ra === rb) return false; // 已连通：这条边冗余
    if (this.rank[ra] < this.rank[rb]) {
      this.parent[ra] = rb;
    } else if (this.rank[ra] > this.rank[rb]) {
      this.parent[rb] = ra;
    } else {
      this.parent[rb] = ra;
      this.rank[ra]++;
    }
    this.count--;
    return true;
  }
  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

function findRedundantConnection(edges) {
  const uf = new UnionFind(edges.length + 1); // 节点编号从 1 开始
  for (const [a, b] of edges) {
    if (!uf.union(a, b)) return [a, b];
  }
  return [];
}

// 岛屿数量的并查集解法：陆格子向右、向上与邻居合并
function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const uf = new UnionFind(rows * cols);
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '0') continue;
      const id = r * cols + c;
      if (r > 0 && grid[r - 1][c] === '1') uf.union(id, id - cols);
      if (c > 0 && grid[r][c - 1] === '1') uf.union(id, id - 1);
    }
  }
  const roots = new Set();
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') roots.add(uf.find(r * cols + c));
    }
  }
  return roots.size;
}

const uf = new UnionFind(5);
assert.strictEqual(uf.count, 5);
assert.strictEqual(uf.union(0, 1), true);
assert.strictEqual(uf.union(1, 2), true);
assert.strictEqual(uf.union(0, 2), false); // 已连通，构成环
assert.strictEqual(uf.connected(0, 2), true);
assert.strictEqual(uf.connected(0, 3), false);
assert.strictEqual(uf.count, 3);

assert.deepStrictEqual(
  findRedundantConnection([
    [1, 2],
    [1, 3],
    [2, 3],
  ]),
  [2, 3],
);

const grid = [
  ['1', '1', '0'],
  ['1', '0', '0'],
  ['0', '0', '1'],
];
assert.strictEqual(numIslands(grid), 2);

console.log('并查集示例全部通过');

数岛屿时只与「上、左」两个邻居 union 是个小巧思：每条边恰好在较后处理的端点处被合并一次，避免重复劳动；数根时收集陆格子的根到 Set 里，去重即得岛数。

常见坑

• union 时不先 find 就直接挂：必须挂根到根，挂到非根节点上会把树接错，连通性判断全乱。
• 只加路径压缩就宣称 O(1)：单用路径压缩是 O(log n) 级别，配合按秩合并才是近乎常数的 α(n)——面试被追问时要答得全。
• count 的语义记错：count 在成功 union 时减一；union 返回 false（本就连通）时不减。
• 编号映射混乱：网格转一维编号用 r * cols + c，行列乘错方向会把不同格子映射到同一编号。
• find 忘记路径压缩的写法细节：隔代压缩 parent[x] = parent[parent[x]] 简单有效；递归全压缩更彻底但写法稍繁，两者都对，别混着写半吊子版本。

小结

并查集 = find（找根）+ union（合并根），路径压缩 + 按秩合并做到近乎 O(1)；动态连通性、冗余边、分量计数是它的三连场景。下一章回到数组：前缀和与差分。