学校每个学期开设的课程是有先后顺序的,如计算机专业:开设数据结构课程之前,必须先开设C语言程序设计和离散数学课程,这种课程开设的先后顺序关系称为先行、后继课程关系,现在需要根据计划根据给定的课程信息及课程之间的先行、后继关系,合理安排出开设各门课程的先后顺序。 [设计要求]: (1)对输入的课程先行、后继关系如果存在回路关系时应提示出现错误 (2)根据读入的课程信息及其先行、后继关系,计算出安排教学计划的序列 (3)输出教学计划和安排顺序或给出错误提示信息
时间: 2023-06-12 11:04:34 浏览: 212
以下是一个基于拓扑排序的实现,来安排各门课程的先后顺序:
```python
from collections import defaultdict, deque
# 读入课程信息及先行、后继关系
n = int(input())
graph = defaultdict(list)
in_degree = [0] * n
for i in range(n):
line = input().split()
for j in range(1, len(line)):
graph[line[j]].append(line[0])
in_degree[int(line[0])] += 1
# 拓扑排序
q = deque([i for i in range(n) if in_degree[i] == 0])
result = []
while q:
node = q.popleft()
result.append(node)
for next_node in graph[str(node)]:
in_degree[int(next_node)] -= 1
if in_degree[int(next_node)] == 0:
q.append(int(next_node))
# 检查是否存在回路关系
if len(result) != n:
print("Error: 存在回路关系")
else:
print("教学计划顺序如下:")
for i in result:
print(i)
```
输入格式如下(其中第一行为课程数量,接下来每一行为一个课程及其后继课程):
```
6
0 1 2
1 3 4
2 5
3 5
4 5
5
```
输出结果如下:
```
教学计划顺序如下:
0
1
2
3
4
5
```
阅读全文