1️⃣ 并查集的本质

并查集是一种用于 动态维护不相交集合（Disjoint Sets） 的数据结构，核心目的是快速判断元素是否属于同一个集合，以及将两个集合合并。

• 用途：

  • 判断图中两个节点是否连通
  • 求连通分量个数
  • 处理网络、社交关系、群体合并等问题

• 核心思想：

  • 每个集合有一个“代表元素”（root）
  • 每个元素只保存指向父节点的指针
  • 查找元素的根节点可以判断是否属于同一个集合
  • 合并两个集合就是把一个集合的根挂到另一个根上

---

2️⃣ 并查集的核心操作

2.1 初始化

int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;

• 每个节点自己是自己的根，表示初始 n 个独立集合。

2.2 查找（Find）

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

• 目的：找到 x 所在集合的根节点
• 路径压缩：将访问路径上的所有节点直接挂到根节点下，优化后续查询

2.3 合并（Union）

void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootX] = rootY; // 合并集合
    }
}

• 把 x 所在集合和 y 所在集合合并为一个集合
• 可以选择按秩合并（rank）进一步优化

2.4 判断是否在同一集合（可选）

boolean connected(int x, int y) {
    return find(x) == find(y);
}

3️⃣ 并查集复杂度分析

操作	复杂度
初始化	O(n)
单次查找/合并	O(α(n))，α(n) 为反阿克曼函数，非常小，可视作常数
n 次操作	O(n α(n))，近似 O(n)

注意：这是经过 路径压缩 + 按秩合并 的最优复杂度。

5️⃣ 总结

• 并查集 = 动态维护不相交集合 + 快速合并

• 核心操作：Find（查找根） + Union（合并集合）

• 优化技巧：

  • 路径压缩（递归或迭代）
  • 按秩合并（rank）或按大小合并（size）

• 适用场景：

  • 连通性判断
  • 社交网络群体合并
  • Kruskal 最小生成树
  • 省份、朋友圈、岛屿数量等问题

并查集这个一般用于解决图的问题吗？还是还有其他的应用场景

并查集（Union-Find）虽然最常见于 图的连通性问题，但它的应用远不止图论，核心是 维护动态的“不相交集合”关系”。

1️⃣ 图论相关应用（最经典）

1. 连通性问题

   • 判断两个节点是否在同一个连通分量
   • 求图中连通分量的数量（例如 LC547 省份问题）

2. Kruskal 最小生成树

   • 遍历边，判断两个端点是否属于同一个集合，避免形成环
   • 用 Union-Find 合并集合，保证生成树不成环

3. 圈 / 环检测

   • 在无向图或有向图中检测是否存在环

4. 网络/社交关系

   • 判断两个人是否在同一个社交群体
   • 朋友圈问题（如 LC547 变体）

---

2️⃣ 非图论的应用（更广泛）

1. 动态连通性集合

   • 任何需要维护元素分组的场景，只要需要频繁合并集合并快速查询：

     • 例如学生分组、团队合并、任务归类等

2. 字符串或集合等归并问题

   • LC721 “账户合并”：把多个邮箱合并到同一个账户
   • LC839 “相似字符串群”：相似字符串归类

3. 区域 / 集群 / 连通块问题

   • 网格 / 矩阵中岛屿数量问题（LC200, LC695）
   • 任何二维或多维网格的连通区域计算，都可以用 Union-Find

4. 动态集合判断

   • 游戏或模拟中，维护不同势力、联盟的合并与判断
   • 动态资源管理，例如服务器分组或网络拓扑合并

5. 优化搜索

   • 路径压缩 + 按秩合并可以加速一些重复查询问题，例如找最小/最大组、合并后查询属性等

---

🔑 核心思想

不论场景如何变化，本质都是：动态维护不相交集合，并支持快速合并和查询。

• **“图问题”**只是最直观的例子
• **“集合归并/分组问题”**是更抽象的本质应用

我要如何记忆并查集呢？

要记忆并查集（Union-Find），核心是抓住它的 本质、操作和优化技巧，而不是死记每一行代码。

我给你总结一个 高效记忆法，用“图+故事+口诀”的方式，容易记住又能理解。

---

1️⃣ 理解本质（记忆核心）

核心概念：

并查集 = 动态维护不相交集合 + 快速合并 + 快速查找代表元素（根节点）

用一句话记忆：

“每个元素都有一个根，想问关系就找根，想合并就让根连起来。”

画面化记忆：

• 每个元素像一棵树的节点
• 根节点是集合的代表
• 合并集合 = 把一棵树挂到另一棵树的根下
• 查询两个元素是否在同一集合 = 找它们的根

---

2️⃣ 核心操作（口诀）

操作	功能	记忆口诀
find(x)	找根	“找根就压扁路”（路径压缩）
union(x, y)	合并	“把两棵树连起来”（按秩或按大小）
connected(x, y)	判断是否同集合	“看根是不是同一个”

口诀串起来：

“找根就压扁路，把两棵树连起来，看根是不是同一个。”

---

3️⃣ 优化技巧（记忆辅助）

• 路径压缩（Path Compression）

  • 找根时，把沿途节点都挂到根节点下
  • 联想：像“把弯曲的路线拉直”，下一次找根更快

• 按秩/大小合并（Union by Rank/Size）

  • 总是把矮树挂到高树下
  • 联想：轻的挂到重的上面，避免树高增长

口诀：

“拉直路线、轻挂重枝”

---

4️⃣ 应用场景（便于联想记忆）

• 图论类：省份、连通分量、最小生成树、环检测
• 非图论类：账户合并、字符串群分组、岛屿数量、联盟/团队合并

联想故事：

想象你在学校里，每个学生最初都是独立的小团体，你可以让两个小团体合并，或者问两个人是不是同一个团体，树形结构帮你快速回答。

---

5️⃣ 练习记忆方法

1. 画图：画几颗小树，模拟 union 和 find，记住路径压缩的变化
2. 写口诀：每天复述
3. 手写代码：不看答案，写出 find + union
4. 结合题目：LC547、LC200、LC721，做题时把并查集用上，加深印象

---

💡 总结一句话记忆并查集：

“每个元素找根，想问关系找根，想合并挂根，路径压缩轻松快。”