POJ 1236 Network of Schools：強連通分量縮點求最少啟動學校數

給定有向圖，求：(1) 至少選幾個節點使能到達所有節點；(2) 至少加幾條邊使圖強連通。經典強連通分量（SCC）縮點拓撲圖應用。

解題步驟

1. Tarjan 算法求 SCC，得到 sccno[u] 及 scc_cnt
2. 縮點建 DAG：SCC 間有邊則連接，統計入度為 0 的 SCC 數 ans1，出度為 0 的 SCC 數 ans2
3. 答案 1：ans1（需從每個入度 0 的 SCC 起始）
4. 答案 2：max(ans1, ans2)（加邊連接入度 0 與出度 0 的 SCC）
5. 特殊情況：若 scc_cnt == 1，輸出 1 和 0

核心代碼

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
const int maxn = 110;
vector G[maxn], G1[maxn], RG1[maxn];
int n, low[maxn], pre[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack S;

void dfs(int u) {
    low[u] = pre[u] = ++dfs_clock;
    S.push(u);
    for (int v : G[u]) {
        if (!pre[v]) { dfs(v); low[u] = min(low[u], low[v]); }
        else if (!sccno[v]) low[u] = min(low[u], pre[v]);
    }
    if (low[u] == pre[u]) {
        scc_cnt++;
        while (true) {
            int x = S.top(); S.pop();
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void build_DAG() {
    for (int i=1; i<=scc_cnt; i++) { G1[i].clear(); RG1[i].clear(); }
    for (int u=1; u<=n; u++)
        for (int v : G[u]) {
            int s = sccno[u], t = sccno[v];
            if (s != t) { G1[s].push_back(t); RG1[t].push_back(s); }
        }
}

void work() {
    int ans1=0, ans2=0;
    for (int i=1; i<=scc_cnt; i++) if (RG1[i].empty()) ans1++;
    for (int i=1; i<=scc_cnt; i++) if (G1[i].empty()) ans2++;
    if (scc_cnt == 1) { printf("1\n0\n"); return; }
    printf("%d\n%d\n", ans1, max(ans1, ans2));
}

int main() {
    int x;
    while (scanf("%d", &n) != EOF) {
        for (int i=1; i<=n; i++) G[i].clear();
        for (int i=1; i<=n; i++) {
            while (scanf("%d", &x), x) G[i].push_back(x);
        }
        memset(pre,0,sizeof(pre)); memset(sccno,0,sizeof(sccno));
        dfs_clock = scc_cnt = 0;
        for (int i=1; i<=n; i++) if (!pre[i]) dfs(i);
        build_DAG(); work();
    }
    return 0;
}

易錯點

• 忘記處理 scc_cnt==1 導致 WA（樣例即此情況）
• 縮點建圖時需去重（本題數據無重邊，實際可用 set 或標記數組去重）

SCC 縮點是有向圖達達性問題的核心工具，本題是模板級應用。