Closed Path Validator — Problem Statement & Solution Guide

GraphsHardCycle Detection in Graph

TimeO(N·(N+M))

SpaceO(N+M)

Problem Description

Given an undirected graph defined by a list of edges, determine the length of the shortest cycle present in the graph. If the graph is acyclic (a forest), return -1.

A cycle is a path that starts and ends at the same node, visiting at least three distinct nodes, with no repeated edges. The length of a cycle is the number of edges in that path.

Input:

- n: an integer representing the number of nodes (labeled 0 to n-1).

- edges: a list of pairs [u, v] representing undirected edges between nodes u and v.

Output:

- An integer representing the length of the shortest cycle, or -1 if no cycle exists.

DSA Pattern Breakdown

"Closed Path Validator"

hard

WHY DOES IT MATTER?

Finding the shortest cycle is a fundamental graph‑theoretic primitive used in network reliability, chemistry (ring detection), and detecting odd‑length cycles for bipartiteness checks. Mastering the BFS‑based pattern equips engineers to solve a wide class of minimum‑distance problems in unweighted graphs.

OPTIMIZATION CHALLENGE

The key insight is to treat each vertex as a BFS source while remembering the parent of each visited node; when a neighbor is already visited and isn’t the parent, the sum of their distances plus one yields a candidate cycle length. Early termination when the current BFS depth exceeds the best known cycle cuts unnecessary work.

REAL-WORLD CONNECTION

Imagine a city’s road network where each intersection is a node and streets are edges. The shortest cycle corresponds to the smallest loop a delivery truck can drive without retracing any street—a critical metric for route optimization and traffic‑flow analysis.

During an interview, start by stating the BFS invariant (layered expansion) and immediately sketch the parent‑check condition for a back‑edge. Then mention the early‑stop pruning and component‑wise processing to show you’re thinking about both correctness and efficiency.

COMPLEXITY AT A GLANCE

⏱ Time:O(N·(N+M))

💾 Space:O(N+M)

Core Theory — Why This Approach?

The shortest cycle problem in an undirected, unweighted graph is a classic application of breadth‑first search (BFS). BFS expands vertices in layers of equal distance from a source, guaranteeing that the first time we encounter a previously visited vertex (that is not the immediate parent) we have found the smallest possible cycle that includes the source. A naïve enumeration of all simple cycles would require exponential time because the number of cycles grows combinatorially with the number of edges; even a double‑nested loop that checks every pair of vertices for a connecting path leads to O(N³) work, which collapses for dense graphs with 10⁵ nodes. By leveraging BFS from each vertex and maintaining parent information, we can compute the length of the smallest cycle that passes through the source in linear time relative to the size of the component. Repeating this for every vertex yields an overall O(N·(N+M)) algorithm, which is the best known for arbitrary unweighted graphs and is fast enough for typical interview constraints (N ≤ 10⁴‑10⁵).

Interview Questions on This Problem

Q1How would you modify the BFS‑based shortest‑cycle algorithm to also return the actual nodes forming the cycle?

During BFS keep a predecessor array. When you discover a back‑edge (u, v) where v is already visited and v ≠ parent[u], you have a candidate cycle. Reconstruct the path from u to the source and from v to the source using the predecessor links, then concatenate them and add the edge (u, v). The first such reconstruction that yields the global minimum length is the required cycle.

Q2Why does the BFS approach guarantee the shortest cycle length, whereas a depth‑first search (DFS) might miss shorter cycles?

BFS explores vertices in order of increasing distance from the start node, so the first time two frontier vertices meet, the combined distances represent the minimal number of edges needed to connect them. DFS can dive deep along a single branch, potentially encountering a long path before a shorter alternative, thus it cannot assure minimality without exhaustive backtracking.

Q3In a massive sparse graph (|E| ≈ |V|), can you improve the O(N·(N+M)) bound, and if so, how?

For sparse graphs you can run BFS from each vertex but stop early once the current distance exceeds the best cycle length found so far, dramatically pruning work. Additionally, you can process each connected component separately and skip vertices whose degree is less than two, because they cannot belong to any cycle.

Examples

Example 1

Input

n = 5, edges = [[0,1],[1,2],[2,0],[3,4]]

Output

Explanation: The graph contains two components. The first component has nodes 0, 1, 2 forming a triangle (0-1-2-0), which is a cycle of length 3. The second component (3-4) is a tree. The shortest cycle is 3.

Example 2

Input

n = 6, edges = [[0,1],[1,2],[2,3],[3,0],[4,5]]

Output

Explanation: Nodes 0, 1, 2, 3 form a square (0-1-2-3-0), which is a cycle of length 4. Nodes 4 and 5 form a tree. The shortest cycle is 4.

Example 3

Input

n = 4, edges = [[0,1],[1,2],[2,3]]

Output

-1

Explanation: The graph is a simple path 0-1-2-3. There are no cycles. Return -1.

Example 4

Input

n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,3],[6,0]]

Output

Explanation: There are two cycles: 0-1-2-0 (length 3) and 3-4-5-3 (length 3). Node 6 is connected to 0 but does not form a cycle. The shortest cycle length is 3.

Constraints

2 <= n <= 10^5
0 <= edges.length <= 10^5
0 <= u, v < n
u != v
No duplicate edges in the input

Optimal Approach & Strategy

Perform BFS from each vertex, using a parent array to detect back‑edges; each back‑edge yields a candidate cycle length = dist[u] + dist[v] + 1, and we keep the global minimum, pruning when possible.

Brute Force Approach

Enumerate every triple of vertices, check if they form a cycle, and keep the smallest length; or run DFS from each node recording all simple cycles, which is exponential in the worst case.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(N·(N+M))

function solution(graph) {
   let shortestCycle = Infinity;
   for (let node in graph) {
       let visited = new Set();
       let stack = [node];
       while (stack.length > 0) {
           let currentNode = stack.pop();
           if (visited.has(currentNode)) {
               let cycleLength = 0;
               while (currentNode !== stack[stack.length - 1]) {
                   cycleLength++;
                   currentNode = stack.pop();
               }
               cycleLength++;
               shortestCycle = Math.min(shortestCycle, cycleLength);
           } else {
               visited.add(currentNode);
               for (let neighbor of graph[currentNode]) {
                   stack.push(neighbor);
               }
           }
       }
   }
   return shortestCycle === Infinity ? -1 : shortestCycle;
}

class Solution {
   public:
   int solution(vector<vector<int>>& graph) {
       int shortestCycle = INT_MAX;
       for (int i = 0; i < graph.size(); i++) {
           set<int> visited;
           stack<int> stack;
           stack.push(i);
           while (!stack.empty()) {
               int currentNode = stack.top();
               stack.pop();
               if (visited.find(currentNode) != visited.end()) {
                   int cycleLength = 0;
                   while (currentNode != stack.top()) {
                       cycleLength++;
                       currentNode = stack.top();
                       stack.pop();
                   }
                   cycleLength++;
                   shortestCycle = min(shortestCycle, cycleLength);
               } else {
                   visited.insert(currentNode);
                   for (int neighbor : graph[currentNode]) {
                       stack.push(neighbor);
                   }
               }
           }
       }
       return shortestCycle == INT_MAX ? -1 : shortestCycle;
   }
}

class Solution {
   public int solution(int[][] graph) {
       int shortestCycle = Integer.MAX_VALUE;
       for (int i = 0; i < graph.length; i++) {
           Set<Integer> visited = new HashSet<>();
           Stack<Integer> stack = new Stack<>();
           stack.push(i);
           while (!stack.isEmpty()) {
               int currentNode = stack.pop();
               if (visited.contains(currentNode)) {
                   int cycleLength = 0;
                   while (currentNode != stack.peek()) {
                       cycleLength++;
                       currentNode = stack.pop();
                   }
                   cycleLength++;
                   shortestCycle = Math.min(shortestCycle, cycleLength);
               } else {
                   visited.add(currentNode);
                   for (int neighbor : graph[currentNode]) {
                       stack.push(neighbor);
                   }
               }
           }
       }
       return shortestCycle == Integer.MAX_VALUE ? -1 : shortestCycle;
   }
}

def solution(graph):
   shortest_cycle = float('inf')
   for node in graph:
       visited = set()
       stack = [node]
       while stack:
           current_node = stack.pop()
           if current_node in visited:
               cycle_length = 0
               while current_node != stack[-1]:
                   cycle_length += 1
                   current_node = stack.pop()
               cycle_length += 1
               shortest_cycle = min(shortest_cycle, cycle_length)
           else:
               visited.add(current_node)
               for neighbor in graph[current_node]:
                   stack.append(neighbor)
   return shortest_cycle if shortest_cycle != float('inf') else -1

function solution(graph) {
   let shortestCycle = Infinity;
   for (let node in graph) {
       let visited = new Set();
       let stack = [node];
       while (stack.length > 0) {
           let currentNode = stack.pop();
           if (visited.has(currentNode)) {
               let cycleLength = 0;
               while (currentNode !== stack[stack.length - 1]) {
                   cycleLength++;
                   currentNode = stack.pop();
               }
               cycleLength++;
               shortestCycle = Math.min(shortestCycle, cycleLength);
           } else {
               visited.add(currentNode);
               for (let neighbor of graph[currentNode]) {
                   stack.push(neighbor);
               }
           }
       }
   }
   return shortestCycle === Infinity ? -1 : shortestCycle;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Closed Path Validator Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Graphs

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Closed Path Validator — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor