针对此问题，最稳健的解法是 Kahn 算法。该算法基于“入度 (In-degree)”这一关键图论概念，采用迭代的贪心思想。

核心思想

拓扑序的本质是“依赖消解”。

  1. 入度为 0 的节点：没有任何前驱节点指向它，意味着它没有任何未满足的依赖条件。因此，它可以安全地排在拓扑序列的当前最前端。
  2. 消解依赖：当我们把一个节点选入拓扑序列后，该节点“完成”了。此时，它可以从图中逻辑上“移除”，其发出的所有指向后续节点的边也随之失效。
  3. 状态更新：边的失效会导致其指向的邻接节点的入度减少。如果某个邻接节点的入度减为 0，说明该节点的所有依赖也已满足，可以进入待处理队列。

实现方法

选择 BFS (广度优先搜索) 范式作为实现载体。

  • 使用一个队列来维护当前所有“入度为 0”（即可执行）的节点。
  • 这种非递归的迭代方式避免了深搜 (DFS) 在极端链状数据下可能导致的栈溢出风险，且逻辑与“任务调度”的物理意义高度契合。

潜在陷阱

  • 环检测：算法不需要预先运行一个单独的环检测算法（如 DFS 找环），而应该在构造拓扑序的过程中动态感知环的存在。
  • 非连通图：图可能不是强连通甚至不是弱连通的（包含多个分散的子图）。算法必须能够处理森林（Forest）结构，确保覆盖所有顶点。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);
    vector<int> deg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        deg[v]++;
    }

    vector<int> res;
    res.reserve(n);
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        int u = Q.front();
        res.push_back(u);
        Q.pop();
        for (int v : adj[u]) {
            deg[v]--;
            if (deg[v] == 0) {
                Q.push(v);
            }
        }
    }

    if (res.size() < n) {
        cout << "-1\n";
    } else {
        for (int i = 0; i < res.size(); i++) {
            cout << res[i];
            cout << (i == res.size() - 1 ? "\n" : " ");
        }
    }
}