🔑 并查集为什么适合“连通性”问题，却不适合“路径”问题
并查集（Union-Find / Disjoint Set Union, DSU）解决的核心不是“怎么走”，而是“是不是一伙的”。当图上的边会不断加入，而你反复想问两个点当前是否连通时，如果每次都重新跑一次 BFS 或 DFS，代价会越来越高；并查集的设计思路更直接：它不关心整条路径长什么样，只维护每个点属于哪个集合。
它之所以高效，关键在两个优化。一个是 path compression：每次
但并查集的“快”，是靠主动丢弃大量路径细节换来的。它只告诉你两个点最后是不是在同一个集合里，却不会保留“经过了哪些边”“路径长度是多少”“谁是父谁是子”的真实图结构。所以它特别适合回答 connectivity，却不适合回答 shortest path、具体路径恢复、拓扑先后关系 这类问题。很多人一看到图连起来了，就下意识想用并查集一路做到底，结果在需要距离、方向、层次的时候才发现信息早就没被保存下来。
真正容易踩坑的地方，恰恰在这里：你以为自己维护的是一棵“树”，其实维护的只是一个“集合代表关系”。例如在 Kruskal 中，并查集只负责判断“加这条边会不会成环”，真正决定最小生成树权值的是排序后的贪心过程，不是并查集本身；再比如有些题要求删除边后的动态连通性，普通并查集不支持高效删除，很多时候要改成离线倒序处理，而不是硬在原结构上减边。换句话说，并查集很强，但它强在边界明确：只管合并与查询连通，不管路径语义。
🧪 课后一题：无向图有 6 个点，初始互不连通。依次执行
💡 易混淆点：并查集维护的是“属于同一个集合”而不是“图上的父子关系”或“实际路径”，
#CS
并查集（Union-Find / Disjoint Set Union, DSU）解决的核心不是“怎么走”，而是“是不是一伙的”。当图上的边会不断加入，而你反复想问两个点当前是否连通时，如果每次都重新跑一次 BFS 或 DFS，代价会越来越高；并查集的设计思路更直接：它不关心整条路径长什么样，只维护每个点属于哪个集合。
union(x, y) 把两个集合合并，find(x) 找到 x 所在集合的代表元，于是“x 和 y 是否连通”就变成比较 find(x) == find(y)。它之所以高效，关键在两个优化。一个是 path compression：每次
find 时，把沿途节点直接挂到根上，后面再找就更快；另一个是 union by rank/size：总把更小或更浅的树挂到更大或更高的树下面，避免结构退化。两者一起使用后，单次操作的均摊复杂度接近 O(1)，严格地说是 O(α(n))，这里的 α 是反 Ackermann 函数，在实际规模里几乎可以当常数看待。这也是为什么 Kruskal 最小生成树、离线连通性判断、朋友圈合并、岛屿归类这类题几乎都会优先想到并查集。但并查集的“快”，是靠主动丢弃大量路径细节换来的。它只告诉你两个点最后是不是在同一个集合里，却不会保留“经过了哪些边”“路径长度是多少”“谁是父谁是子”的真实图结构。所以它特别适合回答 connectivity，却不适合回答 shortest path、具体路径恢复、拓扑先后关系 这类问题。很多人一看到图连起来了，就下意识想用并查集一路做到底，结果在需要距离、方向、层次的时候才发现信息早就没被保存下来。
真正容易踩坑的地方，恰恰在这里：你以为自己维护的是一棵“树”，其实维护的只是一个“集合代表关系”。例如在 Kruskal 中，并查集只负责判断“加这条边会不会成环”，真正决定最小生成树权值的是排序后的贪心过程，不是并查集本身；再比如有些题要求删除边后的动态连通性，普通并查集不支持高效删除，很多时候要改成离线倒序处理，而不是硬在原结构上减边。换句话说，并查集很强，但它强在边界明确：只管合并与查询连通，不管路径语义。
🧪 课后一题：无向图有 6 个点，初始互不连通。依次执行
union(1,2)、union(2,3)、union(4,5)、union(3,5) 之后，1 和 5 是否连通？6 和 1 是否连通？答案：union(3,5)💡 易混淆点：并查集维护的是“属于同一个集合”而不是“图上的父子关系”或“实际路径”，
find 出来的根只是代表元，不等于原图里的起点、终点或最近公共祖先。#CS
