LC 2608. 图中的最短环
https://leetcode.cn/problems/shortest-cycle-in-a-graph/
这题想了很久，原来突破口在于固定一条边。
假设我们固定了(x, y)边的话，那么其实我们就需要寻找另外一条x/y之间的通路，但是这条通路不能使用(x,y)这条边
那这个问题就相当是BFS，但是遍历的时候需要避开某些边。
class Solution:
def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
adj = [[] for _ in range(n)]
for x, y in edges:
adj[x].append(y)
adj[y].append(x)
INF = 1 << 30
def bfs(src, dst):
from collections import deque
dq = deque()
depth = [-1] * n
dq.append(src)
depth[src] = 0
while dq:
x = dq.popleft()
if x == dst:
return depth[x] + 1
for y in adj[x]:
if depth[y] != -1: continue
# exclude this edge.
if (x, y) == (src, dst) or (y, x) == (src, dst): continue
depth[y] = depth[x] + 1
dq.append(y)
return INF
ans = INF
for (src, dst) in edges:
r = bfs(src, dst)
ans = min(ans, r)
if ans == INF: ans = -1
return ans