寻找无向图中的环
0X00 模板题
【寻找无向图中的环】Planet Distance
from collections import dequedef solve(graph):
degrees = {}
deq = deque()# 找到所有度为 1 的点
for k, v in graph.items():
degrees[k] = len(v)
if len(v) == 1:
deq.append(k)# print("deq", deq)
visited = set(deq)# 拓扑排序找到环
while len(deq) > 0:
size = len(deq)
while size > 0:
size -= 1
n = deq.popleft()
for n1 in graph[n]:
if n1 in visited: continue
degrees[n1] -= 1
if degrees[n1] == 1:
visited.add(n1)
deq.append(n1)# print("degrees", degrees)circles = deque([k for k, v in degrees.items() if v != 1])
# print("circles", circles)
visited = set(circles)# 用 bfs 计算距离
dists = [""] * len(graph)
dis = 0
while len(circles) > 0:
size = len(circles)
while size > 0:
size -= 1
n = circles.popleft()
dists[int(n) - 1] = str(dis)
for n1 in graph[n]:
if n1 in visited:
continue
visited.add(n1)
circles.append(n1)
dis += 1return distsdef createGraph(edgeNum):
graph = {}
for i in range(edgeNum):
n1, n2 = input().strip().split()
if n1 not in graph and n2 in graph:
graph[n1] = [n2]
graph[n2].append(n1)
elif n2 not in graph and n1 in graph:
graph[n2] = [n1]
graph[n1].append(n2)
elif n2 in graph and n1 in graph:
graph[n2].append(n1)
graph[n1].append(n2)
else:
graph[n2] = [n1]
graph[n1] = [n2]
return graphT = int(input())
for t in range(T):
graph = createGraph(int(input()))
print("Case #{}: {}".format(t + 1, " ".join(solve(graph))))输入:
1
6
1 2
2 3
3 4
4 5
5 6
4 6
主要看这一段:
from collections import dequegraph = {}degrees = {}
deq = deque()# 找到所有度为 1 的点
for k, v in graph.items():
degrees[k] = len(v)
if len(v) == 1:
deq.append(k)# print("deq", deq)
visited = set(deq)# 拓扑排序找到环
while len(deq) > 0:
size = len(deq)
while size > 0:
size -= 1
n = deq.popleft()
for n1 in graph[n]:
if n1 in visited: continue
degrees[n1] -= 1
if degrees[n1] == 1:
visited.add(n1)
deq.append(n1)
circles = deque([k for k, v in degrees.items() if v != 1])
注意一定要加 visited
