連通網絡裡那個脆弱的點
想像一座城市，每個路口都能到達其他每個路口。現在，假設有一個路口塌了。在一座蓋得好的城市裡，車流只是改道；在一座脆弱的城市裡，一整個街區忽然就被切斷，與其餘部分隔絕了。那個一拿掉就會把網絡斷開的路口，正是本篇要獵捕的對象。用圖的語言說：一個割點（cut vertex）是這樣一個頂點——把它連同它所有的邊一併刪去，會讓圖的連通分量數目增加。與之相伴的概念是橋：一條一刪去就會造成同樣後果的邊。兩者都是網絡的單點故障，而只要韌性要緊的地方，找出它們就要緊：電網、公路圖、通訊骨幹、供應鏈。
笨方法很誠實，但很慢：對 V 個頂點中的每一個，把它刪掉、重跑一次搜尋，看看圖有沒有散掉。每一次測試要花一趟完整的走訪 O(V + E)，所以整件事是 O(V * (V + E))——對一張極小的圖還行，對一張大圖則毫無指望。本篇美妙的結果是：單單一趟深度優先搜尋，就能在一次掃描裡找出每一個割點與每一條橋，花的時間就是當初走訪這張圖一次所用的那個 O(V + E)。我們等於免費拿到了這張脆弱地圖，搭在一趟我們早已會跑的搜尋上順道完成。
DFS 樹就是那件秘密武器
整個把戲，靠的是你兩篇之前就見過的一個事實。當深度優先搜尋探索一張無向圖時，它會刻出一棵 DFS 樹，而邊的分類會變得驚人地簡單：每一條邊不是樹邊（用來發現一個新頂點），就是一條從某頂點往樹上爬、回到它自己某個祖先的回邊。關鍵在於，無向圖的 DFS 完全不會產生任何交叉邊。為什麼？若兩個位於不同分支的頂點之間有一條邊，那麼 DFS 先抵達的那一個，早就會沿著那條邊走過去、把另一個變成自己的後代——所以它們根本不可能最後落在不同的分支裡。正是這一個保證——只有樹邊與回邊、絕無側向跳躍——讓割點得以單憑樹本身就被偵測出來。
下面這個直覺，把樹變成了答案。想像一個頂點 u，以及掛在它某個孩子底下的那棵子樹。要讓這棵子樹在 u 被刪掉後仍存活，它必須另有一條出路——某條從子樹內部往上爬、爬到嚴格高於 u 的某個祖先的回邊，徹底繞過 u。只要有任何一個孩子的子樹沒有這樣的逃生路線，那麼 u 就是連接那棵子樹與圖其餘部分的唯一通道，刪掉 u 就會把它孤立。這正是讓 u 成為割點的原因。於是「u 是割點嗎？」這個問題，化約成了「u 的每個孩子的子樹，能不能不經過 u 就抵達 u 之上？」——而要回答那個問題，我們需要一個數。
每個頂點兩個數：發現時間與最低可達值
替每個頂點配一個發現時間 disc[v]：一個計數器，從 1 開始，每當 DFS 首次造訪一個頂點就加一。所以 disc 告訴你 DFS 抵達各物件的順序——祖先的 disc 永遠小於它的後代。現在來定義本篇的主角，最低可達值 low[v]：從 v 出發，先沿著 v 子樹內任意多條樹邊往下走、再最多走一條回邊，所能抵達的最小發現時間。白話說，low[v] 就是以 v 為根的整棵子樹，動用內部現有的邊，所能往上爬到的最高點（最小的 disc）。若 low[v] 很小，這棵子樹就有一道梯子能搆到樹上很高的地方；若 low[v] 等於 disc[v]，這棵子樹爬不過 v 自己。
DFS(u, parent):
disc[u] = low[u] = ++timer
for each neighbour v of u:
if v == parent: continue # don't bounce back on the tree edge
if v not visited: # tree edge: recurse, then absorb child
DFS(v, u)
low[u] = min(low[u], low[v])
# bridge: low[v] > disc[u]
# cut pt: low[v] >= disc[u] (non-root u); root needs >=2 children
else: # back edge to an ancestor
low[u] = min(low[u], disc[v])計算 low[v] 妙在它非常局部。當 DFS 處理完一個頂點 v，low[v] 就只是三樣東西的最小值：它自己的 disc[v]；它經由一條直接回邊所能搆到的任一祖先的 disc；以及它每個樹孩子的 low 值（因為孩子子樹搆得到的，v 也搆得到，只要先往下走進那個孩子）。所以隨著遞迴回返，low 會往上冒泡——每個孩子把自己的 low 值交給父親，父親取其中最小的。這正是上一篇裡驅動塔揚演算法求強連通分量的那套「向上流動的記帳」；最低可達值這個構想是一件工具戴著兩頂帽子，這裡用在無向圖上，而非有向圖。
把橋與割點讀出來
有了 disc 與 low，兩個條件就很俐落了。考慮一條從 u 往下連到它孩子 v 的樹邊。邊 (u, v) 是橋，恰好在 low[v] > disc[u] 的時候。照字面讀：v 的整棵子樹所能搆到的最高點，嚴格低於 u，所以把那棵子樹綁在上方世界的唯一連線就是這一條邊——剪掉它，子樹就掉了。u 是割點的條件幾乎一模一樣，只是把不等號換成 >=：一個非根的 u 是割點，當它某個孩子 v 滿足 low[v] >= disc[u]，意思是 v 的子樹爬不過 u（它搆得到 u，但更高就不行了），所以拿掉 u 就把它斬斷了。
DFS 的根需要它自己一條特殊規則，而原因不難看出。根沒有祖先，所以上面那個 low/disc 比較對它毫無意義。改成這樣：根是割點，恰好在它有兩個或更多樹孩子的時候。一個孩子，表示根坐在一條鏈的末端，拿掉它後其餘部分仍連通；兩個孩子，表示 DFS 不得不重新啟動、進入它從第一個分支搆不到的第二個分支——所以那些分支只透過根相連，刪掉根就把它們劈開。對根，就數它的樹孩子數來判斷；對其他每個頂點，就用 low[v] >= disc[u] 這個測試。
雙連通性：沒有單點故障的網絡
把整幅畫面翻轉過來，你得到的就不是一個弱點，而是一個設計目標。一張連通圖是雙連通的，當它完全沒有割點——沒有任何單一頂點一失去就會把它斷開。等價地說（而這是個可愛的刻畫），一張圖是雙連通的，當每一對頂點之間都至少有兩條頂點不相交的路徑：兩條不共用任何中間路口的路線。這正是工程師想要的那種冗餘。任何一個節點故障，車流仍找得到出路，因為總是有第二條獨立路徑在等著。
- 跑一趟 DFS，隨著遞迴下降與回返，替每個頂點指定 disc 與 low。
- 每當一條樹邊 (u, v) 處理完，把它推進一個「尚未歸入某個塊」的邊堆疊。
- 當你碰上割點條件 low[v] >= disc[u]，就從堆疊頂一路彈出邊，直到彈到 (u, v)：那些彈出的邊組成一個雙連通塊（一個極大的雙連通片段）。
- 割點恰好就是被兩個或更多這種塊所共享的頂點——網絡那些冗餘片段被縫合在一起的鉸鏈。
做個小小的誠實校正，因為這裡很容易把話說滿。雙連通性講的是頂點故障——熬過任一節點的失去。對應到邊故障（熬過任一連線的失去）的平行概念，是一張沒有橋的圖，那是另一個性質；一張圖可以沒有橋卻仍有割點，反之亦然。再者，這裡整套最低可達值的機制，是為無向圖打造的，倚賴的是「沒有交叉邊」這個保證；這些問題在有向圖上的表親（強連通性、SCC 分解）需要同一構想的有向版本，這正是它們各自單獨成篇的原因。一樣優雅的 O(V + E) 成本、一樣的 disc/low 記帳——但你得把它用在對的那種圖上。
為什麼它正確，以及它的代價
正確性穩穩地建立在「沒有交叉邊」這個性質上。因為無向圖的 DFS 只產生樹邊與回邊，每一條不經過 u 而逃出子樹的路徑，都必須經由一條從子樹內部連到 u 某個祖先的回邊——根本沒有別種邊可用。這就是為什麼 low[v]——它精確捕捉了「v 子樹內任一回邊所能搆到的最高祖先」——是這棵子樹逃生選項的一份完整摘要。什麼都不會漏，因為交叉邊（它本可能提供一條偷偷的側向出口）在這個情境下並不存在。因此 low[v] >= disc[u] 這個測試，不是一個「通常管用」的啟發法；它與「v 的子樹在 u 之上沒有出口」完全等價，而後者正是「u 把 v 切斷」的字面定義。
執行時間是那個招牌般的回報。我們只做一趟 DFS，每個頂點碰一次、每條邊檢視常數次，所以總計是 O(V + E)——和前面幾篇裡 BFS 與 DFS 掙得的那個界相同，承襲自相鄰串列的走訪。把它和笨方法的「刪除再重測」O(V * (V + E)) 比一比：在一張一百萬頂點的稀疏圖上，差距大約是一百萬倍。不過，對 O(V + E) 承諾了什麼、沒承諾什麼要誠實。它是漸進的，所以遞迴與堆疊記帳的隱藏常數意味著，對寥寥幾張極小的圖，笨方法的掃描未必真的感覺更慢；勝利在於擴展性，而這份勝利恰恰在它要緊之處壓倒性地巨大——在那些你真正需要稽核其韌性的大型網絡上。