题干与适用场景
给定 n 个编号为 0 到 n - 1 的节点，以及数组 connections。其中每个二元组 [u, v] 表示一条无向边。图保证连通且为简单图：没有自环，也没有重复边。请返回全部 关键连接，也就是删除后会使图不再连通的边。答案顺序不限，每条边的两个端点也可以互换。
假设 2 <= n <= 100000，且 n - 1 <= connections.length <= 100000。例如：
n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
output = [[1, 3]]前三条边构成一个环，删除其中任何一条仍有替代路径。节点 3 只有 [1, 3] 这一条边， 删除它会让节点 3 与其他节点分离。在图论中，关键连接也叫桥或割边。
这是一道考察图不变量的算法题。现有的 Union-Find 文章处理加边过程中的连通分量；拓扑排序 处理有向无环图的依赖顺序；Dijkstra 处理加权路径的最短长度。本题要求判断删除每条无向边后 连通性如何变化，核心问题与它们都不相同。
面试官考察点
第一，候选人能否根据数据规模排除重复搜索。逐条删除边再跑 BFS 或 DFS，确实能正确回答单次 查询，但对 m 条边重复执行会达到 O(m(n + m))，无法承受 100,000 条边的输入。
第二，能否准确陈述 low-link 不变量。DFS 的发现时间 tin[u] 表示首次访问 u 的时刻。 low[u] 表示从 u 的 DFS 子树出发，沿树边向下，并至多使用一条非树边能够到达的最早发现 时间。对于 DFS 树边 u -> v，它是桥的充要条件是 low[v] > tin[u]。
第三，能否把不变量落实到实现细节。遇到已访问邻居时要用 tin[neighbor] 更新，不能用 low[neighbor]。还要跳过进入当前节点的那一条具体边，不能跳过所有端点等于父节点的边。 给边编号可以把这个区别写清楚，并让代码自然支持允许平行边的追问。
第四，能否注意运行环境。递归 DFS 写起来短，但 100,000 个节点组成的长链可能超过 JavaScript 运行时的调用栈限制。迭代 DFS 不仅要模拟进入节点，还要模拟子节点返回的时刻，因为只有子树 处理完毕后才能向父节点传播 low。
回答前需要澄清的问题
- 图是有向的吗？ 不是。本题是无向图；有向图中的“关键连接”需要另行定义和求解。
- 图一定连通吗？ 基础题保证连通。遍历所有未访问节点不会改变渐进复杂度，还能让实现直接
支持非连通图追问。
- 允许重复边吗？ 基础题不允许。实现仍给每条边分配 ID，因此若追问允许两条平行边，它们会
被正确视为互相提供替代路径，而不会都被判成桥。
- 输出端点顺序有限制吗？ 没有。如果评测要求规范顺序，可将每条边变成
[min, max]，并在
找完桥后再排序。
- 图会动态变化吗？ 不会，这是静态快照。持续插入或删除边属于动态连通性问题，每次都重跑
线性算法可能太贵。
- 可以递归吗？ 只有运行环境明确保证足够的栈深度才可以。对 TypeScript 和 JavaScript 的
100,000 节点约束，显式栈更稳妥。
30 秒回答框架
“我会做一次 DFS，为每个节点记录发现时间 tin。low 表示从当前 DFS 子树出发，不沿进入 该节点的原树边返回时，能到达的最早发现时间。子节点 v 完成后，如果 low[v] > tin[u]，说明 v 的子树没有其他路径回到 u 或其祖先，因此 [u, v] 是桥； 否则存在返祖边形成替代路径。我会给边编号，并用显式栈模拟 DFS，既能处理平行边追问，也避免 调用栈溢出。每个邻接项只处理一次，所以时间是 O(n + m)，空间是 O(n + m)。”
分步骤深入解答
先看正确但慢的基线方案：依次忽略每条边，再从它的一个端点遍历，检查另一个端点是否还能到达。 一次遍历是 O(n + m)，全部边就是 O(m(n + m))。在小图、只检查一条可疑边时，这个方案 简单且容易审查；面对题目规模，它不合格。
DFS 可以在一次遍历中暴露所有替代路径。首次进入节点 u 时，令 tin[u] = low[u] = timer，然后递增计时器。未访问的邻居成为 DFS 树子节点。通过另一条边 遇到已访问邻居时，该非树边可能让 low[u] 降到 tin[neighbor]。子节点 v 完成后，它的 整棵子树信息才齐全，此时用 low[u] = min(low[u], low[v]) 向上合并可达范围。
判定必须是严格大于。如果 low[v] < tin[u]，子树能到达 u 的某个祖先；如果 low[v] == tin[u]，子树能通过另一条路径回到 u 本身。这两种情况下，树边 [u, v] 都在 某个环上。只有 low[v] > tin[u] 才表示子树到已发现一侧的所有路径都必须经过 [u, v]。
迭代实现用 nextIndex[u] 记录节点 u 下一个待检查的邻接项。子节点运行时，父节点继续留在 栈中。所有邻接项耗尽后才将节点弹栈；这个弹栈事件就等同于递归调用返回，也是检查桥并向父节点 传播 low 的正确时机。
type AdjacentEdge = readonly [to: number, edgeId: number]
function findCriticalConnections(
n: number,
connections: ReadonlyArray<readonly [number, number]>,
): number[][] {
const graph: AdjacentEdge[][] = Array.from({ length: n }, () => [])
connections.forEach(([from, to], edgeId) => {
graph[from].push([to, edgeId])
graph[to].push([from, edgeId])
})
const tin = new Array<number>(n).fill(-1)
const low = new Array<number>(n).fill(-1)
const parent = new Array<number>(n).fill(-1)
const parentEdge = new Array<number>(n).fill(-1)
const nextIndex = new Array<number>(n).fill(0)
const bridges: number[][] = []
let timer = 0
for (let root = 0; root < n; root += 1) {
if (tin[root] !== -1) continue
tin[root] = timer
low[root] = timer
timer += 1
const stack = [root]
while (stack.length > 0) {
const node = stack[stack.length - 1]
if (nextIndex[node] < graph[node].length) {
const [neighbor, edgeId] = graph[node][nextIndex[node]]
nextIndex[node] += 1
if (edgeId === parentEdge[node]) continue
if (tin[neighbor] === -1) {
parent[neighbor] = node
parentEdge[neighbor] = edgeId
tin[neighbor] = timer
low[neighbor] = timer
timer += 1
stack.push(neighbor)
} else {
low[node] = Math.min(low[node], tin[neighbor])
}
} else {
stack.pop()
const parentNode = parent[node]
if (parentNode !== -1) {
if (low[node] > tin[parentNode]) {
bridges.push([parentNode, node])
}
low[parentNode] = Math.min(low[parentNode], low[node])
}
}
}
}
return bridges
}基础输入保证连通，所以外层循环看似多余；若取消连通保证，它会为每个分量启动一次 DFS，结果仍 正确。边 ID 也比只比较父节点更稳健。假设 u 和 v 之间有两条平行边，子节点只跳过其中的 树边，另一条会被识别为替代路径，从而降低 low。
正确性可以围绕一条已经完成处理的 DFS 树边 u -> v 来证明。按照 low[v] 的定义，若它不 大于 tin[u]，就存在一条从 v 子树到 u 或其祖先的非树路径。它与树路径合起来形成包含 [u, v] 的环，删除该边不会分离子树。若 low[v] > tin[u]，这样的路径不存在，从子树到先前 发现部分的每条路径都必须通过 [u, v]，删除它会增加连通分量数。因此该条件既充分又必要。
每条无向边在邻接表中出现两次，每个邻接项只检查一次；每个节点只入栈、出栈一次。时间复杂度 是 O(n + m)。邻接表、数组、显式栈和输出合计占用 O(n + m)；若不计输入图和返回结果， 辅助空间为 O(n)。
对抗性测试不能依赖输出顺序，应先规范化边集合再比较。一条孤立边必须是桥；一个环不应有桥； 树的每条边都是桥；两个环由一条边相连时只应返回连接边。还要用 100,000 节点长链验证不会遭遇 递归栈问题。进一步可以生成小规模随机图，把线性算法与“逐条删边再搜索”的基线结果做差分比较。
高质量示范回答
“直接做法是逐条删除边并重新遍历，复杂度会达到 O(m(n + m))。我可以用一次 DFS 的发现 时间和 low-link 值复用这些连通性信息。
进入节点 u 时，我把 tin[u] 和 low[u] 初始化为当前时间。树子节点必须完整处理后，才能 把它的 low 传播给 u。如果通过另一条边遇到已访问节点，就用那个节点的 tin 更新，因为 这个非树边本身正是当前不变量允许使用的一条逃生边。
子节点 v 完成后，[u, v] 是桥当且仅当 low[v] > tin[u]。相等不能算桥：相等说明子树 还有另一条路径回到 u，因此该边处在环上。严格大于则表示子树无法绕过这条树边到达 u 或 其祖先，删除它必然分离子树。
因为节点数可达 100,000，我会用显式栈。栈中的节点要一直保留到所有邻接项处理完，这样弹栈时 就能模拟递归返回，检查桥并传播 low。同时记录父边 ID，只跳过进入节点的具体边，平行边追问 也能正确处理。算法只检查每个邻接项一次，时间 O(n + m)，总空间 O(n + m)。测试会覆盖 环、树、两个环之间的单连接、长链、非连通分量和平行边，并用小随机图与基线做差分测试。”
常见错误
- 每条边都重跑 DFS → 结果正确但最坏复杂度远超线性 → **用一次 DFS，并在
low中保留
替代路径信息。**
- 使用
low[child] >= tin[parent]→ 相等已经表示存在另一条路径回到父节点 → **桥的条件
必须是严格的 low[child] > tin[parent]。**
- 遇到已访问邻居时使用
low[neighbor]→ 另一个 DFS 子树的可达性会错误穿过非树边，
可能掩盖真实的桥 → 已访问邻居使用 tin[neighbor]，树子节点结束后才使用 low[child]。
- 跳过所有指向父节点的边 → 平行边会被一起忽略，导致误报 → **给边编号，只跳过进入当前
节点的那条边。**
- 子节点尚未完成就判桥 → 此时还不知道子树的全部替代路径 → 在模拟返回的弹栈阶段判断。
- 只从节点 0 开始 → 非连通图追问会漏掉其他分量 → 为每个未访问节点启动遍历。
- 不检查运行时栈限制就递归 → 长链会让线性算法在运行时失败 → **使用显式栈，或先证明环境
支持所需递归深度。**
追问及应对
追问一：如果图不连通，需要改什么？
把桥定义为“删除后让全图连通分量数增加的边”。相同的 low-link 判定适用于每个分量。对每个 发现时间仍为 -1 的节点启动 DFS 即可；上面的实现已经这样做。不要把“删除后整个图第一次变得 不连通”当作判定标准，因为输入本来就可能不连通。
追问二：如果允许平行边和自环呢？
保留每条边的唯一 ID，只跳过 parentEdge[node]。第二条指向父节点的平行边会成为非树路径， 阻止这两条边被判为桥。自环只会用节点自己的发现时间更新自己，永远不可能是桥。基础题排除了 两者，但边身份让扩展后的结论仍正确。
追问三：如果改成返回割点呢？
发现时间和 low-link 信息仍可复用，但条件从边移到节点。非根节点 u 只要存在 DFS 子节点 v 满足 low[v] >= tin[u]，就是割点；DFS 根节点必须至少有两个 DFS 树子节点才是割点。 这里等号属于割点条件，而桥的条件使用严格大于。
追问四：如果边会持续加入呢？
当前算法对静态快照做一次线性计算。每次插边后重算需要 O(n + m)。只有插入的场景可以用专门 的在线桥维护结构；同时支持新增和删除则需要更通用的动态连通性设计。选型前先确认更新类型、 查询频率和一致性要求。
追问五：什么情况下重复搜索的基线反而更合适？
如果图很小、只检查一条可疑边，或诊断代码更看重直观性，那么忽略这一条边再做 BFS 更短、更易 审查。明确它检查单边的成本是 O(n + m) 即可；只有题目要求全部桥或大量重复查询时，才值得 引入 low-link 状态。