题目重点：区分节点身份与数值，以DFS或DSU维护分量极值，处理孤立点、自环、重复边和负节点值。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版无向图，节点编号0..n−1，values[i]是属性而非身份；边起点/终点需同长度。若有向图须核对weak/strong connectivity。
- 孤立节点分量差0，空图返回0。节点值可负且重复，自环/重复边不改变连通性。
- 差值用宽整数，不能用节点index代替value计算。
解题路线
- DFS/BFS解法构邻接表，按未访问节点启动遍历，当前分量更新lo/hi。结束取hi−lo，再全图max。节点入队即标visited，重复边不会重复扩展。
- 示例给DSU替代：每个root保存size、low、high；union两个不同root时合并极值，最终只遍历root计算范围。路径压缩与按size合并提升批量边处理。
- 不在边上取最大abs差：路径两端可能值差很大但各相邻边差较小。目标是整个分量的极值，可通过任意长度路径关联。
- 输入从三个list转换时核对边数组长度、端点与节点id映射；稀疏外部id需字典映射，不把节点value当map key而合并同值节点。
- 在线只加边，DSU可持续更新全局最大差；删除边后分量可能拆开，原DSU无逆操作，需要离线回滚或动态连通，不能沿用union再取旧极值。
手动走一遍
训练例values=[−5,0,10,100]，边0−1、1−2。前三点同分量，差15，孤立节点3差0，答案15。相邻边最大差只有10，不能替代分量范围；两个同值但不连通节点仍是两个分量。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def maximum_component_range(values, edges):
n = len(values)
parent = list(range(n))
size = [1] * n
low = list(values)
high = list(values)
def find(index):
while parent[index] != index:
parent[index] = parent[parent[index]]
index = parent[index]
return index
for a, b in edges:
if not (0 <= a < n and 0 <= b < n):
raise ValueError("invalid endpoint")
ra, rb = find(a), find(b)
if ra == rb:
continue
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
low[ra] = min(low[ra], low[rb])
high[ra] = max(high[ra], high[rb])
return max((high[i] - low[i] for i in range(n) if parent[i] == i), default=0)
复杂度
DFS/BFS O(n+e)时间与空间；DSU O((n+e)α(n))均摊、O(n)状态空间，边可流式处理。5,000个随机小图用独立DFS收集全部值作为oracle，与DSU版本核对，自环和空图包含在内。
易错点与追问
容易失分的边界
- 只算边两端差。
- 同值节点当成同一个节点。
- 有向图未经澄清就当无向。
- DSU删除边仍保留过时分量极值。
继续深挖
- 若图有向，strong与weak component答案怎样不同？
- 节点值在线更新，root极值如何维护？
- 要返回取得最大差的两个节点，DSU保存什么？
- 同时增删边如何选离线方案？
