HDU 1269 迷宮城堡：Tarjan 算法求有向圖強連通分量

HDU 1269 迷宮城堡：Tarjan 算法求有向圖強連通分量

判斷給定有向圖是否為強連通圖（任意兩點互達）。即檢查強連通分量 (SCC) 數量是否為 1。

Tarjan 算法核心

基於 DFS，維護：

• dfn[u]：訪問時間戳。
• low[u]：以 u 為根的子樹能回溯到的最早祖先時間戳。
• 棧 S 存當前 DFS 路徑上的點。

關鍵步驟

1. 訪問 u：dfn[u]=low[u]=++timer，入棧。
2. 遍歷出邊 u→v：
   　① v 未訪問：遞歸 v，回溯 low[u]=min(low[u], low[v])。
   　② v 在棧中：low[u]=min(low[u], dfn[v])（回邊）。
3. 若 low[u] == dfn[u]：u 為 SCC 根，彈棧直到 u，標記同一 SCC 編號。

完整代碼

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 100010;
vector G[MAXN];
int dfn[MAXN], low[MAXN], sccno[MAXN], timer, scc_cnt;
stack S;

void dfs(int u) {
    dfn[u] = low[u] = ++timer;
    S.push(u);
    for (int v : G[u]) {
        if (!dfn[v]) {
            dfs(v);
            low[u] = min(low[u], low[v]);
        } else if (!sccno[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int x = S.top(); S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        if (n==0 && m==0) break;
        for (int i=0; i

複雜度與注意點

時間 O(V+E)，空間 O(V+E)，n,m ≤ 1e5 輕鬆通過。
遞歸深度可能達 V，C++ 默認棧通常夠用；極大圖可改用手動棧非遞歸版。
low[u] = min(low[u], dfn[v]) 針對回邊用 dfn 而非 low，是 Tarjan 正確性關鍵。


Kosaraju 對比
Kosaraju 需兩次 DFS + 反圖，代碼稍長。Tarjan 一次 DFS 即得，更常用於競賽。
此題是強連通分量模板題，掌握 Tarjan 核心邏輯（dfn/low/stack）即可解決所有 SCC 相關問題。