拓扑排序

#include <iostream>
#include <queue>
using namespace std;
const int maxn=1000;

int head[maxn],cnt;
struct edge{
    int to,next,w;
}e[maxn*2];

void add_edge(int u,int v,int w){
    cnt++;
    e[cnt].next=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}

queue<int> q;
int in[maxn],p;        //in[]:入度  p:计数器/指针 
int topo[maxn];        //topo[]：拓扑序 
bool toposort(int n) {        //n为图中的节点数 
    for(int u=1;u<=n;u++)    //遍历所有节点出度 
    {
        if(!in[u])    //若入度==0，则放入队列 
        {
            q.push(u);    
        }
    }
    while(!q.empty())
    {
        int u=q.front();    //取出的节点顺序为topo序 
        q.pop();
        topo[++p]=u;
        if(p>n)    return false;    //若p>n，说明一定有环(拓扑序内的节点数一定与DAG中节点数相同) 
        for(int i=head[u];i;i=e[i].next) {    //链遍历 
            int v=e[i].to;    
            in[v]--;        //每一个与u相连的点入度-1 
            //work()    拓扑排序往往不只是单纯排序,可根据情况在此执行work[eg.拓扑上的DP] 
            if (!in[v])    //若v入度为0,则v入队 
            {
                q.push(v);
            } 
        }
    }
    if(p!=n)    return false;    //因为有可能一开始队列就是空的,所以再次特判 
    return true;
}

void output(int n){
    for(int i=1;i<=n;i++)
        cout<<topo[i]<<" ";
}

int main(){
    int n,m;
    int u,v,w;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        add_edge(u,v,1);
        in[v]++;        //加边的时候顺便初始化入度 
    }
    if(toposort(n))
        output(n);
    else cout<<"NO";
    return 0;
}