使用完整的c语言实现: 课程表 Description 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习?如果可以,输出1 ;否则,输出 -1 。 Input 第一行为一个整数,numCourses 接下来 2 *numCourses行表示课程n,和其有多少先修课程以及每一个先修课程是什么 0 < numCourses <= 1000 0 < len(prerequisites) <= 100 Output 若其可以完成所有课程的学习,如果可以,输出1 ;否则,输出 -1 。 Sample Input 1 2 1 1 0 0 1 1 Sample Output 1 -1 Sample Input 2 3 0 2 1 2 1 1 2 2 0 Sample Output 2 1
时间: 2023-12-03 13:44:00 浏览: 37
以下是使用 C 语言实现的代码:
```c
#include <stdio.h>
#define MAX_NUM_COURSES 1000
int main() {
int numCourses, n, m, i, j;
int indegrees[MAX_NUM_COURSES] = { 0 };
int graph[MAX_NUM_COURSES][MAX_NUM_COURSES] = { 0 };
scanf("%d", &numCourses);
for (i = 0; i < numCourses; i++) {
scanf("%d %d", &n, &m);
indegrees[n] = m;
for (j = 0; j < m; j++) {
int pre;
scanf("%d", &pre);
graph[pre][n] = 1;
}
}
int count = 0;
for (i = 0; i < numCourses; i++) {
int flag = 0;
for (j = 0; j < numCourses; j++) {
if (indegrees[j] == 0) {
flag = 1;
break;
}
}
if (flag == 0) {
printf("-1\n");
return 0;
}
indegrees[j] = -1;
for (int k = 0; k < numCourses; k++) {
if (graph[j][k] == 1) {
indegrees[k]--;
}
}
count++;
}
printf("%d\n", (count == numCourses) ? 1 : -1);
return 0;
}
```
具体思路是,先将每门课程的入度(即需要学习它的先修课程数量)和它的先修课程所在的位置在邻接矩阵中标记出来。然后循环执行以下操作:找到入度为 0 的课程,将它的入度标记为 -1,然后将它的后继课程的入度减 1。这个过程可以用一个 indegrees 数组来实现。如果找不到入度为 0 的课程,说明存在环,无法完成所有课程学习,返回 -1。最终判断是否完成了所有课程的学习,即 count 是否等于 numCourses。