問題描述

N 頭牛（N≤100），M 場比賽結果（M≤4500），A B 表示 A 勝 B。技能值唯一且可傳遞（A>B, B=C ⇒ A>C）。求能唯一確定排名的牛的數量（即與其他所有 N-1 頭牛關系均已知）。

解題思路

1. 連通性檢查：若圖不連通（存在孤立分量），則無牛能被唯一確定，直接輸出 0。用並查集維護連通分量。
2. 拓撲排序唯一性：在連通圖中，若拓撲排序過程中每一步都只有唯一一個入度為 0 的節點，則該節點排名確定。統計這類節點數量。

算法流程

1. 讀入邊，構建鄰接矩陣/表，統計入度，並查集合併。
2. 檢查並查集根節點數 > 1 → 輸出 0。
3. 拓撲排序：隊列存入度 0 節點。
   若隊列大小 > 1 → 當前步驟有多個選擇，排名不唯一。
   彈出唯一節點，更新鄰居入度，新入度 0 入隊。
   統計「隊列大小始終為 1」的步驟數 = 可確定排名的牛數。

代碼實現

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN = 105;
bool g[MAXN][MAXN];
int in[MAXN], fa[MAXN];
int n, m;

int find(int x) { return fa[x]==x ? x : fa[x]=find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = find(y); }

int topo() {
    queue q;
    for (int i=1;i<=n;++i) if (in[i]==0) q.push(i);
    int determined = 0;
    while (!q.empty()) {
        if (q.size() > 1) return determined; // 不唯一，後續也無法確定
        int u = q.front(); q.pop();
        ++determined;
        for (int v=1; v<=n; ++v) if (g[u][v]) {
            if (--in[v] == 0) q.push(v);
        }
    }
    return determined;
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        memset(g, 0, sizeof(g));
        memset(in, 0, sizeof(in));
        for (int i=1;i<=n;++i) fa[i]=i;
        
        for (int i=0;i 1) { puts("0"); continue; }
        
        printf("%d\n", topo());
    }
    return 0;
}

關鍵細節

1. 重邊去重：if (!g[a][b]) 避免重複計入入度。
2. 並查集僅判連通：不需維護大小/秩，N≤100 路徑壓縮足夠。
3. 拓撲排序提前終止：一旦隊列大小 > 1，後續節點排名均不唯一，直接返回已確定數。
4. 鄰接矩陣：N≤100，O(N²) 掃描鄰居可接受；大圖應用鄰接表。

複雜度

• 時間：O(N² + M) ≈ 10000 + 4500，極快。
• 空間：O(N²) ≈ 10KB。

總結

POJ 3660 結合並查集（判連通）與拓撲排序（判唯一性）解決「排名確定性」問題。關鍵洞察：

1. 不連通 ⇒ 無法比較跨分量牛 ⇒ 全部不確定。
2. 連通圖中，拓撲排序每步唯一選擇 ⇔ 該節點與所有其他節點關系已確定（因拓撲序唯一）。
3. 拓撲排序過程中出現多個入度 0 節點，說明這些節點之間無直接/間接邊，相對順序不定。

此模板適用於所有「偏序關系中可確定順序的元素計數」問題。