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

邻接矩阵+入度

队列存放入度为0的结点

循环：取出队头，更新相应入度，入度为0的结点入队

检查出队元素个数即可判断是否为DAG

若对拓扑排序的顺序有要求，将队列加强为优先队列即可

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

const int maxn=200001;

vector<int>graph[maxn];//DAG的邻接矩阵
int degree[maxn];//结点入度

vector<int> topologicalsort(int n){//拓扑排序
    vector<int>ans;
    queue<int>myqueue;
    for(int i=1;i<=n;i++){//初始结点
        if(degree[i]==0){
            myqueue.push(i);
        }
    }
    while(!myqueue.empty()){
        int next=myqueue.front();
        ans.push_back(next);
        myqueue.pop();
        for(int i=0;i<graph[next].size();i++){
            int v=graph[next][i];
            degree[v]--;
            if(degree[v]==0)myqueue.push(v);
        }
    }
    return ans;
}

int main() {
    int n, m;
    while (scanf("%d%d",&n,&m)!=EOF) { 
        memset(graph,0,sizeof(graph));//初始化
        fill(degree,degree+n+1,0);

        while(m--){
            int from,to;
            scanf("%d%d",&from,&to);
            graph[from].push_back(to);
            degree[to]++;
        }
    
        vector<int>ans=topologicalsort(n);
        if(ans.size()<n)printf("-1\n");
        else{
             for(int i=0;i<ans.size();i++){
            if(i==0)printf("%d",ans[i]);
            else printf(" %d",ans[i]);
        }
        printf("\n");
        }
       
    }
    return 0;
}