题目描述
现有一个含 n
个顶点的 双向 图,每个顶点按从 0
到 n - 1
标记。图中的边由二维整数数组 edges
表示,其中 edges[i] = [u_i, v_i]
表示顶点 u_i
和 v_i
之间存在一条边。每对顶点最多通过一条边连接,并且不存在与自身相连的顶点。
返回图中 最短 环的长度。如果不存在环,则返回 -1
。
环 是指以同一节点开始和结束,并且路径中的每条边仅使用一次。
样例
输入:n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
输出:3
解释:长度最小的循环是:0 -> 1 -> 2 -> 0
输入:n = 4, edges = [[0,1],[0,2]]
输出:-1
解释:图中不存在循环
限制
2 <= n <= 1000
1 <= edges.length <= 1000
edges[i].length == 2
0 <= u_i, v_i < n
u_i != v_i
- 不存在重复的边。
算法
(宽度优先遍历) $O(m(n + m))$
- 枚举每一条边,从边的一个端点开始,在不经过这条边的情况下,到达另一个端点的最短路的长度,再加 1,就是这条边所能得到的最小环。
时间复杂度
- 对于每一条边,需要 $O(n + m)$ 的时间宽度优先搜索,故时间复杂度为 $O(m(n + m))$。
空间复杂度
- 需要 $O(n + m)$ 的额外空间存储图,宽度优先搜索的队列和距离数组。
C++ 代码
class Solution {
private:
vector<vector<int>> graph;
queue<int> q;
int bfs(int st, int ed, int n) {
q.push(st);
vector<int> d(n, INT_MAX);
d[st] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u])
if (d[v] > d[u] + 1 && !(u == st && v == ed)) {
d[v] = d[u] + 1;
q.push(v);
}
}
return d[ed];
}
public:
int findShortestCycle(int n, vector<vector<int>>& edges) {
graph.resize(n);
for (const auto &e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
int ans = INT_MAX;
for (const auto &e : edges)
ans = min(ans, bfs(e[0], e[1], n));
if (ans == INT_MAX)
return -1;
return ans + 1;
}
};