题目描述
思路解析动画文字版
记住「初始各自一块 → 逐边 union → 最后比 source 与 destination 的根」,下面逐帧套它。
先放下 6 个点 0~5,每个点的 parent 都指向自己,彼此独立。此刻连通块数 = 6,谁和谁都还没连上。
并查集准备就绪。接下来按给定顺序扫每条边,把边的两个端点并进同一个连通块。
第 1 条边 (0, 1):要把端点 0 和 1 连起来(两点高亮)。先各自 find 出所在块的根。
union(0, 1):把 0 那组的根接到 1 所在组的根上(永远接到对方的根,不是接到普通点),两组并成同一块(同色)。连通块数减 1,现在是 5。
第 2 条边 (0, 2):要把端点 0 和 2 连起来(两点高亮)。先各自 find 出所在块的根。
union(0, 2):把 0 那组的根接到 2 所在组的根上(永远接到对方的根,不是接到普通点),两组并成同一块(同色)。连通块数减 1,现在是 4。
第 3 条边 (3, 5):要把端点 3 和 5 连起来(两点高亮)。先各自 find 出所在块的根。
union(3, 5):把 3 那组的根接到 5 所在组的根上(永远接到对方的根,不是接到普通点),两组并成同一块(同色)。连通块数减 1,现在是 3。
第 4 条边 (5, 4):要把端点 5 和 4 连起来(两点高亮)。先各自 find 出所在块的根。
union(5, 4):把 5 那组的根接到 4 所在组的根上(永远接到对方的根,不是接到普通点),两组并成同一块(同色)。连通块数减 1,现在是 2。
第 5 条边 (4, 3):要把端点 4 和 3 连起来(两点高亮)。先各自 find 出所在块的根。
union(4, 3):find 后发现 4 和 3 已经同根了(前面的边已把它们间接连通)。这条边在块内成环,不合并新连通块、连通块数不变(仍是 2);不过 find(3) 顺手做了路径压缩,把 3 直接挂到根 4 上(parent 指针被理顺,只是不改变分块)。
五条边都并完了。看整张图:0、1、2 经边连成一块,3、4、5 经边连成另一块,共 2 个连通块。两块互不相连。
在查询前,先逐个点做一次 find 看它们各自归到哪个根,这样能一眼看清两个连通块的归属。根相同的点就是一块。
find(0) 的根是 2。这是目前见到的第 1 个不同的根,代表一个新连通块。
find(1) 的根是 2。和前面某个点的根相同,归入同一连通块。
find(2) 的根是 2。和前面某个点的根相同,归入同一连通块。
find(3) 的根是 4。这是目前见到的第 2 个不同的根,代表一个新连通块。
find(4) 的根是 4。和前面某个点的根相同,归入同一连通块。
find(5) 的根是 4。和前面某个点的根相同,归入同一连通块。
逐点 find 下来共出现 2 个不同的根:{0,1,2} 一根、{3,4,5} 另一根。两块界线清楚,接下来正式回答 source 到 destination 是否连通。
现在回答问题。先 find(source) = find(0):顺着 parent 一路找到 0 这一块的根 = 2。
再 find(destination) = find(5):找到 5 这一块的根 = 4。
比较两个根:2 和 4 不同。根不同说明 source 与 destination 分属不同连通块,彼此之间没有路径,返回 false。
反过来想:若问的是 source=0、destination=2,它俩同在上面这块、根相同,find 结果一致,就会返回 true。判定法则始终是「同根即有路径」。
边界:同点 true;无边异点 false;异块 false。
两个追问:DFS/BFS 等价但要建图;动态多查询并查集更优。
参考代码
from typing import Listclass Solution: def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x for a, b in edges: parent[find(a)] = find(b) return find(source) == find(destination)复杂度
- 时间：O(n + e·log n)，n 是点数,e 是边数。初始化 parent 是 O(n);每条边一次 union(两次 find)。本实现只用了路径压缩(没有按秩/按大小合并),单次 find 均摊为 O(log n);若再配上按秩合并,可进一步降到反阿克曼 α(n)、近似常数。合计 O(n + e·log n),已足够快
- 空间：O(n)，只需一个长度 n 的 parent 数组,不必显式建邻接表
易错点
面试追问把动画讲成自己的话
追问能不能不用并查集,改用 DFS 或 BFS?
追问如果题目改成「不断加边,中途多次询问两点是否连通」呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
被围绕的区域
LeetCode 130 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题