Identify Cyclic Patterns in Network Structures — Problem Statement & Solution Guide

GraphsHardCycle Detection in Graph

TimeO(V + E)

SpaceO(V + E)

Problem Description

You are provided with an undirected graph representing a network topology, defined by an adjacency list. Your task is to determine the length of the shortest cycle (also known as the girth) in the graph. If the graph is acyclic (i.e., it is a forest), return -1.

The input is given as an array of lists, where adj[i] contains the indices of all nodes directly connected to node i. The graph is guaranteed to be simple (no self-loops or multiple edges between the same pair of nodes).

Return an integer representing the minimum number of edges in any cycle within the graph. If no cycle exists, return -1.

DSA Pattern Breakdown

"Identify Cyclic Patterns in Network Structures"

hard

WHY DOES IT MATTER?

Shortest‑cycle detection is a classic graph‑theoretic primitive used in network reliability, chemistry (ring detection), and social network analysis. Mastering this pattern demonstrates a candidate's ability to translate a global property (girth) into local BFS explorations, a skill that recurs in many hard graph problems.

OPTIMIZATION CHALLENGE

The key insight is that BFS naturally discovers the shortest path tree from a source. By checking for cross‑edges that connect two nodes already in the tree, we instantly obtain the length of the smallest cycle involving the source, eliminating the need to enumerate all possible cycles.

REAL-WORLD CONNECTION

Imagine a distributed system where nodes represent services and edges represent direct API calls. The shortest cycle corresponds to the minimal feedback loop that can cause cascading failures; detecting it quickly helps engineers break harmful loops before they amplify.

During an interview, start BFS from each unvisited component, keep a queue of (node, distance), and store the parent. When you see a neighbor that is visited and not the parent, compute candidate = dist[current] + dist[neighbor] + 1 and update the global minimum. Early exit if the current distance exceeds the best answer found so far.

COMPLEXITY AT A GLANCE

⏱ Time:O(V + E)

💾 Space:O(V + E)

Core Theory — Why This Approach?

The girth of an undirected graph is the length of its shortest simple cycle. A naïve way to find it would be to enumerate all possible node sequences, but the number of walks grows exponentially with the number of vertices, making it infeasible for any realistic input size. The optimal paradigm leverages breadth‑first search (BFS) from each vertex, treating the graph as unweighted; during BFS we keep track of the distance from the source and the parent of each visited node. When we encounter an already‑visited neighbor that is not the parent, we have discovered a cycle, and its length can be computed as distance[u] + distance[v] + 1. By running BFS from every vertex (or from each component) and taking the minimum cycle length found, we guarantee the shortest cycle is captured while keeping the overall complexity linear in the number of edges.

Interview Questions on This Problem

Q1How would you modify the BFS‑based girth algorithm to work on a directed graph where cycles must respect edge direction?

In a directed graph, BFS must follow outgoing edges only. When a visited node is encountered again, we cannot simply ignore the parent check; we need to ensure the back edge forms a directed cycle. The cycle length is computed as distance[u] + distance[v] + 1 where u is the current node and v is the already‑visited neighbor reachable via a directed edge. Running BFS from each vertex still yields the shortest directed cycle.

Q2Why does running BFS from every vertex still result in O(V + E) time overall for an undirected graph?

Each BFS explores edges only within its connected component, and each edge is examined at most twice across all BFS runs because once a component is fully visited, subsequent BFS starts from vertices inside that component will immediately terminate after seeing all neighbors as already visited. By marking vertices as globally visited after the first BFS of a component, we avoid redundant traversals, yielding overall linear time.

Q3In a massive sparse graph stored as an adjacency list, how can you reduce memory overhead while still computing the girth?

Store the adjacency list using compact structures such as vectors of ints or CSR (compressed sparse row) format, and reuse a single distance and parent array for each BFS, resetting only the entries of vertices visited in the current component. This avoids allocating O(V) space per BFS and keeps the extra memory to O(V + E).

Examples

Example 1

Input

adj = [[1, 2], [0, 2], [0, 1]]

Output

Explanation: The graph contains a single cycle: 0 -> 1 -> 2 -> 0. The length of this cycle is 3 edges. Since this is the only cycle, the minimum cycle length is 3.

Example 2

Input

adj = [[1], [0, 2], [1, 3], [2]]

Output

-1

Explanation: The graph is a tree (a path from 0 to 3). There are no cycles present in the structure. Therefore, the function returns -1.

Example 3

Input

adj = [[1, 3], [0, 2], [1, 3], [0, 2]]

Output

Explanation: The graph contains two distinct cycles: 0 -> 1 -> 2 -> 3 -> 0 (length 4) and 0 -> 3 -> 2 -> 1 -> 0 (length 4). Both cycles have a length of 4. The minimum cycle length is 4.

Example 4

Input

adj = [[1, 2], [0, 3], [0, 3], [1, 2]]

Output

Explanation: The graph is a complete bipartite graph K2,2. The cycles are 0 -> 1 -> 3 -> 2 -> 0 and 0 -> 2 -> 3 -> 1 -> 0. Both have length 4. The minimum cycle length is 4.

Constraints

1 <= adj.length <= 10^5
0 <= adj[i][j] < adj.length
adj[i] is unique for each i
The graph is undirected and simple (no self-loops, no multi-edges)
The total number of edges is at most 10^5

Optimal Approach & Strategy

Perform BFS from each vertex, using distance and parent arrays to detect cross‑edges that close a cycle, updating the global minimum; overall linear time.

Brute Force Approach

Enumerate every possible node sequence up to length V, check if it forms a simple cycle, and keep the smallest length; this is exponential.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(V + E)

/**
 * @param {number[][]} adj
 * @return {number}
 */
var findShortestCycle = function(adj) {
    const n = adj.length;
    let ans = Infinity;
    
    for (let i = 0; i < n; i++) {
        const dist = new Array(n).fill(-1);
        const parent = new Array(n).fill(-1);
        const queue = [i];
        dist[i] = 0;
        
        while (queue.length > 0) {
            const u = queue.shift();
            
            for (const v of adj[u]) {
                if (dist[v] === -1) {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    queue.push(v);
                } else if (parent[u] !== v && parent[v] !== u) {
                    ans = Math.min(ans, dist[u] + dist[v] + 1);
                }
            }
        }
    }
    
    return ans === Infinity ? -1 : ans;
};

class Solution {
public:
    int findShortestCycle(vector<vector<int>>& adj) {
        int n = adj.size();
        int ans = INT_MAX;
        
        for (int i = 0; i < n; i++) {
            vector<int> dist(n, -1);
            vector<int> parent(n, -1);
            queue<int> q;
            dist[i] = 0;
            q.push(i);
            
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                
                for (int v : adj[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        parent[v] = u;
                        q.push(v);
                    } else if (parent[u] != v && parent[v] != u) {
                        ans = min(ans, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        
        return ans == INT_MAX ? -1 : ans;
    }
};

class Solution {
    public int findShortestCycle(int[][] adj) {
        int n = adj.length;
        int ans = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            int[] dist = new int[n];
            int[] parent = new int[n];
            Arrays.fill(dist, -1);
            Arrays.fill(parent, -1);
            Queue<Integer> queue = new LinkedList<>();
            dist[i] = 0;
            queue.offer(i);
            
            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : adj[u]) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        parent[v] = u;
                        queue.offer(v);
                    } else if (parent[u] != v && parent[v] != u) {
                        ans = Math.min(ans, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

class Solution:
    def findShortestCycle(self, adj: List[List[int]]) -> int:
        n = len(adj)
        ans = float('inf')
        
        for i in range(n):
            dist = [-1] * n
            parent = [-1] * n
            queue = deque([i])
            dist[i] = 0
            
            while queue:
                u = queue.popleft()
                for v in adj[u]:
                    if dist[v] == -1:
                        dist[v] = dist[u] + 1
                        parent[v] = u
                        queue.append(v)
                    elif parent[u] != v and parent[v] != u:
                        ans = min(ans, dist[u] + dist[v] + 1)
        
        return -1 if ans == float('inf') else ans

/**
 * @param {number[][]} adj
 * @return {number}
 */
var findShortestCycle = function(adj) {
    const n = adj.length;
    let ans = Infinity;
    
    for (let i = 0; i < n; i++) {
        const dist = new Array(n).fill(-1);
        const parent = new Array(n).fill(-1);
        const queue = [i];
        dist[i] = 0;
        
        while (queue.length > 0) {
            const u = queue.shift();
            
            for (const v of adj[u]) {
                if (dist[v] === -1) {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    queue.push(v);
                } else if (parent[u] !== v && parent[v] !== u) {
                    ans = Math.min(ans, dist[u] + dist[v] + 1);
                }
            }
        }
    }
    
    return ans === Infinity ? -1 : ans;
};

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.

Identify Cyclic Patterns in Network Structures 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

Identify Cyclic Patterns in Network Structures — 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