关键连接
关键连接题本质上是在找桥。真正要抓住的不是结论，而是
low[v] > dfn[u]这条判定为什么成立。
问题描述
LeetCode 1192 - 查找集群内的关键连接
给定一个无向连通图，找出所有的关键连接（桥）。关键连接是指删除后会使图不连通的边。
输入: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
输出: [[1,3]]
图示:
0---1---3
\ /
2
关键连接: (1,3)
解题思路
- 桥的定义：删除后图不连通的边
- Tarjan算法：使用DFS和时间戳
- 判断条件：
low[v] > dfn[u] - 无向图：注意处理父节点
为什么 low[v] > dfn[u] 就说明是桥
如果从 v 这棵 DFS 子树出发，连一条返祖边都回不到 u 或 u 的祖先，
那就说明 u - v 是这棵子树和上层世界之间唯一的连接通道。
这条边一删，整棵子树都会被切下来，所以它就是桥。
Go 代码
Go 实现
func criticalConnections(n int, connections [][]int) [][]int {
// 构建邻接表
graph := make([][]int, n)
for _, conn := range connections {
u, v := conn[0], conn[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
dfn := make([]int, n)
low := make([]int, n)
for i := range dfn {
dfn[i] = -1
low[i] = -1
}
bridges := [][]int{}
time := 0
var dfs func(int, int)
dfs = func(node, parent int) {
dfn[node] = time
low[node] = time
time++
for _, neighbor := range graph[node] {
if neighbor == parent {
continue
}
if dfn[neighbor] == -1 {
dfs(neighbor, node)
if low[neighbor] < low[node] {
low[node] = low[neighbor]
}
if low[neighbor] > dfn[node] {
bridges = append(bridges, []int{node, neighbor})
}
} else {
if dfn[neighbor] < low[node] {
low[node] = dfn[neighbor]
}
}
}
}
for i := 0; i < n; i++ {
if dfn[i] == -1 {
dfs(i, -1)
}
}
return bridges
}复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V+E) | 一次DFS |
| 空间复杂度 | O(V+E) | 图和递归栈 |
易错点
Tarjan 找桥最容易错的是把无向图边和父节点关系处理乱。
- 无向图 DFS 时要跳过父边，否则会误把父节点当返祖边。
dfn是首次访问时间，low是能回到的最早时间戳，含义不能混。- 图不一定只有一个连通块，外层通常还要补一层遍历。
- 如果题目允许重边，自定义父边判断要更谨慎。