题解 | #【模板】拓扑排序#

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

class Graph{
    public:
    vector<int> in;//入度数组
    vector<vector<int>> out;//出度二维数组
    vector<int> res; //输出队列
    Graph(int n){
    in.resize(n);
    for(int i=0;i<n;i++){ 
        out.push_back(vector<int>());
    }
    }
    bool topologicalSort(){
        deque<int> deq;
        for(int i=0;i<in.size();i++){
            if(in.at(i)==0)
                //入度为零入队
                deq.push_back(i);
        }
        while(!deq.empty()){
            //删除一个队中入度为0点u
            int u=deq.front();deq.pop_front();
            ////删除后进入输出队
            res.push_back(u+1);
            for(int j=0;j<out.at(u).size();j++){
                int v=out.at(u).at(j);
                //u的所有后继节点v入度-1
                in[v]--;
                if(in[v]==0)
                    //v成为新的入度为0点
                    deq.push_back(v);
            }
            //删除邻接表中的u,因为后继节点入度已经处理
            out.at(u).clear();
        }
        //num数等于节点数，不存在环;
        return res.size()==in.size();
    }
};

int main()
{
    int n,m;
    cin >> n >> m;
    Graph graph(n);
    for(int i = 0; i < m; ++i)
    {
        int from, to;
        cin >> from;
        cin >> to;
        //出现一次to,to入度+1(入度即前趋节点数)
        graph.in.at(to-1)++;
        //from点增加出度(邻接表长度)
        graph.out.at(from-1).push_back(to-1);
    }
    if(graph.topologicalSort())
    {
        for(int i = 0; i < n; ++i)
        {
            cout << graph.res.at(i);
            if(i != n - 1) cout << ' ';
        }
    }
    else
    {
        cout << -1;
    }
}