题解 用邻接表处理拓扑排序

#include <stdio.h>
#include <stdlib.h>
#define MAXS 2*100000+10

// 用邻接表是比较好的选择
typedef struct LinkTable{
   int data;
   struct LinkTable *next;
}LinkTable;


int main() {
    int m,n;
    scanf("%d%d\n",&n,&m);
    LinkTable tab[MAXS];
    // 初始化
    for(int i=1;i<=n;i++){
        tab[i].data=i;
        tab[i].next=NULL;
    }
    // 输入数据
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        LinkTable *p=&tab[x];
        while(p->next) p=p->next;
        p->next=(LinkTable *)malloc(sizeof(LinkTable));
        p->next->data=y;
        p->next->next=NULL;
    }
    int queue[n+2],que=1,front=1,du[n+1];
    for(int i=0;i<n+1;i++){
        du[i]=0;
    }
    // 统计度数
    for(int i=1;i<=n;i++){
        LinkTable *p=&tab[i];
        while(p->next) {
            p=p->next;
            du[p->data]++;
        }
    }
    // 挑出度为0的顶点
    for(int i=1;i<=n;i++) if(du[i]==0){queue[que++]=i;du[i]=-1;}
    // 出队度为0 并删除
    while(front!=que){
        int i=queue[front++];
        LinkTable *p=&tab[i];
        while(p->next) {
            p=p->next;
            du[p->data]--;
        }
        // 这一步大部分节省时间
       if(front==que)
        for(int j=1;j<=n;j++)if(du[j]==0){queue[que++]=j;du[j]=-1;}
    }
    // 当队列满了之后 说明获取到了所有顶点 没有剩余
    if(que==n+1) {
        printf("%d",queue[1]);
        for(int j=2;j<que;j++){
            printf(" %d",queue[j]);
        }
        return 0;
    }  
    printf("-1\n");
    return 0;
}