題幹與適用場景
給定 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 狀態。