题解 | 【模板】拓扑排序

#include <stdio.h>
#include <stdlib.h>

#define MAXN 200000

// 定义边的结构体
typedef struct Edge {
    int to;
    struct Edge* next;
} Edge;

// 定义邻接表表头数组
Edge* adj[MAXN];
// 入度数组
int inDegree[MAXN];
// 拓扑排序结果数组
int topoOrder[MAXN];
// 队列数组
int queue[MAXN];

// 添加边到邻接表
void addEdge(int u, int v) {
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->to = v;
    newEdge->next = adj[u];
    adj[u] = newEdge;
    inDegree[v]++;
}

// 拓扑排序函数
int topologicalSort(int n) {
    int front = 0, rear = 0;
    // 将入度为 0 的节点入队
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            queue[rear] = i;
            rear++;
        }
    }
    int index = 0;
    while (front < rear) {
        int u = queue[front];
        front++;
        topoOrder[index] = u;
        index++;
        Edge* p = adj[u];
        while (p != NULL) {
            int v = p->to;
            inDegree[v]--;
            if (inDegree[v] == 0) {
                queue[rear] = v;
                rear++;
            }
            p = p->next;
        }
    }
    // 如果拓扑排序结果节点数不等于总节点数，说明图中有环
    return index == n;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    // 初始化邻接表和入度数组
    for (int i = 1; i <= n; i++) {
        adj[i] = NULL;
        inDegree[i] = 0;
    }
    // 读入边信息并添加到邻接表
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
    // 进行拓扑排序
    if (topologicalSort(n)) {
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                printf(" ");
            }
            printf("%d", topoOrder[i]);
        }
        printf("\n");
    } else {
        printf("-1\n");
    }
    // 释放邻接表内存
    for (int i = 1; i <= n; i++) {
        Edge* p = adj[i];
        while (p != NULL) {
            Edge* temp = p;
            p = p->next;
            free(temp);
        }
    }
    return 0;
}