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

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

#define MAX_NODES 200000

struct Node {
    int value;
    struct Node* next;
};

struct Graph {
    struct Node* adjList[MAX_NODES];
    int inDegree[MAX_NODES];
    int numNodes;
};

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

struct Graph* createGraph(int numNodes) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numNodes = numNodes;

    for (int i = 0; i < numNodes; ++i) {
        graph->adjList[i] = NULL;
        graph->inDegree[i] = 0;
    }

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;

    graph->inDegree[dest]++;
}

void enqueue(int queue[], int* rear, int node) {
    queue[(*rear)++] = node;
}

int dequeue(int queue[], int* front) {
    return queue[(*front)++];
}

int* topologicalSort(struct Graph* graph) {
    int* result = (int*)malloc(graph->numNodes * sizeof(int));
    int front = 0, rear = 0;
    int queue[MAX_NODES];
    int idx = 0;

    for (int i = 0; i < graph->numNodes; ++i) {
        if (graph->inDegree[i] == 0) {
            enqueue(queue, &rear, i);
        }
    }

    while (front != rear) {
        int currentNode = dequeue(queue, &front);
        result[idx++] = currentNode;

        struct Node* temp = graph->adjList[currentNode];
        while (temp != NULL) {
            int adjNode = temp->value;
            graph->inDegree[adjNode]--;
            if (graph->inDegree[adjNode] == 0) {
                enqueue(queue, &rear, adjNode);
            }
            temp = temp->next;
        }
    }

    if (idx != graph->numNodes) {
        free(result);
        return NULL; // Graph contains cycle
    }

    return result;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    struct Graph* graph = createGraph(n);

    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(graph, u - 1, v - 1);
    }

    int* result = topologicalSort(graph);
    if (result == NULL) {
        printf("-1\n");
    } else {
        for (int i = 0; i < n; ++i) {
            if (i == n - 1) {
                printf("%d", result[i] + 1);
            } else {
                printf("%d ", result[i] + 1);
            }
        }
        printf("\n");
        free(result);
    }

    return 0;
}