拓撲排序模板：Kahn 算法 C++ 通用實現（含唯一性/環判斷）

適用場景

• 有向圖拓撲排序。
• 判斷拓撲序是否唯一（隊列大小 > 1 即不唯一）。
• 判斷圖中是否有環（排序節點數 < 總節點數）。

核心代碼（鄰接表 + 隊列）

// 拓撲排序通用模板
// 返回值：-1=有環, 0=可排序但不唯一, 1=唯一拓撲序
// seq 輸出拓撲序（若有環則為部分序列）
int topoSort(int n, const vector>& adj, vector& seq) {
    vector indeg(n, 0);
    for (int u = 0; u < n; ++u)
        for (int v : adj[u]) ++indeg[v];
    queue q;
    for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
    bool multiple = false;
    while (!q.empty()) {
        if (q.size() > 1) multiple = true;
        int u = q.front(); q.pop();
        seq.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
    }
    if ((int)seq.size() < n) return -1; // 有環
    return multiple ? 0 : 1;
}

完整可運行示例（POJ 1094 風格）

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m, n || m) {
        vector> adj(n);
        vector> edges;
        string rel;
        int determined = -1, inconsistent = -1;
        vector finalSeq;
        for (int i = 0; i < m; ++i) {
            cin >> rel;
            int u = rel[0] - 'A', v = rel[2] - 'A';
            edges.emplace_back(u, v);
            if (determined != -1 || inconsistent != -1) continue;
            // 重建圖
            adj.assign(n, {});
            for (auto &e : edges) adj[e.first].push_back(e.second);
            vector seq;
            int res = topoSort(n, adj, seq);
            if (res == -1) inconsistent = i + 1;
            else if (res == 1) { determined = i + 1; finalSeq = seq; }
        }
        if (determined != -1) {
            cout << "Sorted sequence determined after " << determined << " relations: ";
            for (int x : finalSeq) cout << char('A' + x);
            cout << ".\n";
        } else if (inconsistent != -1) {
            cout << "Inconsistency found after " << inconsistent << " relations.\n";
        } else {
            cout << "Sorted sequence cannot be determined.\n";
        }
    }
    return 0;
}

DFS 版拓撲排序（備選）

// 返回 false 表示有環
bool dfsTopo(int u, const vector>& adj, vector& state, vector& seq) {
    state[u] = 1; // 訪問中
    for (int v : adj[u]) {
        if (state[v] == 1) return false; // 回邊 → 環
        if (state[v] == 0 && !dfsTopo(v, adj, state, seq)) return false;
    }
    state[u] = 2; // 訪問完
    seq.push_back(u);
    return true;
}

// 調用
vector state(n, 0), seq;
for (int i = 0; i < n; ++i)
    if (state[i] == 0 && !dfsTopo(i, adj, state, seq)) { /* 有環 */ }
reverse(seq.begin(), seq.end()); // 反序即拓撲序

選型建議

總結

拓撲排序是有向圖基礎算法。掌握 Kahn 模板（入度+隊列）+ 唯一性判斷（隊列大小）+ 環判斷（節點計數），覆蓋 99% 競賽與面試場景。代碼放入個人模板庫，隨取隨用。