难度: Hard
现有一个含 n 个顶点的 双向 图，每个顶点按从 0 到 n - 1 标记。图中的边由二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和 vi 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。
返回图中 最短 环的长度。如果不存在环，则返回 -1 。
环 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。
示例 1：
输入：n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]] 输出：3 解释：长度最小的循环是：0 -> 1 -> 2 -> 0
示例 2：
输入：n = 4, edges = [[0,1],[0,2]] 输出：-1 解释：图中不存在循环
提示：
2 <= n <= 10001 <= edges.length <= 1000edges[i].length == 20 <= ui, vi < nui != vi运行时间: 52 ms
内存: 16.8 MB
class Solution:
def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
# 构建邻接表
cnt = defaultdict(set)
for i, j in edges:
cnt[i].add(j)
cnt[j].add(i)
# 并查集，用于检测环（逐个添加边，当边上两点属于同一个集合，说明该边是环上边）
dp = list(range(n))
def find(x):
if x != dp[x]:
dp[x] = find(dp[x])
return dp[x]
# 单点出发，检测经过该点的最短伪环（伪环：环或者包含环的图，其长度定义为该点到环的长度*2，再加上环的长度）
def bfs(i):
dist, res = [0] * n, n + 1
deq = deque([(i, -1)]) # 边权重为1，可以通过队列实现广度优先遍历
while deq and res == n + 1:
cur, pre = deq.popleft()
d = dist[cur] + 1
for j in cnt[cur]:
if j == pre: continue # 不走回头路
if dist[j]: # 找到伪环s，注意dist[j]只可能是 d 或者 d-1
if dist[j] < d: return dist[j] << 1 | 1
res = d << 1
deq.append((j, cur))
dist[j] = d
return res
meet, res = set(), n + 1
for i, j in edges:
fi, fj = find(i), find(j)
if fi == fj: # 有环。注意：对于一条边，只用检测一个点
if i in meet or j in meet: continue
res = min(res, bfs(i))
meet.add(i)
# 经过点i的环都检测过了，断开连接减少其它点的检测时间
for k in cnt[i]:
cnt[k].remove(i)
else:
dp[fi] = fj
return res if res != n + 1 else -1
这个题解首先利用了邻接表来表示图的结构。使用并查集来检测边的添加是否会形成环。如果在添加一条边时，该边连接的两个顶点已经在同一个集合中，说明添加这条边会形成一个环。然后，题解利用广度优先搜索（BFS）来寻找最短环。搜索从某个顶点开始，尝试找到通过该点的最短环。如果在过程中发现一个顶点已经访问过（即在当前BFS层次中再次访问），则可以计算形成环的长度。题解中逐个处理每条边，检查其是否形成环，并使用BFS确定环的最短长度。对于每个已经检测过的点，为了减少计算，会从图中断开其连接，避免重复计算。
时间复杂度: O(n^3)
空间复杂度: O(V + E)
class Solution:
def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
# 构建邻接表
cnt = defaultdict(set)
for i, j in edges:
cnt[i].add(j)
cnt[j].add(i)
# 并查集，用于检测环
dp = list(range(n))
def find(x):
if x != dp[x]:
dp[x] = find(dp[x])
return dp[x]
# 单点出发，检测经过该点的最短伪环
def bfs(i):
dist, res = [0] * n, n + 1
deq = deque([(i, -1)]) # 使用队列实现BFS
while deq and res == n + 1:
cur, pre = deq.popleft()
d = dist[cur] + 1
for j in cnt[cur]:
if j == pre: continue # 避免回头路
if dist[j]: # 如果已访问过j
if dist[j] < d: return dist[j] << 1 | 1
res = d << 1
deq.append((j, cur))
dist[j] = d
return res
meet, res = set(), n + 1
for i, j in edges:
fi, fj = find(i), find(j)
if fi == fj: # 检测到环
if i in meet or j in meet: continue
res = min(res, bfs(i))
meet.add(i)
# 优化：断开已检测点的连接
for k in cnt[i]:
cnt[k].remove(i)
else:
dp[fi] = fj
return res if res != n + 1 else -1
并查集是一种高效的数据结构，用于处理元素分组和组间关系的问题，特别擅长处理动态连通性问题。使用并查集检测环的形成主要是因为其能快速判断两个节点是否属于同一个集合，即快速检测添加边是否会形成环。相比直接使用邻接表进行深度或广度优先搜索找环，这种方法在初始阶段可以更快地拒绝形成环的边，避免不必要的搜索，从而提高效率。然而，劣势在于并查集本身不存储路径信息，因此无法直接用来找到具体的环或计算环的长度，需要配合其他搜索方法使用。
断开已检测点的连接主要是为了优化算法性能，减少不必要的重复计算。这种做法能够确保每个节点作为环的起点最多被考虑一次，从而降低时间复杂度。然而，这种方法确实可能导致某些环未被检测到，特别是如果存在多个通过同一节点的不同环时，断开连接可能会使得后续的搜索无法找到其他环。因此，这种优化是在算法效率和可能遗漏环之间的一种权衡。
在BFS搜索中，记录每个节点的访问距离可以帮助我们快速判断并计算环的长度。当在BFS过程中遇到一个已经访问过的节点时，这意味着我们找到了一个闭环。通过比较这个节点的距离与当前距离，可以立即计算出环的长度。这种即时计算方法是有效的，因为BFS保证了每次扩展的都是等距离的节点，所以一旦形成环，我们就可以确信找到了从起点出发的最短路径长度，即最短环。
表达式(dist[j] << 1 | 1)是位操作的一种用法，其中'dist[j] << 1'将dist[j]的值左移一位，相当于乘以2，'| 1'则是将结果与1进行按位或操作，实际上是将结果的最低位设置为1。这在某些情况下用来调整偶数长度的环，使其变为奇数，可能是为了区分不同情况下环的长度或类型。然而，具体含义可能依赖于题解的其他部分或上下文，此处没有更多信息，难以给出完全准确的解释。