提交时间:2022-08-01 20:37:02

运行 ID: 56412

#include<bits/stdc++.h> using namespace std; const int maxn=500; vector<int> graph[maxn]; int inDegree[maxn]; vector<int> TopoSort(int n){ vector<int> topology; priority_queue<int,vector<int>,greater<int> > q; for(int i=1;i<=n;i++){ if(inDegree[i]==0){ q.push(i); } } while(!q.empty()){ int u=q.top(); q.pop(); topology.push_back(u); for(int i=0;i<graph[u].size();i++){ int v=graph[u][i]; inDegree[v]--; if(inDegree[v]==0){ q.push(v); } } } return topology; } int main(){ int n,m; while(cin>>n>>m){ memset(graph,0,sizeof graph); memset(inDegree,0,sizeof inDegree); for(int i=0;i<m;i++){ int from,to; cin>>from>>to; graph[from].push_back(to); inDegree[to]++; } vector<int> v=TopoSort(n); for(int i=0;i<v.size();i++){ if(i==0){ cout<<v[i]; }else{ cout<<" "<<v[i]; } } } return 0; }