POJ 2762 強連通分量縮點 + 拓撲排序判斷唯一路徑

問題核心

給定有向圖，判斷是否對任意兩點 u,v，至少存在 u→v 或 v→u 的路徑。即縮點後的 DAG 是否為「鏈狀」（每層拓撲序只有一個節點）。

算法流程

1. Tarjan 縮點：求強連通分量 (SCC)，構建縮點 DAG
2. 拓撲排序檢查：對縮點圖做拓撲排序，若某步可選節點 >1 則不滿足條件
3. 原理：若某層有兩個節點 A,B，則 A 不能到 B 也不能到 A（否則同層矛盾），後續分支永不可達

Tarjan 核心代碼

int dfn[MAXN], low[MAXN], bel[MAXN], stk[MAXN], top, idx, scc;
bool ins[MAXN];
void tarjan(int u) {
    dfn[u]=low[u]=++idx; stk[++top]=u; ins[u]=1;
    for (int e=head[u]; ~e; e=E[e].next) {
        int v=E[e].v;
        if (!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); }
        else if (ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]) {
        ++scc; int v;
        do { v=stk[top--]; bel[v]=scc; ins[v]=0; } while (v!=u);
    }
}

拓撲唯一性判斷

bool topo() {
    for (int step=0; step1) return false; // 多個入度0節點，非鏈狀
        for (int e=head1[u]; ~e; e=E1[e].next) deg[E1[e].v]--;
    }
    return true;
}

完整流程

• 讀入多組測試數據
• Tarjan 縮點，構建 SCC DAG（去重邊、計算入度）
• 拓撲排序檢查每層唯一性
• 輸出 "Yes" / "No"

關鍵洞察

「任意兩點單向可達」等價於「縮點 DAG 是一條哈密爾頓路徑」，進而等價於「拓撲序唯一」。這是本題最精妙的轉化。