难度: Hard
Submission
运行时间: 155 ms
内存: 49.4 MB
class Solution:
def distanceToCycle(self, n: int, e: List[List[int]]) -> List[int]:
#bfs判环,只要不往回走即可
#重跑多源bfs
edge=[[] for _ in range(n)]
vis = [False]*n
for x,y in e:
edge[x].append(y)
edge[y].append(x)
pa = [-1]*n
circle=set()
def find():
q=[0]
while q:
tmp = q
q = []
while tmp:
x=tmp.pop()
for y in edge[x]:
if y==pa[x]:continue
if pa[y]==-1:
pa[y]=x
q.append(y)
else:
circle.add(y)
#x与pa[y]回溯
a,b=x,pa[y]
while a!=b:
circle.add(a)
circle.add(b)
if pa[b]==a or pa[a]==b:
return
a=pa[a]
b=pa[b]
circle.add(a)
return
find()
#跑多源bfs
q=[]
ans = [0]*n
for x in circle:
q.append(x)
vis[x]=True
ans[x]=0
level=0
while q:
tmp=q
q=[]
level+=1
while tmp:
x=tmp.pop()
for y in edge[x]:
if vis[y]:continue
q.append(y)
vis[y]=True
ans[y]=level
return ans
Explain
此题解采用了两阶段的广度优先搜索（BFS）来解决问题。首先，第一阶段的BFS用于在无向图中找到一个环，并将环中的节点记录下来。初始时从节点0开始，利用数组`pa`记录每个节点的父节点，以避免向父节点反向遍历，从而检测到环。一旦检测到一个节点被重复访问（即形成环路），则回溯以确定环中的所有节点。第二阶段的BFS从环中的所有节点同时出发，以这些节点作为多源点，计算图中所有其他节点到最近的环中节点的最短距离。这里使用`vis`数组记录节点是否已被访问过，以避免重复处理。
时间复杂度: O(V + E)
空间复杂度: O(V + E)
class Solution:
def distanceToCycle(self, n: int, e: List[List[int]]) -> List[int]:
# 初始化邻接表和访问记录
edge=[[] for _ in range(n)]
vis = [False]*n
for x,y in e:
edge[x].append(y)
edge[y].append(x)
# 初始化父节点数组和环节点集合
pa = [-1]*n
circle=set()
# 使用BFS检测环
def find():
q=[0]
while q:
tmp = q
q = []
while tmp:
x=tmp.pop()
for y in edge[x]:
if y==pa[x]:continue # 避免往回走
if pa[y]==-1:
pa[y]=x
q.append(y)
else:
circle.add(y)
# 回溯以找到环的完整路径
a,b=x,pa[y]
while a!=b:
circle.add(a)
circle.add(b)
if pa[b]==a or pa[a]==b:
return
a=pa[a]
b=pa[b]
circle.add(a)
return
find()
# 从环中的节点出发进行多源BFS
q=[]
ans = [0]*n
for x in circle:
q.append(x)
vis[x]=True
ans[x]=0
level=0
while q:
tmp=q
q=[]
level+=1
while tmp:
x=tmp.pop()
for y in edge[x]:
if vis[y]:continue # 避免重复访问
q.append(y)
vis[y]=True
ans[y]=level
return ans
Explore
在广度优先搜索（BFS）中，通过使用一个布尔数组`vis`来跟踪每个节点的访问状态来确保不会对同一个节点进行重复访问或处理。在搜索过程开始之前，所有节点的访问状态都设置为`False`。当一个节点第一次被访问时，将其对应在`vis`数组中的值设置为`True`。之后，在遍历该节点的邻接节点时，会首先检查其访问状态，如果已被访问（即`vis`值为`True`），则跳过该节点，这样可以防止同一个节点被重复处理。
该算法从节点0开始执行BFS，因此它将检测到从节点0开始能够首先到达的任何环。如果存在多个环，该算法并不保证找到所有环，而是只关注第一个被检测到的环。环的检测依赖于BFS的遍历顺序和图的结构，一旦发现重复访问的节点即确定一个环，然后通过回溯确定环的完整路径并结束寻找环的过程。因此，哪个环被检测到主要取决于图的连接结构以及BFS的遍历起点。
在环的检测过程中，仅仅记录形成环的那两个节点是不够的，因为环可能包含多于两个节点的路径。为了确保正确计算图中所有节点到环的最短距离，需要知道环中包含的所有节点。通过回溯可以精确地确定环的全部构成节点，这些节点在之后的多源BFS中被用作起始点来计算距离。如果只记录两个节点，那么可能会遗漏环中的其他节点，从而导致距离的计算不准确。
在题解中的多源BFS执行过程中，如果存在孤立节点或与环不连通的节点，这些节点将不会被访问到。这是因为它们不会被环中节点的波及到，因此它们在`vis`数组中的值会保持为`False`，并且在`ans`数组中的值（距离）会保持初始化的默认值（这里题解中未明确初始化为什么值，理论上应该初始化为一个表示无法到达的值，比如正无穷）。因此，这种方法自然地忽略了与环不连通的节点。