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

#include <stdio.h>
#include <stdlib.h>
typedef struct Edge {
    int index;
    struct Edge* next;
} edge;

typedef struct {
    int in;
    int data;
    edge* firstedge;
} node;

typedef struct {
    node vertex[200010];
    int n, m;
} graph;

void insert(graph* G, int a, int b) {
    edge* s = (edge*)malloc(sizeof(edge));
    int index_a = a-1;
    s->index = b-1;
    s->next = G->vertex[index_a].firstedge;
    G->vertex[index_a].firstedge = s;
    G->vertex[s->index].in++;
}

typedef struct {
    int data[200010];
    int top, rear;
} que;


int pop(que* q) {
    //printf("%d", q->data[q->top]);
    int e = q->data[q->top];
    q->top++;
    return e;
}

void push(que* q, int x) {
    q->data[q->rear] = x;
    ++q->rear;
}

int main() {
    int a, b, n, m;
    scanf("%d %d", &n, &m);
    graph* G = (graph*)malloc(sizeof(graph));
    G->n = n;
    G->m = m;
    //int i = 0;
    int count = 0;
    for (int l = 0; l < n; l++) {
        G->vertex[l].data = l + 1;
        G->vertex[l].in = 0;
        G->vertex[l].firstedge = NULL;
    }
    while (scanf("%d %d", &a, &b) != EOF) { // 注意 while 处理多个 case
        insert(G, a, b);
    }
    que* q = (que*)malloc(sizeof(que));
    q->top = q->rear = 0;
    // printf("序号 入度 值 第一条边\n");
    // for (int j = 0; j < n; j++) {
    //     printf("  %d     %d   %d   ",j, G->vertex[j].in, G->vertex[j].data);
    //     if (G->vertex[j].firstedge!=NULL) {
    //         printf("%d\n",G->vertex[j].firstedge->index);
    //     }
    // }
    int *ans=(int *)malloc(sizeof(int)*n);//最终输出数组
    for (int j = 0; j < n; j++) {//入度为0入队列
        if (G->vertex[j].in == 0) {
            push(q, j);
        }
    }
    while (q->top != q->rear) {
        ans[count]=pop(q);//出队
        int index_tmp = ans[count];
        count++;
        while (G->vertex[index_tmp].firstedge != NULL) {//查找出栈顶的元素关联的边
            int k = G->vertex[index_tmp].firstedge->index;
            G->vertex[k].in--;//入度减一
            if (G->vertex[k].in == 0) {//判断减一后是否等于0，若等于0入栈
                push(q, k);
            }
            G->vertex[index_tmp].firstedge=G->vertex[index_tmp].firstedge->next;
            // //删除链表中的边
            // edge* e = G->vertex[index_tmp].firstedge;
            // edge* tmpe = e->next;
            // free(e);
            // e = tmpe;
            // G->vertex[index_tmp].firstedge = e; 
        }
    }
    if (count != n) {
        printf("-1");
    }else {
        for (int v=0; v<count; v++) {
            printf("%d",ans[v]+1);
            if (v != n-1) {
                printf(" ");
            }
        }
    }
    return 0;
}