HDU 1269 迷宮城堡：Tarjan 強連通分量判斷強連通圖

題目大意

有向圖 N（≤10,000）節點，M（≤100,000）邊。判斷任意兩節點是否互達（即圖是否強連通）。多測資，以 0 0 結束。

解題思路

強連通圖 ⇔ 強連通分量數量為 1。使用 Tarjan 算法求 SCC 計數，若為 1 輸出 Yes，否則 No。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;

struct Edge { int to, next; } e[N*10];
int head[N], e_cnt;
int dfn[N], low[N], stk[N], top, idx, scc_cnt;
bool in_stk[N];

void add_edge(int u, int v) { e[e_cnt] = {v, head[u]}; head[u] = e_cnt++; }

void tarjan(int u) {
    dfn[u] = low[u] = ++idx;
    stk[++top] = u; in_stk[u] = true;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int v;
        do { v = stk[top--]; in_stk[v] = false; } while (v != u);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m;
    while (cin >> n >> m, n || m) {
        fill(head, head+n+1, -1); e_cnt = 0;
        fill(dfn, dfn+n+1, 0); fill(in_stk, in_stk+n+1, false);
        idx = top = scc_cnt = 0;
        for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; add_edge(u, v); }
        for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
        cout << (scc_cnt == 1 ? "Yes" : "No") << '\n';
    }
    return 0;
}

複雜度

• 時間：O(N + M)。
• 空間：O(N + M)。

替代方案：Kosaraju

兩次 DFS（原圖 + 轉置圖）同樣可得 SCC 計數，代碼略長但思路清晰。

注意

• 節點編號從 1 開始，陣列大小 N+1。
• 遞歸深度可能達 N，C++ 通常能承受；若棧溢出可改用非遞歸版 Tarjan。