LeetCode 1192. 查找集群内的关键连接
题目描述
题意分析
将服务器看作顶点、连接看作无向边。删除某条边后，如果图不再连通，这条边就是关键连接，也称为桥。题目保证原图连通，没有自环和重复边，顶点、边的数量均可达到十万级。
逐条删边再检查连通性，会为每条边重复遍历整个图。可以反过来判断一条边是否有替代路径：如果边位于某个环上，删除它后仍能沿环的另一侧绕过去，因此它不是桥；不在任何环上的边才是桥。
深度优先搜索能把边分成通向新节点的树边，以及连接已访问节点的非树边。通过记录子树能绕回的最早祖先，一次遍历就能检查每条树边是否有替代路径。实现使用显式栈，避免十万节点长链带来的深递归问题。
解法：显式栈模拟 Tarjan 桥判定
核心思路
[!blue]
先理解发现时间与最早可达时间。
dfn[u]是节点u第一次进入 DFS 的时间编号，从 1 递增，0 表示尚未访问。low[u]初始化为dfn[u]，最终表示：从u沿 DFS 树向下走任意步，再至多通过一条非树边回到祖先时，能够到达的最小发现时间。若邻点
v未访问，它会成为u的 DFS 子节点。必须等v的整棵子树处理完，再用low[v]更新low[u]，因为v子树能绕回的地方，u也可以先走到v再到达。若邻点已访问且不是父节点，则用这条边另一端的dfn[v]更新low[u]，记录通过该边直接回到的位置。桥的判定发生在子节点完成时。 对树边
u-v，若low[v] <= dfn[u]，说明v的子树能经其他边回到u或其祖先，这条树边就有替代路径。反之，若low[v] > dfn[u]，整棵子树都不能绕出父边到达父节点一侧，删除u-v就会将它与其余节点分开，因此它是桥。显式栈需要模拟递归的暂停与返回。 栈保存当前尚未完成的 DFS 路径，
parent[u]记录树上的父节点，next[u]记录下一个待检查的邻接位置。检查一条邻边后先推进next[u]；若发现新节点便压栈，暂停父节点。只有栈顶的邻边全部处理完，才能弹栈，此时low[u]才是最终值，可以检查父边并回传给父节点。无向边在邻接表中存了两个方向，从子节点看见父节点时必须跳过，否则会把来时的同一条边误当成替代路径。题目没有重复边，所以按父节点跳过是充分的。
解题步骤
- 为每条连接添加两个方向的邻接记录，初始化
dfn、low、parent、next。父节点设为 -1，作为根节点没有父亲的标记。- 从节点 0 开始，设置
dfn[0] = low[0] = 1并压栈。原图连通，所以一次 DFS 能覆盖全图。- 查看栈顶
u。若还有未处理邻边，取出v并推进next[u]：父节点直接跳过；未访问点设置父节点和发现时间后压栈；其余点用dfn[v]尝试降低low[u]。- 若
u的邻边已经处理完，将它弹栈。设父节点为p，若p >= 0，用low[u] > dfn[p]判断父边是否为桥，再执行low[p] = min(low[p], low[u])。- 栈为空时，所有子树都已经完成并回传结果，返回收集的桥；边的顺序和两个端点的顺序均不影响答案。
对三角形
0-1-2-0加边1-3，若沿0→1→2搜索，节点 2 能通过边2-0把最早可达时间降到节点 0 的发现时间，因此三角形上的树边不是桥。节点 3 只有父边，无法绕回，完成时low[3] > dfn[1]，所以1-3是桥。
代码实现
class Solution {
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (List<Integer> edge : connections) {
int a = edge.get(0);
int b = edge.get(1);
graph.get(a).add(b);
graph.get(b).add(a);
}
int[] dfn = new int[n];
int[] low = new int[n];
int[] parent = new int[n];
int[] next = new int[n];
int[] stack = new int[n];
Arrays.fill(parent, -1);
int time = 1;
int top = 0;
dfn[0] = low[0] = time;
stack[0] = 0;
List<List<Integer>> answer = new ArrayList<>();
while (top >= 0) {
int u = stack[top];
if (next[u] < graph.get(u).size()) {
int v = graph.get(u).get(next[u]++);
if (v == parent[u]) {
continue;
}
if (dfn[v] == 0) {
parent[v] = u;
dfn[v] = low[v] = ++time;
stack[++top] = v;
} else {
low[u] = Math.min(low[u], dfn[v]);
}
} else {
top--;
int p = parent[u];
if (p >= 0) {
if (low[u] > dfn[p]) {
answer.add(Arrays.asList(p, u));
}
low[p] = Math.min(low[p], low[u]);
}
}
}
return answer;
}
}
func criticalConnections(n int, connections [][]int) [][]int {
graph := make([][]int, n)
for _, edge := range connections {
a, b := edge[0], edge[1]
graph[a] = append(graph[a], b)
graph[b] = append(graph[b], a)
}
dfn, low, parent, next := make([]int, n), make([]int, n), make([]int, n), make([]int, n)
for i := range parent {
parent[i] = -1
}
time := 1
dfn[0] = 1
low[0] = 1
stack := []int{
0,
}
answer := [][]int{}
for len(stack) > 0 {
u := stack[len(stack)-1]
if next[u] < len(graph[u]) {
v := graph[u][next[u]]
next[u]++
if v == parent[u] {
continue
}
if dfn[v] == 0 {
parent[v] = u
time++
dfn[v] = time
low[v] = time
stack = append(stack, v)
} else {
low[u] = min(low[u], dfn[v])
}
} else {
stack = stack[:len(stack)-1]
p := parent[u]
if p >= 0 {
if low[u] > dfn[p] {
answer = append(answer, []int{
p,
u,
})
}
low[p] = min(low[p], low[u])
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(V+E)$。构建邻接表需遍历每条边；每个节点入栈、出栈各一次，
next使每条邻接记录也只被处理一次。- 空间复杂度：$O(V+E)$。邻接表占 $O(V+E)$，发现时间、最早可达时间、父节点、邻边游标和显式栈均占 $O(V)$。输出的桥最多有 $V-1$ 条。
关键点总结
[!green]
dfn一经赋值不再变化，low会在发现回边或接收子树结果时逐步减小。- 判断桥必须等待子树完成，压栈时的初始
low还没有包含后续回边信息。next[u]让父节点恢复执行时从下一条邻边继续，否则重复检查会破坏线性复杂度。- 已访问邻点若是后代，其
dfn比当前节点更大，不会降低已满足low[u] <= dfn[u]的值；直接取最小值即可。- 根节点没有父边，因此弹出根时只结束遍历，不执行桥判定。
易错点总结
[!yellow]
- 把严格大于写成大于等于：
low[child] == dfn[parent]表示子树仍能通过其他边回到父节点，父边不是桥。- 不跳过父边的反方向：每个子节点都会误以为可以绕回父节点，真正的桥也被漏掉。
- 对子节点刚压栈就回传
low：它还没搜索完，可能尚未发现构成环的边，应在弹栈时处理。- 把已访问邻点的更新写成
low[v]：当前这条非树边直接连接到的是v，对应的更新来源应为dfn[v]，不能与完成的子树回传混淆。- 忘记推进邻边游标：父节点恢复后会重新处理同一条边，可能无法结束。
- 脱离题目约束直接扩展：从 0 开始依赖图连通，按父节点跳过依赖没有重复边；本实现按当前题意处理即可。