解题思路
思路借鉴了灵茶山艾府大佬的$BFS$思路。对每个点进行宽搜,从当前点出发,遍历其所有邻点,如果该点是这个点的父节点,则直接跳过,如果不是其父节点,并且该点的距离已经被更新过了(我们需要维护一个距离来判断该点是否被遍历过,也可以使用$bool$数组标记),那么说明当前点存在一个环,环的长度就等于$dist[vertex] + dist[j] + 1$,我们需要找到从起始节点出发的所有环的最小值,所以用一个变量维护这个值。
代码
class Solution {
static final int N = 1010, M = 1000010, INF = Integer.MAX_VALUE;
static int[] h = new int[N], e = new int[M], ne = new int[M], dist = new int[N];
static int idx;
public static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
public static int bfs(int u) {
Arrays.fill(dist, INF);
dist[u] = 0;
int res = INF;
LinkedList<int[]> q = new LinkedList<>();
q.add(new int[]{u, -1});
while (!q.isEmpty()) {
int[] a = q.remove();
int vertex = a[0], fa = a[1];
for (int i = h[vertex]; i != -1; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
if (dist[j] == INF) {
dist[j] = dist[vertex] + 1;
q.add(new int[]{j, vertex});
}
else {
res = Math.min(res, dist[vertex] + dist[j] + 1);
}
}
}
return res;
}
public int findShortestCycle(int n, int[][] edges) {
Arrays.fill(h, -1);
for (int[] a : edges) {
int x = a[0], y = a[1];
add(x, y);
add(y, x);
}
int res = INF;
for (int i = 0; i < n; i ++) {
res = Math.min(res, bfs(i));
}
if (res == INF) return -1;
return res;
}
}