并查集的经典应用
极难2并查集不止能查朋友圈——经典应用全解析
并查集是什么？它能帮你解决哪些问题？
想象一下：你刚转学到一所新学校，班上有很多同学，你要快速知道谁和谁是朋友（可能通过“朋友的朋友”也是朋友）。如果每个同学都有一张“朋友卡”，卡上写着他的“朋友圈老大”是谁，那么你只要看两个人的老大是不是同一个人，就能判断他们是不是同一个朋友圈的。这就是并查集（Union-Find Set）的核心思想——用一棵树代表一个集合，通过“找根”和“合并”两个操作，快速判断元素是否属于同一集合。
并查集专门用来处理动态连通性问题，比如：
- 社交网络里，两个人是否间接认识？
- 地图上，两块陆地之间有没有路连接？
- 游戏中，两个角色是否在同一个队伍？
- 修路时，还需要修多少条路才能把所有城市连起来？
它的两个核心操作：
- 查找（Find）：找到某个元素所在集合的“根”（即老大）。
- 合并（Union）：把两个集合合并成一个（让一个集合的老大认另一个做老大）。
加上路径压缩（让每个节点直接指向根）和按秩合并（让矮树挂到高树下），几乎能在常数时间内完成操作，效率非常高。
并查集的基本实现（复习）
先回忆一下并查集的模板代码，后面所有应用都基于它。我们以 Python 为例（C++ 类似），每行都加了注释：
class DSU:
def __init__(self, n):
# 初始化：每个节点自己就是一个集合，父节点指向自己
self.parent = list(range(n)) # parent[i] 表示 i 的父节点
self.rank = [0] * n # rank[i] 表示以 i 为根的树的高度（近似）
def find(self, x):
# 查找 x 的根，同时做路径压缩（让 x 直接指向根）
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 递归压缩
return self.parent[x]
def unite(self, x, y):
# 合并 x 和 y 所在的集合
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return # 已经在同一集合，不用合并
# 按秩合并：把高度低的树挂到高度高的树下
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1 # 两棵树高度相等，合并后高度加1
def same(self, x, y):
# 判断 x 和 y 是否在同一集合
return self.find(x) == self.find(y)
常见错误：
- 忘记初始化 parent 数组：每个节点必须初始化为自己，否则 find 会无限递归。
- 路径压缩不彻底：写
find时如果用循环而不是递归，容易只压缩一层。建议用递归写法，或者用 while 循环加两次遍历。- 合并时忘记判断根是否相同：如果不判断就直接改 parent，会导致循环引用。
- 节点编号从 1 开始：很多题目节点从 1 到 n，初始化时要
DSU(n+1)，否则会漏掉节点 n。
经典应用一：统计图的连通分量（有几个“朋友圈”）
场景：班级里有 N 个同学，老师告诉你 M 条“谁和谁是朋友”的信息，问这个班级里有多少个互不相通的“朋友圈”？（假设朋友关系是相互的，且可以传递）
思路：把每个同学看作一个节点，每对朋友关系就合并一次。合并完后，数一数有多少个同学的“老大”是自己（即 parent[i] == i），这个数量就是朋友圈的个数。
生活例子：比如班上有 5 个同学：小明、小红、小刚、小丽、小强。已知：小明和小红是朋友，小红和小刚是朋友，小丽和小强是朋友。那么朋友圈有两个：{小明、小红、小刚} 和 {小丽、小强}。
完整代码（Python）：
# 假设有一个 DSU 类（上面已定义）
def count_friend_circles(n, friendships):
"""
n: 人数（编号从 0 到 n-1）
friendships: 列表，每个元素是 (u, v) 表示 u 和 v 是朋友
返回朋友圈个数
"""
dsu = DSU(n)
for u, v in friendships:
dsu.unite(u, v)
# 统计有多少个不同的根
circles = 0
for i in range(n):
if dsu.find(i) == i: # 如果自己的父节点是自己，说明它是一个集合的根
circles += 1
return circles
# 测试
n = 5
friendships = [(0,1), (1,2), (3,4)]
print(count_friend_circles(n, friendships)) # 输出 2
经典应用二：检测冗余连接（破环）
场景：修路队要修一条连接所有村庄的公路，但施工队不小心多修了一段，导致出现了环路（即有些路是多余的）。现在给你所有道路的清单（按修建顺序），找出最后一条导致环路的道路。
思路：从第一条路开始，每次尝试连接两个村庄。如果两个村庄已经在同一个集合里（说明之前已经有路连通了），那么这条新路就会形成环路，它就是答案。否则，把两个村庄合并。
生活例子：比如有 3 个村庄 A、B、C。先修了 A-B，再修 B-C，此时三个村庄都连通了（集合 {A,B,C}）。如果再修 A-C，会发现 A 和 C 已经在同一个集合里，所以 A-C 是多余的边，会导致环路（三角形）。
C++ 关键代码（保留原有内容）：
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size(); // 题目保证有 n 条边，节点从 1 到 n
DSU dsu(n + 1); // 节点编号从 1 开始，所以要 n+1
for (auto& e : edges) {
int u = e[0], v = e[1];
if (dsu.same(u, v)) return {u, v}; // 如果已经连通，这条边多余
dsu.unite(u, v); // 否则合并
}
return {};
}
常见错误：忘记节点编号从 1 开始，导致数组越界。一定要用 DSU(n+1) 而不是 DSU(n)。
经典应用三：最小生成树（Kruskal 算法）
场景：学校要在几个校区之间修路，每条路有造价，希望用最少的钱把所有校区连通（即最小生成树）。Kruskal 算法就是：先把所有道路按造价从小到大排序，然后依次尝试，只要加入这条路不会形成环路（即两个端点还没连通），就修这条路。
生活例子：有 4 个校区 A、B、C、D，可能的道路及造价：A-B 100 万，A-C 200 万，B-C 50 万，C-D 150 万。排序后先修 B-C（50），再修 A-B（100），然后 C-D（150），此时四个校区都连通了，总造价 300 万。A-C 虽然便宜（200）但会导致环路，被跳过。
核心代码（保留原有内容，补充注释）：
struct Edge { int u, v, w; }; // 边的结构体：起点，终点，权重
bool cmp(Edge a, Edge b) { return a.w < b.w; } // 按权重排序
int kruskal(int n, vector<Edge>& edges) {
sort(edges.begin(), edges.end(), cmp); // 按权重从小到大排序
DSU dsu(n); // 初始化并查集
int totalWeight = 0; // 总造价
for (auto& e : edges) {
if (!dsu.same(e.u, e.v)) { // 如果两个端点不在同一集合
dsu.unite(e.u, e.v); // 合并（修这条路）
totalWeight += e.w; // 累加造价
}
}
return totalWeight; // 返回最小总造价
}
注意：Kruskal 算法要求图是连通的，如果不连通会返回“最小生成森林”的权值和。通常题目保证图连通。
经典应用四：等式方程的可满足性
场景：给你一些关于字母的等式，比如 a == b, b != c, a == c。问这些等式能不能同时成立？答案是：不能，因为由 a==b 和 a==c 可得 b==c，但题目说 b != c。
思路：先处理所有 == 等式，把相等的字母放在同一个集合里。然后检查所有 != 等式，如果发现两个变量已经在同一个集合，就矛盾了。
生活例子：老师给班级分组，说“小明和小红一组，小红和小刚一组，小刚和小明不同组”，这显然矛盾——三人只能在一组或不同组，不能同时满足。
Python 关键代码（保留原有内容，加注释解释）：
def equationsPossible(equations):
dsu = DSU(26) # 26个小写字母，用 0-25 表示 'a'~'z'
for eq in equations:
if eq[1] == '=': # 处理所有相等关系
u = ord(eq[0]) - ord('a') # 将字符转为编号
v = ord(eq[3]) - ord('a')
dsu.unite(u, v)
for eq in equations:
if eq[1] == '!': # 检查所有不等关系
u = ord(eq[0]) - ord('a')
v = ord(eq[3]) - ord('a')
if dsu.same(u, v): # 如果已经相等，冲突
return False
return True
常见错误：只处理了 != 而不先处理 ==，或者顺序颠倒。一定要先做相等合并，再来检查不等。
经典应用五：计算岛屿数量（二维网格中的连通分量）
场景：给你一张地图，用 1 表示陆地，0 表示水，相邻的陆地（上下左右）算同一个岛屿。问有多少个岛屿？虽然用 DFS/BFS 更简单，但并查集也能做，而且能体现“二维坐标映射为一维”的技巧。
思路：把每个陆地格子看作一个节点，编号为 row*col + col。遍历整个网格，对于每个陆地格子，检查它右边和下边的格子，如果也是陆地，就合并它们的编号。最后统计有多少个不同的根（只统计陆地格子的根）。
生活例子：就像在一个游泳池里，一些浮板漂浮着，相邻的浮板连在一起算一个岛。你想知道游泳池里有几个浮板岛。
Python 实现：
def numIslands(grid):
if not grid or not grid[0]:
return 0
rows = len(grid)
cols = len(grid[0])
dsu = DSU(rows * cols) # 最大节点数
water = 0 # 用来统计水的数量（不是必须）
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
idx = r * cols + c # 一维编号
# 检查右边邻居
if c + 1 < cols and grid[r][c+1] == '1':
dsu.unite(idx, r * cols + (c+1))
# 检查下边邻居
if r + 1 < rows and grid[r+1][c] == '1':
dsu.unite(idx, (r+1) * cols + c)
else:
water += 1
# 统计陆地根的数量
roots = set()
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
roots.add(dsu.find(r * cols + c))
return len(roots)
常见错误：忘记将二维坐标转一维时，要注意列数乘的是 cols 而不是 rows。另外，只检查右边和下边即可，不需要检查全部四个方向（因为遍历顺序已经保证不重复）。
应用六：动态连通性（离线反向处理）
场景：给你一个图，一开始所有节点都不连通，然后依次执行“添加边”操作，问你每次操作后有多少个连通分量？或者反过来，给你一个图，依次“删除边”，问每次删除后连通性变化。因为并查集只支持添加边，不支持删除边，怎么办？
技巧：离线反向处理。先把所有操作读进来，然后从后往前处理：删除边变成添加边。例如，题目要求每次删边后查询连通分量个数，我们可以先假设所有边都删除了（即只保留从未被删过的边），然后从最后一次操作往前，每次“删除”变成“添加”，用并查集处理，最后把答案倒序输出。
生活例子：一个网络公司有多个服务器，每天会移除一些连接（故障）。运营想知道每次移除后，还有多少个子网络。我们可以先记录所有移除操作，然后从最后一天往前模拟，把移除的连接“恢复”回来，就能算出每一天的状态。
完整可运行示例：统计朋友圈个数
下面是一个完整的 Python 程序，包含 DSU 类的实现和测试用例。你可以直接复制运行。
# 并查集类（带路径压缩和按秩合并）
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # 父节点数组，初始指向自己
self.rank = [0] * n # 树的高度（近似）
def find(self, x):
# 查找 x 的根，并做路径压缩
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def unite(self, x, y):
# 合并 x 和 y 所在的集合
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
# 按秩合并：将矮树挂到高树下
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
def same(self, x, y):
return self.find(x) == self.find(y)
def count_friend_circles(n, friendships):
"""
n: 人数（编号0~n-1）
friendships: 列表，每个元素是 (u, v)
返回朋友圈个数
"""
dsu = DSU(n)
for u, v in friendships:
dsu.unite(u, v)
circles = 0
for i in range(n):
if dsu.find(i) == i:
circles += 1
return circles
# 测试
if __name__ == "__main__":
# 5个人，朋友关系：0-1, 1-2, 3-4
n = 5
friendships = [(0,1), (1,2), (3,4)]
print("朋友圈个数：", count_friend_circles(n, friendships)) # 输出 2
# 另一个测试：所有人都连通
friendships2 = [(0,1), (1,2), (2,3)]
print("朋友圈个数：", count_friend_circles(4, friendships2)) # 输出 1
总结与扩展
| 应用 | 核心思想 | 生活比喻 |
|---|---|---|
| 连通分量个数 | 合并所有边，数根的数量 | 班级里的朋友圈数 |
| 冗余连接（环检测） | 合并前检查是否已在同一集合 | 修路时发现多余的路 |
| 最小生成树（Kruskal） | 排序边，用并查集避免环路 | 花最少的钱修通所有校区 |
| 等式方程可满足性 | 先合并相等关系，再检查不等关系 | 分组冲突检测 |
| 岛屿数量 | 二维坐标转一维，合并相邻陆地 | 游泳池里的浮板岛 |
| 动态连通性（离线） | 把删除边变成添加边，反向处理 | 网络故障恢复模拟 |
相关知识点指引：
- 带权并查集：除了知道是否连通，还能知道两个元素之间的距离或差值（比如“食物链”问题）。
- 可撤销并查集：支持撤销最近的一次合并操作（用于某些回溯算法）。
- 启发式合并：合并时按集合大小（或高度）优化，保证树高为 O(log n)。
- 并查集在其他算法中的应用：如 Tarjan 的 LCA 算法、离线 RMQ 等。
掌握了并查集，你就拥有了一把处理“关系”的瑞士军刀。在算法竞赛、面试甚至日常编程中，它都能帮你快速解决连通性问题。下次遇到“判断是否连通”、“是否成环”、“有多少个团体”这类问题，不妨第一个想到并查集！
例题精讲
在无向图中使用并查集检测冗余连接时，当处理一条边，若它的两个端点已经属于同一个集合，则这条边被称为：
在Kruskal算法求最小生成树的过程中，每次加入一条边前，使用并查集判断该边的两个顶点是否在同一集合中。若不在同一集合，则加入该边；若在同一集合，则跳过。这种说法正确吗？
下面是一个带路径压缩的并查集查找函数，请补全空缺部分。
int find(int x) {
if (parent[x] != x) {
parent[x] = ___;
}
return parent[x];
}给定一组形如“a==b”的等式和“a!=b”的不等式，使用并查集判断是否冲突（所有等式与不等式能否同时成立）。通常的处理策略是：
下面是并查集的合并函数，实现了按秩合并（秩存储在数组rank中）。请补全空缺部分。
void unionSet(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]) {
___;
} else if (rank[rx] > rank[ry]) {
parent[ry] = rx;
} else {
parent[ry] = rx;
rank[rx]++;
}
}