AcWing 848. 有向图的拓扑序列-python
原题链接
简单
作者:
Actor丶
,
2020-02-14 21:06:23
,
所有人可见
,
阅读 1072
"""
基本思想:
图和树的bfs模板:
1. 初始化队列
2. while queue不为空
3. 队头元素出队
*4*. if t not in graph: continue # !!!注意:有向图需要判断如果元素t不存在相邻节点(即出度为0),则跳过
5. 遍历,满足条件的节点入队
"""
def topSort():
global res
queue = []
for i in range(1,n+1):
if d[i]==0:
queue.append(i)
res.append(i)
while queue:
t = queue.pop(0)
if t not in graph: continue
for j in graph[t]:
if d[j]-1==0:
queue.append(j)
res.append(j)
else:
d[j] -= 1
return len(res)==n
n, m = map(int, input().split())
d = [0 for i in range(n+1)]
res = []
graph = {}
for i in range(m):
a,b = map(int, input().split())
if a not in graph:
graph[a] = [b]
d[b] += 1
else:
graph[a].append(b)
d[b] += 1
if not topSort():
print(-1)
else:
for item in res:
print(item, end=" ")