POJ 2553 The Bottom of a Graph：Tarjan 算法求強連通分量詳解

題目大意

給定有向圖，找出所有「底層」強連通分量 (SCC) 的頂點。底層 SCC 定義：該分量內無邊指向分量外部 (出度為 0)。輸出所有屬於底層 SCC 的頂點編號。

兩步解法

1. Tarjan 算法求所有 SCC，記錄每個頂點屬於哪個分量
2. 統計分量出度：遍歷所有邊，若邊跨分量，則源分量出度 +1
3. 出度為 0 的分量即為底層，輸出其所有頂點

Tarjan 算法核心邏輯

• dfn[u]：DFS 訪問時間戳
• low[u]：u 及其子樹能回溯到的最早祖先時間戳
• 棧維護當前 DFS 路徑上的點
• 當 low[u] == dfn[u] 時，彈出棧直到 u，形成一個 SCC

完整代碼實現

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 5005;

int n, m;
vector<int> G[MAXV];
stack<int> stk;

int dfn[MAXV], low[MAXV], dfsTime;
bool inStk[MAXV];
int compId[MAXV];    // 頂點 -> 分量 ID
int compCnt;         // 分量計數
int outDeg[MAXV];    // 分量出度

void tarjan(int u) {
    dfn[u] = low[u] = ++dfsTime;
    stk.push(u);
    inStk[u] = true;
    
    for (int v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]); // 子樹回溯更新
        } else if (inStk[v]) {
            low[u] = min(low[u], dfn[v]); // 回邊/橫邊更新 (注意用 dfn[v] 而非 low[v])
        }
    }
    
    if (low[u] == dfn[u]) { // 找到 SCC 根
        ++compCnt;
        while (true) {
            int v = stk.top(); stk.pop();
            inStk[v] = false;
            compId[v] = compCnt;
            if (v == u) break;
        }
    }
}

void solveSCC() {
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(inStk, 0, sizeof(inStk));
    compCnt = 0; dfsTime = 0;
    while (!stk.empty()) stk.pop();
    
    for (int i = 1; i <= n; ++i)
        if (!dfn[i]) tarjan(i);
}

void countCompOutDeg() {
    memset(outDeg, 0, sizeof(outDeg));
    vector<bool> vis(n+1, false);
    
    function<void(int)> dfs = [&](int u) {
        vis[u] = true;
        for (int v : G[u]) {
            if (compId[u] != compId[v]) 
                outDeg[compId[u]]++; // 跨分量邊
            if (!vis[v]) dfs(v);
        }
    };
    
    for (int i = 1; i <= n; ++i)
        if (!vis[i]) dfs(i);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    while (cin >> n && n) {
        cin >> m;
        for (int i = 1; i <= n; ++i) G[i].clear();
        while (!stk.empty()) stk.pop(); // 關鍵：多測試用例清空棧
        
        for (int i = 0; i < m; ++i) {
            int u, v; cin >> u >> v;
            G[u].push_back(v);
        }
        
        solveSCC();
        countCompOutDeg();
        
        bool first = true;
        for (int i = 1; i <= n; ++i) {
            if (outDeg[compId[i]] == 0) {
                if (!first) cout << ' ';
                first = false;
                cout << i;
            }
        }
        cout << '\n';
    }
    return 0;
}

Tarjan 關鍵細節對比

常見錯誤避坑

1. 多測試用例未清空全局變量：棧、dfn、low、inStk、compId、outDeg、dfsTime、compCnt 全部需重置
2. low 更新用錯：回邊用 dfn[v]，樹邊用 low[v]
3. 出度統計重複計算：同分量間多條邊會重複計出度，但不影響「出度為 0」判斷
4. 遞歸棧溢出：n=5000 遞歸深度可能超限，可改迭代或增大棧

複雜度分析

• 時間：O(V+E) — Tarjan 線性，出度統計線性
• 空間：O(V+E) — 圖存儲、棧、數組

Kosaraju 算法對比 (備選)