Approach
Breadth-first search
For Shortest Cycle in a Graph, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 43 lines of Java from the credited upstream file 2608.java.
- The implementation visibly relies on sequence storage, work queue.
- 4 loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution {2 public int findShortestCycle(int n, int[][] edges) {3 int ans = INF;4 List<Integer>[] graph = new List[n];5 Arrays.setAll(graph, i -> new ArrayList<>());6 7 for (int[] edge : edges) {8 final int u = edge[0];9 final int v = edge[1];10 graph[u].add(v);11 graph[v].add(u);12 }13 14 for (int i = 0; i < n; ++i)15 ans = Math.min(ans, bfs(graph, i));16 17 return ans == INF ? -1 : ans;18 }19 20 private static final int INF = 1001;21 22 23 24 private int bfs(List<Integer>[] graph, int i) {25 int[] dist = new int[graph.length];26 Arrays.fill(dist, INF);27 Queue<Integer> q = new ArrayDeque<>(List.of(i));28 dist[i] = 0;29 while (!q.isEmpty()) {30 final int u = q.poll();31 for (final int v : graph[u]) {32 if (dist[v] == INF) {33 dist[v] = dist[u] + 1;34 q.offer(v);35 } else if (dist[v] + 1 != dist[u]) { 36 return dist[v] + dist[u] + 1;37 }38 }39 }40 return INF;41 }42}43