题解 | 【模板】拓扑排序

#include <iostream>
#include<unordered_map>
#include<vector>
#include<queue>
using namespace std;

// 注意 while 处理多个 case
        //directed acyclic diagram才有拓扑序
        //已经确定有向，则判断有没有环
        //任意有向无环图（DAG）都至少有一个入度为 0 的顶点。
        //反过来，如果在“剪枝”某一步没有任何入度为 0 的顶点，却仍有未处理的顶点，说明剩下的子图必有环。



int main() {
    int n,m;
    std::cin>>n>>m;
    std::vector<int> in(n+1,0);
    std::vector<std::vector<int>> router(n+1);
    //先记录入度与路由表
    int a,b;
    while(std::cin>>a>>b)
    {
        in[b]++;
        router[a].push_back(b);
    }
    //处理0入度节点
    std::queue<int> q;
    for(int i=1;i<in.size();i++)
    {
        if(in[i]==0) q.push(i);//记录符合要求的顶点
    }
    std::vector<int> topo;
    //通过0入度节点扩散检查
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        topo.push_back(u);
        for(int j=0;j<router[u].size();j++)
        {
            if(--in[router[u][j]]==0) q.push(router[u][j]);
        }
    }
    //检查是否有剩余节点
 if (topo.size() == (size_t)n) {
        for (int i = 0; i < n; ++i) {
            cout << topo[i] << (i+1 < n ? ' ' : '\n');
        }
    } else {
        cout << -1 << '\n';
    }


}
// 64 位输出请用 printf("%lld")