Shortest Cycle in a Graph
01 · Problem
You are given an undirected, unweighted graph with n nodes labelled 0 to n - 1 and a list edges, where edges[i] = [u, v] connects u and v. There are no self-loops and no duplicate edges, and the graph may be disconnected.
A cycle is a path that starts and ends at the same node, uses each edge at most once, and visits no node twice except the start/end node. Its length is the number of edges it contains.
Return the length of the shortest cycle in the graph, or -1 if the graph has no cycle.
02 · Examples
n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]
3
There are two cycles: 0-1-2-0 of length 3 and 3-4-5-6-3 of length 4. The shorter one has length 3.
n = 5, edges = [[0,1],[1,2],[2,3],[3,0],[1,4],[4,3]]
4
Cycles 0-1-2-3-0, 0-1-4-3-0 and 1-2-3-4-1 all have 4 edges, and there is no triangle.
n = 4, edges = [[0,1],[0,2]]
-1
The graph is a tree (plus an isolated node 3), so it contains no cycle.
03 · Constraints
- 012 <= n <= 1000
- 020 <= edges.length <= 1000
- 03edges[i].length == 2, 0 <= u, v <= n - 1, u != v
- 04There are no repeated edges
04 · Optimal complexity
- Time
- O(n * (n + e))
- Space
- O(n + e)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.