题目重点：无向连通恰一环图中先持续删除度为 1 的树枝，再从全部环点同时 BFS 求每点最短距离。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 图无向、简单、连通，n≥3 且 n 条边，因此恰有一个简单环；顶点用 0..n−1。
- 距离按边数，环上所有顶点为 0；不返回具体最近环点。
- 代码先验证边数、无自环/重边和连通性；若原题允许多环，剥叶后的 2-core 也可能不是单个环，需重定答案。
解题路线
- 先计算各点度数，把所有叶子入队。反复取叶并减邻居度数，新成叶的继续入队；被剥掉的都在挂到环上的树中，剩余点恰是唯一环。
- 以所有环点作为距离 0 的多源 BFS 起点，向剥掉的树扩展；首次到达顶点的层数就是它到任意环点的最短边数。
- 证明：环上每点在剥叶过程至少保留两条环边，永不被删；环外树有限且必有叶，反复剥离直至全删。多源 BFS 的层数按最短路径顺序扩展。
手动走一遍
环 0-1-2-0，树枝 2-3-4。初始叶 4 先被剥，随后 3 被剥，剩 0/1/2 为环；多源 BFS 给距离 [0,0,0,1,2]。只从任意一个环点做 BFS 会把其他环点误算为正数。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Distance from each vertex to the unique cycle in an undirected simple graph."""
from collections import deque
def distance_to_unique_cycle(n: int, edges: list[tuple[int, int]]) -> list[int]:
if n < 3 or len(edges) != n:
raise ValueError("connected simple unicyclic graph needs n >= 3 and n edges")
graph = [[] for _ in range(n)]
seen_edges = set()
for a, b in edges:
if not 0 <= a < n or not 0 <= b < n or a == b:
raise ValueError("invalid edge")
key = (min(a, b), max(a, b))
if key in seen_edges:
raise ValueError("parallel edge")
seen_edges.add(key)
graph[a].append(b)
graph[b].append(a)
reached = {0}
pending = [0]
while pending:
node = pending.pop()
for neighbor in graph[node]:
if neighbor not in reached:
reached.add(neighbor)
pending.append(neighbor)
if len(reached) != n:
raise ValueError("graph must be connected")
degree = [len(neighbors) for neighbors in graph]
leaves = deque(v for v in range(n) if degree[v] == 1)
on_cycle = [True] * n
while leaves:
node = leaves.popleft()
on_cycle[node] = False
for neighbor in graph[node]:
degree[neighbor] -= 1
if degree[neighbor] == 1:
leaves.append(neighbor)
distances = [-1] * n
queue = deque()
for vertex, cycle_member in enumerate(on_cycle):
if cycle_member:
distances[vertex] = 0
queue.append(vertex)
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if distances[neighbor] == -1:
distances[neighbor] = distances[node] + 1
queue.append(neighbor)
return distances
复杂度
n 点、m=n 边：验证连通、剥叶、多源 BFS 都是 O(n+m) 时间；邻接表、队列与数组 O(n+m) 空间。
易错点与追问
容易失分的边界
- 从一个环点 BFS 而不是全部环点。
- 只找一条 back edge 就假设其两个端点覆盖整个环。
- 在一般多环图上把 2-core 全部当作环点而不重新论证。
- 题目未明确有向/重边，却把训练假设称原题约束。
继续深挖
- 若图有多个连通分量且各有一个环，如何返回每点距离？
- 若是一般无向图，哪些点在任意环上，2-core 是否足够？
- 若需要返回最近的环点且并列按 ID，BFS 如何定 tie-break？
