用c语言 利用拓扑关系制定课程表

下面是一个 C 语言代码示例：

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

#define MAX_COURSES 1000

int make_course_schedule(int num_courses, int prerequisites[][2], int course_schedule[]) {
    // 将课程之间的先修关系转化为有向图表示
    int graph[MAX_COURSES][MAX_COURSES] = {0};
    int in_degree[MAX_COURSES] = {0};
    for (int i = 0; i < num_courses; i++) {
        graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
        in_degree[prerequisites[i][0]]++;
    }

    // 将所有入度为 0 的节点加入队列
    int q[MAX_COURSES], front = 0, rear = -1;
    for (int i = 0; i < num_courses; i++) {
        if (in_degree[i] == 0) {
            q[++rear] = i;
        }
    }

    // 拓扑排序
    int count = 0;
    while (front <= rear) {
        int node = q[front++];
        course_schedule[count++] = node;

        // 将所有以该节点为起点的有向边删去
        for (int neighbor = 0; neighbor < num_courses; neighbor++) {
            if (graph[node][neighbor] == 1) {
                in_degree[neighbor]--;
                if (in_degree[neighbor] == 0) {
                    q[++rear] = neighbor;
                }
            }
        }
    }

    // 判断是否存在环路
    if (count == num_courses) {
        return count;
    } else {
        return -1;
    }
}

int main() {
    int num_courses = 4;
    int prerequisites[4][2] = {{1,0},{2,0},{3,1},{3,2}};
    int course_schedule[MAX_COURSES];

    int count = make_course_schedule(num_courses, prerequisites, course_schedule);
    if (count == -1) {
        printf("There is a cycle in the prerequisites.\n");
    } else {
        printf("The course schedule is: ");
        for (int i = 0; i < count; i++) {
            printf("%d ", course_schedule[i]);
        }
        printf("\n");
    }

    return 0;
}

其中，`num_courses` 表示总课程数，`prerequisites` 是一个二维数组，表示课程之间的先修关系。函数返回制定的课程表顺序数量，如果无法制定课程表，则返回 -1。

例如，对于以下输入：

int num_courses = 4;
int prerequisites[4][2] = {{1,0},{2,0},{3,1},{3,2}};
int course_schedule[MAX_COURSES];

则输出为：

The course schedule is: 0 1 2 3