请写出一个代码完成以下功能输入描述: n,<工序1,工序2>,<工序1,工序3>, ...工序i工序> 例如,6,<1,3>,<2,3>,<3,4>,<4,5>,<4,6> 输出描述:可以最后执行的工序 例如,5,6 要求:输出要求保证按字典序或自然数递增排序。
时间: 2023-08-18 17:09:19 浏览: 32
以下是 Python 代码实现:
```python
n = int(input().split(',')[0]) # 获取工序总数
graph = [[] for _ in range(n+1)] # 创建空的图,下标从1开始
# 构建图
for line in input().split(',')[1:]:
node1, node2 = map(int, line.strip('<>').split(','))
graph[node1].append(node2)
# 拓扑排序
in_degree = [0] * (n+1) # 计算每个节点的入度
for i in range(1, n+1):
for j in graph[i]:
in_degree[j] += 1
queue = [i for i in range(1, n+1) if in_degree[i] == 0] # 将入度为0的节点加入队列
res = []
while queue:
node = queue.pop(0)
res.append(node)
for i in graph[node]:
in_degree[i] -= 1
if in_degree[i] == 0:
queue.append(i)
# 输出结果
print(','.join(map(str, res)))
```
输入格式为 `n,<工序1,工序2>,<工序1,工序3>,...`,例如 `6,<1,3>,<2,3>,<3,4>,<4,5>,<4,6>`。输出格式为可以最后执行的工序,例如 `5,6`。
代码实现的思路是先构建一个图,然后对图进行拓扑排序,最后输出结果。具体实现可以参考代码注释。