蓝桥杯2017年第八届真题-发现环(拓扑排序python)

解题思路: 

关键点就在于怎么判断一个点是环上的点，还是一个普通的节点。每个点都统计度数(入度加上出度)。

如果我们从所有度为1的点开始访问，对子节点的度数减少1，并判断子节点度数是否为1，为1才可以继续访问，如图1中c到e点，e点度减小为1，然后可以继续访问b，b点度数减小为2，不再继续访问子节点，相似的从a和d点开始访问点，发现b点度数减小为0，不存在环，但在图二中b点的度就不可能为1或0，最终一定会减少到2不变。自己通过2图推导一下。

参考代码:

from collections import deque

n = int(input())
que = deque()
mp = [[] for _ in range(n + 1)]
du = [0 for i in range(n + 1)]
for _ in range(n):
   a, b = map(int, input().split())
   mp[a].append(b)
   mp[b].append(a)
   du[a] += 1
   du[b] += 1


def bfs():
   for i in range(1, len(du)):
       if du[i] == 1:
           que.append(i)
   while que:
       tmp = que.popleft()
       for i in mp[tmp]:
           du[i] -= 1
           if du[i] == 1:
               que.append(i)


bfs()
ans = []
for i in range(1, n + 1):
   if du[i] == 2:
       ans.append(i)
ans.sort()
for i in range(len(ans)):
   print(ans[i], end=' ')