LeetCode-2608. 图中的最短环【广度优先搜刮 图，腾讯口试真题】

标题形貌：

现有一个含 n 个极点的 双向 图，每个极点按从 0 到 n - 1 标志。图中的边由二维整数数组 edges 表现，此中 edges = [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 <= 1000
1 <= edges.length <= 1000
edges.length == 2
0 <= ui, vi < n
ui != vi
不存在重复的边
解题思绪一：【一图秒懂】罗列出发点跑 BFS

题解参考

问：为什么说发现一个已经入队的点，就阐明有环？
答：这阐明到同一个点有两条差别的路径，这两条路径构成了一个环。

1. class Solution:
2.     def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
3.         g = [[] for _ in range(n)]
4.         for x, y in edges:
5.             g[x].append(y)
6.             g[y].append(x) # 建图
8.         def bfs(start):
9.             ans = inf
10.             dis = [-1] * n # dis[i] 表示从start到i的最短路径长度
11.             dis[start] = 0
12.             q = deque([(start, -1)])
13.             while q:
14.                 x, fa = q.popleft()
15.                 for y in g[x]:
16.                     if dis[y] < 0: # 第一次遇到
17.                         dis[y] = dis[x] + 1
18.                         q.append((y, x))
19.                     elif y != fa: # 第二次遇到
20.                         ans = min(ans, dis[x] + dis[y] + 1)
21.             return ans
22.         ans = min(bfs(i) for i in range(n))
23.         return ans if ans < inf else -1

复制代码

时间复杂度：O(nm)
空间复杂度：O(n+m)
解题思绪二：背诵版

1. class Solution:
2.     def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
3.         g = [[] for _ in range(n)]
4.         for u, v in edges:
5.             g[u].append(v)
6.             g[v].append(u)
8.         def bfs(start):
9.             ans = inf
10.             dis = [-1] * n
11.             q = deque([(start, -1)])
12.             dis[start] = 0
13.             while q:
14.                 x, fa = q.popleft()
15.                 for y in g[x]:
16.                     if dis[y] < 0:
17.                         dis[y] = dis[x] + 1
18.                         q.append((y, x))
19.                     elif y != fa:
20.                         ans = min(ans, dis[x] + dis[y] + 1)
21.             return ans
23.         ans = min(bfs(i) for i in range(n))
24.         return ans if ans < inf else -1

复制代码

时间复杂度：O(nm)
空间复杂度：O(n+m)
解题思绪三：

[code][/code] 时间复杂度：O(n)
空间复杂度：O(n)

---

   创作不易，观众老爷们请停步… 动起可爱的小手，点个赞再走呗 (๑◕ܫ￩๑)   

    欢迎各人关注笔者，你的关注是我一连更博的最大动力

   原创文章，转载告知，盗版必究

---

---

---

♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠