并查集三部曲：集、查、并的深度打磨

并查集（Union-Find）在江湖上被戏称为“江湖门派算法”。它的核心逻辑可以用三个字概括：集、查、并。

1. 算法心法：三字诀

• 集 (Set)：初始化阶段。每个人一开始都是自成一派，自己的“上级”就是自己。
• 查 (Find)：寻找门派老大。最重要的优化是路径压缩 (Path Compression)——既然都要找老大，不如直接把所有人的上级都改成老大，这样下次查的时候就是 $O(1)$。
• 并 (Union)：合并两个门派。进阶优化是按秩合并 (Union by Rank)——让小门派去挂在大门派名下，防止树结构变得过深。

2. 什么时候掏出并查集？

当你看到题目中出现“连通”、“朋友圈”、“岛屿数量”、“网络延迟”等词汇，且涉及动态合并过程时，立刻想到并查集。

• 🎯 [LeetCode 547. 省份数量]：典型的朋友圈问题。
• 🎯 [LeetCode 200. 岛屿数量]：虽然可以用 DFS，但并查集在处理大规模动态数据时更具优势。
• 🎯 [Kruskal 算法]：求最小生成树的核心逻辑就是并查集。

3. 终极工业级模板（JavaScript/TypeScript）

这段模板我反复练习并背诵，它可以直接应对 90% 的连通性题目：

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.count = n; // 记录当前连通分量的数量
  }

  // “查”：带路径压缩
  find(i) {
    if (this.parent[i] === i) return i;
    // 递归查找并将路径上的所有节点直接挂在根节点下
    this.parent[i] = this.find(this.parent[i]);
    return this.parent[i];
  }

  // “并”：将两个节点连通
  union(i, j) {
    let rootI = this.find(i);
    let rootJ = this.find(j);
    if (rootI !== rootJ) {
      this.parent[rootI] = rootJ;
      this.count--; // 每合并一次，独立的门派就少一个
    }
  }
}

4. 背诵口诀

1. 先初始化：parent[i] = i，大家都是光杆司令。
2. 查要压缩：find 的时候顺手把 parent 更新了。
3. 并要断根：合并的是 find(i) 和 find(j) 的结果，千万别合并 i 和 j 本身。

锻造感悟： 并查集的精髓在于“降维打击”。通过路径压缩，我们将复杂的树状结构拍扁。在现实开发中，这种“扁平化管理”的思想同样能极大提高复杂逻辑的索引效率。