🎮图鉴更新：不找路径，只扫连通块，并查集一键通关
你是一名资深运维，信奉"预判风险就是节约生命"，技能树上最亮眼的天赋就是在服务器崩溃前把锅甩出去。这天运维小哥丢来一个任务：从1 号测试机，一路 SSH 到n 号生产机，中间跳板机的安全系数 distance 一个比一个离谱——数字越小越刺激，敲个回车就可能蓝屏、宕机、主板升天。整条链路的安全性由最烂那台跳板机决定（木桶效应，也是生产事故的第一块多米诺），崩了你会被截图挂上 Slack #incident-recap 频道循环处刑。
你的任务说白了就是：所有可能跳转路径里，最坏能踩到多烂的跳板机——也就是最小安全系数的最小值。为什么求下限？因为甩锅要趁早。只要你摸清全网最脆的那台机器，就能理直气壮输出：
“团队，本次路径不可避免触碰了安全系数 3 的遗产服务器，已连续运行 999 天，属不可抗力……”
你甚至故意绕远路去踩它——毕竟策划给了你一个 BUG 级技能：可以反复走同一条路、也可以多次到达同一节点。这意味着你可以像刷副本一样，把整张图的边全踩一遍，攒满“烂机器证据库”再晃悠到终点。只要 1 号和 n 号服务器连通，你总能溜达到那个最脆节点上——这不是冒险，这是战略性踩雷。
这压根不是最短路，是考连通性：1 和 n 所在连通块内所有边的最小值。
你邪魅一笑，从工具箱抽出两件神装，准备展开这场甩锅之旅。
DFS
从 1 号机出发，把能连上的跳板机全踩一遍，顺便记下见过的最小安全系数。
递归 DFS：实现起来干净利落，像一把匕首。
def minScore(n: int, roads: List[List[int]]) -> int:
# 无向图，双向建边
g = [[] for _ in range(n + 1)]
for u, v, cost in roads:
g[u].append((v, cost))
g[v].append((u, cost))
vis = [False] * (n + 1)
ans = float('inf')
# 递归 DFS：一条路走到黑，撞墙再回溯
def dfs(u: int):
nonlocal ans
vis[u] = True
for v, cost in g[u]:
ans = min(ans, cost)
if not vis[v]: # 如果下一个 v 还没访问过
dfs(v) # 递归访问 v（系统会自动把返回地址压入调用栈）
dfs(1) # 从 1 号机出发，开始踩点
return ans
但递归匕首有个致命弱点：跳板机太多→调用栈太深→RecursionError，锅还没甩出去自己先炸了，留下满地碎片成为第二天晨会的素材：“看，这就是那个写出无限递归的天才。”
成熟运维当然有栈式防炸甲——手动模拟递归，把系统调用栈换成自己维护的列表栈，稳如老狗。
迭代 DFS：和递归版逻辑完全一样，只是把"系统自动压栈"换成了"手动 append/pop"。
def minScore(n: int, roads: List[List[int]]) -> int:
g = [[] for _ in range(n + 1)]
for u, v, cost in roads:
g[u].append((v, cost))
g[v].append((u, cost))
vis = [False] * (n + 1)
ans = float('inf')
# 迭代 DFS：手动栈，稳如老狗
stack = [1] # 手动栈，从 1 号服务器开始
vis[1] = True # 标记起点已访问，到此一游
while stack:
u = stack.pop()
for v, cost in g[u]:
ans = min(ans, cost)
if not vis[v]:
vis[v] = True
stack.append(v)
return ans
**两种 DFS 本质相同：**遍历 1 号机所在的连通分量，沿途捡最小的边。时间 O(n+m)，空间 O(n+m)。递归版优雅简洁，像个精炼的甩锅话术；迭代版稳健可控，像个详细的甩锅邮件。
但你的强迫症开始隐隐作痛：为了找一个连通块的最小边，居然要把所有节点和边都扫一遍？这种“战略性踩雷”的脚本，是不是有点太敬业了？
你重新审视手里的底牌。策划给了你三个关键信息：
- 可以重复走 → 不需要关心具体路径，只关心连通分量
- 求最小边权 → 这是整个连通分量的集体属性，完全可以边建边维护
- 单次查询 → 只问 1 和 n 所在连通块的最小值，不问过程，不问路径
这三条信息指向同一个结论：你要的不过是 1 号和 n 号服务器所在连通分量里的最小边权。而能直接维护连通分量、顺手还能记个最小值的，正是工具箱底层压着的另一件神器——并查集。它天生为连通性而生，连图都不用完整建，边读边合并，账本随时可查。
并查集——连通性的天选之子
真正的甩锅大师，从来不止一手准备。
并查集天生就是用来维护连通分量的神器——它能把整张图压缩成若干个集合，每个集合的根节点手里攥着该集合的集体属性。查询时只需 find(1)，瞬间拿到答案——不用遍历、不回溯、不废话，查询 O(α(n)) ≈ O(1)，甩锅 O(∞)。
你只需要三步：
- 初始化：每个节点自立门户，
parent[i]=i，min_cost[i]=∞ - 合并：遍历所有道路，把相连的节点合并到同一集合，顺手更新该集合的最小安全值
- 查询：返回节点 1 所在集合的最小安全值，就是答案
这招完全绕开了显式的图遍历，直接把问题降维成"集合合并 + 最小值维护"。
基础版并查集：
一个 parent 数组、一个 min_cost 数组，合并时随便把一方挂在另一方下面（谁当爹都行），查找时带路径压缩（把沿途节点全挂到根下面，下次一查就中）。时间复杂度近似 O(m α(n))，空间 O(n)：
# 并查集
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # parent[i] 表示节点i的父节点
self.min_cost = [float('inf')] * n # min_cost[i] 表示节点i所在集合的最小边权
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y, cost):
"""合并 x 和 y 所在的集合，同时更新最小边权"""
px, py = self.find(x), self.find(y)
if px != py:
self.parent[px] = py
self.min_cost[py] = min(self.min_cost[py], self.min_cost[px], cost)
else:
self.min_cost[px] = min(self.min_cost[px], cost)
class Solution:
def minScore(self, n: int, roads: List[List[int]]) -> int:
uf = UnionFind(n + 1)
for u, v, cost in roads:
uf.union(u, v, cost)
return uf.min_cost[uf.find(1)]
但基础版有一个隐患：合并时总是 parent[px] = py，可能导致树变得极高（极端情况退化成链表），虽然路径压缩能挽回一些，但你想优雅到底，于是祭出按秩合并优化：加一个 rank 数组记录树的深度（或大小），永远把小树挂在大树下面，确保树高稳定在 O(log n)。搭配路径压缩，双管齐下，性能拉满。
按秩合并版：
合并时比较两棵树的"秩"（近似高度或节点数），把矮树挂到高树下，避免树过高导致 find 变慢。
# 并查集
class UnionFindOptimize:
def __init__(self, n):
self.parent = list(range(n)) # parent[i] 表示节点i的父节点
self.min_cost = [float('inf')] * n # min_cost[i] 表示节点i所在集合的最小边权
self.rank = [0] * n # rank[i] 表示节点 i 所在树的秩（近似高度）
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y, cost):
"""按秩合并 x 和 y 所在的集合，同时更新最小边权"""
px, py = self.find(x), self.find(y)
if px == py:
self.min_cost[px] = min(self.min_cost[px], cost)
return
# 按秩合并：矮树挂到高树下
if self.rank[px] < self.rank[py]:
self.parent[px] = py # px 树矮，把 px 挂到 py 下
self.min_cost[py] = min(self.min_cost[py], self.min_cost[px], cost)
elif self.rank[px] > self.rank[py]:
self.parent[py] = px # py 树矮，把 py 挂到 px 下
self.min_cost[px] = min(self.min_cost[px], self.min_cost[py], cost)
else:
self.parent[py] = px # 两树一样高，随便挂（这里把 py 挂到 px 下）
self.min_cost[px] = min(self.min_cost[px], self.min_cost[py], cost)
self.rank[px] += 1 # px 树高度 +1
class Solution:
def minScore(self, n: int, roads: List[List[int]]) -> int:
uf = UnionFindOptimized(n + 1)
for u, v, cost in roads:
uf.union(u, v, cost)
return uf.min_cost[uf.find(1)]
时间复杂度 O(m α(n))，空间 O(n)。最关键的是——你根本不需要显式建图，边读边合并，流水线作业，潇洒得像开着自动拾取刷副本。并查集这把降维打击杖，让你在甩锅的路上又领先了一个身位。
尾声：
你合上笔记本，从工位抽屉里翻出那本牛皮封面的 《踩坑指南》——这是你多年运维生涯的血泪结晶，封面上还沾着上次服务器爆炸时溅到的咖啡渍。 你翻到最新一页，工工整整地写下今天的战利品——一张随身携带的判断流程图：
拿到一个图论题， 先问自己：和连通性有关吗？ ├─ 是 → 需要具体路径吗？ │ ├─ 是 → DFS/BFS │ └─ 否 → 需要维护连通分量的属性吗？ │ ├─ 是 → 并查集 │ └─ 否 → 边是动态加的？频繁查询？ │ ├─ 是 → 并查集 │ └─ 否 → DFS/BFS 也可以 │ └─ 否 → 是最短路径/层次问题吗？ ├─ 是 → BFS / Dijkstra └─ 否 → 需要遍历整张图吗？ ├─ 是 → DFS/BFS └─ 否 → 看情况开盲盒
你深吸一口气，准备好了完美的甩锅话术：“主管，不是我的问题，是 1 号服务器所在连通分量里有台安全系数只有 3 的遗产服务器，这是并查集算出来的，数学不会骗人。如果您不信，我可以给您画个 Union-Find 的树形图。”
存档已保存，下张地图见。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。