Python3——拓扑排序
作者:
心牢
,
2024-01-27 10:32:01
,
所有人可见
,
阅读 47
Acwing 848.有向图的拓扑序列
"""
刷基础课题的时候自己想一下整体的思路,不要照着y总板子敲代码
自己做完之后最好找一个优美的板子参照一下
如果不存在环,那么最终入度为0的点会为n
否则不能构成拓扑序列
1.首先将所有入度为0的点加入到队列之中
2.每次取出队头,枚举这些入度为0的点的出边,删掉出边,如果入度变为0则加入队列,否则继续
3.最后判断一下入度为0的点是不是n
"""
from collections import deque # 双端队列
def topSort():
global res
q = deque()
for i in range(1, n+1):
if d[i] == 0:
q.append(i) # 初始时将所有入度为0的点入队
res.append(i) # 这些入度为0的点都是可以直接输出的,所有加入答案列表
while q:
cur = q.popleft()
# 首先确保这个点在图中
if cur in graph:
# 遍历当前点的所有出边
for nxt in graph[cur]:
d[nxt] -= 1 # 入度-=1
if d[nxt] == 0: # 如果入度为0就入队,否则继续
q.append(nxt)
res.append(nxt)
return len(res)==n
n, m = map(int, input().strip().split())
res = [] # 答案数组
graph = {} # 初始化图
d = [0 for _ in range(1+n)]
for i in range(m):
a, b = map(int, input().strip().split())
if a not in graph:
graph[a] = [b]
else:
graph[a].append(b)
d[b] += 1 # 初始时需要记录所有点的入度
if not topSort():
print(-1)
else:
for item in res:
print(item, end=' ')