根据输入,输出有向图的拓扑排序序列。并画出有向图。输入: 6,5,1 0,1 1,2 2,3 4,1 4,5 -1,-1
时间: 2023-08-20 14:07:20 浏览: 53
根据输入的数据,我们可以画出如下的有向图:
```
6 -> 5 -> 1 -> 2 -> 3
^
|
4 -> 5
```
其中箭头表示有向边的方向。接下来我们需要对这个有向图进行拓扑排序,得到拓扑排序序列。
拓扑排序的算法是基于 Kahn 算法的。其基本思想是不断地选择入度为 0 的顶点,并将其从图中删除,直到所有顶点都被选择为止。在实现过程中,我们需要使用一个队列来存储入度为 0 的顶点。
根据上面的有向图,我们可以得到每个节点的入度:
```
1: 2
2: 1
3: 1
4: 0
5: 2
6: 0
```
其中入度为 0 的节点有 4 和 6。我们将它们入队,并依次出队并处理它们的邻接节点,更新它们的入度。
一开始入队的节点是 4 和 6,所以拓扑排序序列的开头是 4 或者 6 都可以。接下来我们以 4 为例来进行拓扑排序。
首先将 4 出队,并将其邻接节点 1 和 5 的入度减 1。此时入度为 0 的节点只有 1 和 6。因为 1 的入度为 0,所以将 1 出队,并将其邻接节点 2 的入度减 1。此时入度为 0 的节点只有 2 和 6。因为 2 的入度为 0,所以将 2 出队,并将其邻接节点 3 的入度减 1。此时入度为 0 的节点只有 3 和 6。因为 3 的入度为 0,所以将 3 出队。最后入度为 0 的节点只有 6,将其出队后,拓扑排序序列为:
```
4 -> 1 -> 2 -> 3 -> 5 -> 6
```
所以输出为:4,1,2,3,5,6。
下面是 Python 代码实现拓扑排序:
```python
from collections import deque
# 读入数据
data = []
while True:
line = input().strip()
if line == "-1,-1":
break
data.append(list(map(int, line.split(","))))
# 构建邻接表和入度数组
adj = [[] for _ in range(7)]
indegree = [0] * 7
for x, y in data:
if x == -1 and y == -1:
break
adj[x].append(y)
indegree[y] += 1
# 拓扑排序
res = []
q = deque([i for i in range(7) if indegree[i] == 0])
while q:
x = q.popleft()
res.append(x)
for y in adj[x]:
indegree[y] -= 1
if indegree[y] == 0:
q.append(y)
# 输出结果
print(",".join(map(str, res)))
```