AcWing 848. 有向图的拓扑序列-python
原题链接
简单
作者:
Actor丶
,
2020-02-14 21:06:23
,
所有人可见
,
阅读 1062
"""
基本思想:
图和树的bfs模板:
1. 初始化队列
2. while queue不为空
3. 队头元素出队
*4*. if t not in graph: continue # !!!注意:有向图需要判断如果元素t不存在相邻节点(即出度为0),则跳过
5. 遍历,满足条件的节点入队
"""
def topSort():
global res
# 1. 初始化队列:入度为零时,节点入队
queue = []
for i in range(1,n+1):
if d[i]==0:
queue.append(i)
res.append(i)
# 2. while queue不为空
while queue:
# 3. 队头元素出队
t = queue.pop(0)
# 4. 有向图判断t节点是否出度为0(出度为0的点不在graph的keys中)
if t not in graph: continue
# 5. 循环遍历满足条件的节点入队:入度为1的节点,删掉节点t后入度变为0,所以条件为入度d[j]==1
for j in graph[t]:
if d[j]-1==0:
queue.append(j)
res.append(j)
else:
d[j] -= 1
return len(res)==n # !!!出错:如果只返回res的话,那么有环图返回的res包含的节点会小于n
# 1. 输入示例
n, m = map(int, input().split())
# 2. 初始化入度状态,默认值为0
d = [0 for i in range(n+1)]
res = [] # 存储要输出的拓扑序列
# 3. 图的存储模板
graph = {}
for i in range(m):
a,b = map(int, input().split())
if a not in graph:
graph[a] = [b]
d[b] += 1 # a到b,所以节点b的入度加1
else:
graph[a].append(b)
d[b] += 1 # a到b,所以节点b的入度加1
if not topSort():
print(-1)
else:
for item in res:
print(item, end=" ")