解题思路:
关键点就在于怎么判断一个点是环上的点,还是一个普通的节点。每个点都统计度数(入度加上出度)。
如果我们从所有度为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=' ')
0.0分
2 人评分
C语言考试练习题_保留字母 (C语言代码)浏览:694 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:585 |
C语言程序设计教程(第三版)课后习题7.4 (Java代码)浏览:843 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:566 |
简单的a+b (C语言代码)浏览:726 |
A+B for Input-Output Practice (III) (C语言代码)浏览:576 |
C语言训练-求PI* (C语言代码)浏览:614 |
WU-整数平均值 (C++代码)浏览:1245 |
Wu-求圆的面积 (C++代码)浏览:1893 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:798 |