POJ 2762：Tarjan 縮點 + 判斷縮點圖是否為單鏈

問題描述

給定有向圖，判斷是否存在一條路徑經過所有強連通分量（SCC）恰好一次（即縮點後的 DAG 是否為一條單鏈：所有節點入度 ≤ 1、出度 ≤ 1，且從唯一入度 0 點出發能遍歷所有節點）。

解法框架：Tarjan + 縮點圖拓撲性質檢查

1. Tarjan 算法求強連通分量

• 標準 Tarjan：dfn 時間戳、low 最早可達祖先、棧 qq、instack 標記。
• 遞歸 tarjan(x)，low[x] == dfn[x] 時彈棧形成一個 SCC，標記 shuyu[y] = nums（分量編號）。
• 得到 nums 個分量（編號 1~nums-1）。

2. 構建縮點圖並統計度

• 遍歷原圖邊 (u,v)，若 shuyu[u] != shuyu[v]，在縮點圖加邊 (shuyu[u], shuyu[v])。
• 統計每個分量的入度 id[] 和出度 od[]。

3. 判斷單鏈條件

1. 入度 0 的分量有且僅有 1 個（起點），出度 0 的分量有且僅有 1 個（終點）。否則 No。
2. 從入度 0 的分量出發 DFS，求最長路徑長度（節點數）。若最長路徑節點數 == 總分量數（nums-1），則為單鏈，輸出 Yes；否則 No。

代碼關鍵結構

struct gra {
    struct list { int u,v,next; } edge[maxm];
    int head[maxn], vis[maxn], num, n;
    int id[maxn], od[maxn], shuyu[maxn], nums;
    int dfn[maxn], low[maxn], times, instack[maxn];
    stack qq;
    void init() { memset(head,-1,sizeof(head)); ... num=0; nums=1; times=1; }
    void add(int u,int v) { edge[num]={u,v,head[u]}; head[u]=num++; }
    void tarjan(int x) { ... } // 標準 Tarjan
    void start() { for(i=1..n) if(!dfn[i]) tarjan(i); }
    int dfs(int x,int p) { // 求最長路徑節點數
        int mm=p;
        for(i=head[x]; i!=-1; i=edge[i].next)
            mm=max(mm, dfs(edge[i].v, p+1));
        return mm;
    }
} G, g; // G 原圖, g 縮點圖

int main() {
    int T; scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        G.init(); g.init(); G.n=n;
        for(i=1..m) { scanf("%d%d",&a,&b); G.add(a,b); }
        G.start(); // Tarjan 縮點
        g.n = G.nums;
        // 構建縮點圖、統計度
        for(i=1..G.n) for(j=G.head[i]; j!=-1; j=G.edge[j].next) {
            u=G.edge[j].u; v=G.edge[j].v;
            if(G.shuyu[u]==G.shuyu[v]) continue;
            G.id[G.shuyu[v]]++; G.od[G.shuyu[u]]++;
            g.add(G.shuyu[u], G.shuyu[v]);
        }
        // 檢查入度出度
        nin=nout=0;
        for(i=1; i1 || nout>1) { puts("No"); continue; }
        // 找入度0的點
        for(i=1; i

複雜度分析

Tarjan：O(n + m)。
構建縮點圖：O(m)。
DFS 求最長路：縮點圖為 DAG，O(V+E) ≤ O(n+m)。
總體 O(n + m)，n ≤ 1100, m ≤ 10000 極快。


關鍵細節

縮點圖去重邊：代碼未顯式去重，但入度/出度統計與 DFS 邏輯不受重邊影響（重邊只會多加幾次相同遞歸，不影響最長路節點數計算）。
DFS 參數：dfs(x, p) 中 p 為當前路徑節點數，返回以 x 為起點的最長路徑節點數。
分量編號：nums 從 1 開始遞增，總分量數 = nums - 1。


總結
POJ 2762 是「Tarjan 縮點 + 縮點圖結構判斷」的經典組合：

用 Tarjan 將圖壓縮為 DAG。
利用 DAG 的度性質（入度/出度 ≤ 1）快速排除非鏈結構。
從唯一源點 DFS 驗證是否能遍歷所有節點（即為單鏈）。

此模式廣泛適用於「判斷有向圖是否為鏈/環/樹」等結構性質問題。