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

#include <stdio.h>
#include <stdlib.h>
// MAX为无穷
typedef struct arcnode
{
    int adjvex;
    struct arcnode*next;
}arcnode;
typedef struct
{
    int in;
    arcnode*first;
}vertex;
int main() {
    int n, m,i,j,a,b;
    int top=0;
    int k=0;
    int top2=0;
    int front=0;
    scanf("%d%d",&n,&m);
    vertex vertexs[n+1];
    for(i=0;i<n+1;i++)
    {
        vertexs[i].in=0;
        vertexs[i].first=NULL;
    }
    for(i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        vertexs[b].in++;
        arcnode*p=(arcnode*)malloc(sizeof(arcnode));
        p->adjvex=b;
        p->next=vertexs[a].first;
        vertexs[a].first=p;
    }
    int gettop[n];
    int stack[n+1];
    for(i=1;i<n+1;i++)
    {
        if(vertexs[i].in==0)
        {
            stack[top++] =i;
            
        }
    }
    while(top!=front)
    {

        int k= gettop[top2++]=stack[front++];
    //  printf("%d ",k);
    //  printf("%d ",gettop[top2]);
        arcnode*q=vertexs[k].first;
        while(q!=NULL)
        {
            vertexs[q->adjvex].in--;
            if(vertexs[q->adjvex].in==0)
            {
                stack[top++]=q->adjvex;
            }
            q=q->next;
        }
    
    }
    if(top2==n)
    {
        for(i=0;i<n-1;i++)
        {
            printf("%d ",gettop[i]);
        }
        printf("%d",gettop[n-1]);
        printf("\n");
    }
    else {
    printf("%d",-1);
    }
    return 0;
}