BZOJ 1093 ZJOI2007 最大半連通子圖：Tarjan 縮點 + 拓撲 DP

題目轉化

半連通子圖定義：誘導子圖中任意兩點 u, v，至少有一條方向路徑連通 (u→v 或 v→u)。等價於：縮點後的 DAG 中，節點構成一條**鏈** (任意兩點可達)。故問題轉為：**在縮點後的 DAG 中找最長路徑 (點權為強連通分量大小) 及其方案數**。

解題步驟

1. Tarjan 算法 求強連通分量 (SCC)，縮點建立 DAG。每個 SCC 內部任兩點互達，視為一個超級節點，權重 = 內部節點數。
2. 去重建邊：縮點後不同 SCC 間可能有多條平行邊，需去重 (用 set 或排序唯一化)。
3. 拓撲序 DP：按拓撲逆序 (或正序) DP。
   len[u] = 以 u 為起點的最大權重和。
   ways[u] = 對應方案數 (模 p)。
   轉移：len[u] = max(len[u], len[v] + size[u])，v 為 u 的出邊鄰居。
   方案數合併時取模加和。
4. 全域答案：遍歷所有節點，取最大 len 及對應 ways 總和。

關鍵代碼片段

Tarjan 縮點

void Tarjan(int x) {
    dfn[x] = low[x] = ++timer;
    stk[++top] = x; inStack[x] = true;
    for (int e = head[x]; e; e = nxt[e]) {
        int y = to[e];
        if (inStack[y]) low[x] = min(low[x], dfn[y]);
        else if (!dfn[y]) { Tarjan(y); low[x] = min(low[x], low[y]); }
    }
    if (dfn[x] == low[x]) {
        ++sccCnt;
        do { int y = stk[top--]; inStack[y] = false; belong[y] = sccCnt; size[sccCnt]++; } while (y != x);
    }
}

拓撲 DP (逆序)

for (int u = sccCnt; u >= 1; --u) { // 假設節點編號即拓撲逆序
    len[u] = size[u]; ways[u] = 1;
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (len[v] + size[u] > len[u]) { len[u] = len[v] + size[u]; ways[u] = 0; }
        if (len[v] + size[u] == len[u]) ways[u] = (ways[u] + ways[v]) % mod;
    }
    // 更新全域答案
}

複雜度

• Tarjan：O(N + M)
• 去重建邊：O(M log M) (用 set) 或 O(M) (排序唯一化)
• DP：O(N + M)
• 總計：O(N + M log M) 或 O(N + M)，滿足 N ≤ 1e5, M ≤ 1e6。

易錯點提醒

• 縮點後邊方向：原邊 u->v，縮點後 belong[u] -> belong[v] (若不同 SCC)。
• 方案數取模：每次加法都要 % mod。
• 拓撲序獲取：可在 Tarjan 時記錄縮點圖的入度，再 BFS 拓撲排序；或利用 SCC 編號的反序性質 (Tarjan 產生的 SCC 編號本身是拓撲逆序)。