题解 | #比赛名次#

拓扑排序（已知为DAG）：邻接矩阵+入度，优先队列保证序号小的排前面

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

const int maxn=501;

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

vector<int> topologicalsort(int n){//拓扑排序
    vector<int>ans;
    priority_queue< int,vector<int>,greater<int> >myqueue;//越小优先级越高
    for(int i=1;i<=n;i++){//初始结点
        if(degree[i]==0){
            myqueue.push(i);
        }
    }
    while(!myqueue.empty()){
        int next=myqueue.top();
        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);
        for(int i=0;i<ans.size();i++){
            if(i==0)printf("%d",ans[i]);
            else printf(" %d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}