确定比赛名次 HDU - 1285(topo模板题)

确定比赛名次 HDU - 1285

题意：

给你m条边，要求你进行topo排序。

思路：

1. 没当in【i】==0，即满足条件
2. 编号小的在前面，可以通过优先队列来维护（数据小当然也可以直接暴力）

AC

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
using namespace std;
const int maxn=500+10;
priority_queue<int>q;
vector<int>e[maxn];
int n,m,in[maxn];
vector<int>ans;
void topo(){
    while(!q.empty()){
    int u=-q.top();q.pop();ans.push_back(u);for(auto v:e[u]){
    if(in[v]==0)continue;in[v]--;if(in[v]==0)q.push(-v);}}
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);while(cin>>n>>m){
    ans.clear();while(!q.empty())q.pop();int u,v;For(i,1,n)in[i]=0,e[i].clear();For(i,1,m){
    cin>>u>>v;e[u].push_back(v);in[v]++;}For(i,1,n)if(in[i]==0)q.push(-i);topo();for(int i=0; i<n; i++){
    if(i!=0)cout<<' ';cout<<ans[i];}cout<<endl;}return 0;
}