HDU 3313 Key Vertex：有向無環圖中 s-t 割點查找

HDU 3313 Key Vertex：有向無環圖中 s-t 割點查找

給定有向無環圖（DAG），求從 s 到 t 的所有路徑必經的頂點（割點）。n ≤ 100000, m ≤ 300000。利用拓撲序性質：先求最短路（BFS/SPFA），最短路上的點按距離遞增排列。從 s 沿最短路 DFS 尋找最遠的「必經點」，迭代直到達到 t。

算法流程

1. BFS 求最短路：從 s 出發 BFS 計算 dist[v] 並記錄父節點 fa[v]。若 t 不可達，所有點都是割點（輸出 n）。
2. 提取最短路鏈：從 t 回溯 fa 到 s，標記最短路上的點 mark[v]=1。
3. 迭代 DFS 找割點：
   • 當前起點 cur = s，答案 ans=1（含 s）。
   • 從 cur DFS，只走 mark=1 的點，找到距離 dist 最大的點 next。
   • next 即為下一個割點，ans++，cur = next。
   • 重複直到 cur == t。

正確性證明

在 DAG 中，s 到 t 的所有路徑長度 ≥ dist[t]。最短路上的點按 dist 嚴格遞增。若某點 v 在最短路上，且從 s 到 v 的所有路徑必經 u，則 u 是割點。DFS 找最遠可達最短路點，保證找到的點是「瓶頸」。

完整代碼

關鍵細節

邊數組開 N*3 防止越界。
BFS 用 SPFA 模板（可處理負權，此處權均為 1）。
DFS 只遍歷 mark=1 的點，非最短路點直接遞歸探索，不影響割點判定。
dist 比較確保找到最遠點。


複雜度

BFS：O(n+m)
DFS 總共：每條邊最多訪問一次，O(n+m)
總體：O(n+m)，線性時間，完美應對 10⁵ 規模。


總結
HDU 3313 巧妙利用 DAG 最短路的拓撲有序性，將割點查找轉化為最短路上的「瓶頸點」迭代搜索。避免了一般圖割點的 Tarjan 算法（O(n+m) 但常數大、難寫），代碼簡潔高效，是 DAG 割點問題的最佳解法。