POJ Popular Cows：Tarjan 強連通分量縮點 + 出度為零判斷

題目大意

有 N（≤10,000）頭牛，M（≤50,000）對有序關係 (A, B) 表示 A 認為 B 受歡迎。關係可傳遞。求被所有牛認為受歡迎的牛的數量。

解題思路

1. 建圖：有向邊 A → B。
2. Tarjan 算法求強連通分量（SCC），縮點得到 DAG。
3. 在縮點圖中，若存在唯一出度為 0 的強連通分量，則該分量內所有牛被所有牛可達（即被所有牛認為受歡迎），答案為該分量大小；否則答案為 0。

代碼實現

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

struct Edge { int to, next; } e[N*10];
int head[N], e_cnt;
int dfn[N], low[N], stk[N], top, idx, scc_cnt;
int bel[N], scc_sz[N], out_deg[N];
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;
            bel[v] = scc_cnt;
            ++scc_sz[scc_cnt];
        } while (v != u);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; 
    while (cin >> 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);
        fill(out_deg, out_deg+n+1, 0); fill(scc_sz, scc_sz+n+1, 0);
        idx = top = scc_cnt = 0;
        for (int i = 0; i < m; ++i) {
            int a, b; cin >> a >> b;
            add_edge(a, b);
        }
        for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
        for (int u = 1; u <= n; ++u)
            for (int i = head[u]; ~i; i = e[i].next) {
                int v = e[i].to;
                if (bel[u] != bel[v]) out_deg[bel[u]]++;
            }
        int zero_cnt = 0, ans_scc = 0;
        for (int i = 1; i <= scc_cnt; ++i)
            if (out_deg[i] == 0) { ++zero_cnt; ans_scc = i; }
        cout << (zero_cnt == 1 ? scc_sz[ans_scc] : 0) << '\n';
    }
    return 0;
}

複雜度

• Tarjan：O(N + M)。
• 縮點後統計出度：O(M)。
• 總時間：O(N + M)，空間 O(N + M)。

關鍵點

• 傳遞性 → 強連通分量內任意兩點互達。
• 縮點後 DAG 中出度為 0 的分量若唯一，則所有點最終可達該分量。
• 若有多個出度為 0 的分量，它們互不可達，無牛被所有牛認可。