Shortest Cycle in a Graph - Practice Coding Problems

Shortest Cycle in a Graph - Problem

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1. The edges in the graph are represented by a given 2D integer array edges, where edges[i] = [ui, vi] denotes an edge between vertex ui and vertex vi.

Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.

Return the length of the shortest cycle in the graph. If no cycle exists, return -1.

A cycle is a path that starts and ends at the same node, and each edge in the path is used only once.

Input & Output

Example 1 — Simple Triangle

$ Input: edges = [[0,1],[1,2],[2,0]]

› Output: 3

💡 Note: The graph forms a triangle: 0→1→2→0. This cycle has length 3, which is the shortest possible cycle.

Example 2 — Multiple Cycles

$ Input: edges = [[1,2],[2,3],[3,4],[4,1],[1,5]]

› Output: 4

💡 Note: There's a 4-cycle: 1→2→3→4→1, and vertex 5 is connected but doesn't form a shorter cycle.

Example 3 — No Cycle

$ Input: edges = [[1,2],[2,3],[3,4]]

› Output: -1

💡 Note: This is a simple path with no cycles, so return -1.

Constraints

2 ≤ n ≤ 1000
1 ≤ edges.length ≤ n * (n - 1) / 2
edges[i].length == 2
0 ≤ ui, vi ≤ n - 1
ui != vi
There are no repeated edges

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Undirected graph with edges [[0,1],[1,2],[2,0]]

Find Cycles

Use BFS to detect cycles and measure their lengths

Return Shortest

Return the length of the shortest cycle found

Key Takeaway

🎯 Key Insight: BFS from each vertex guarantees finding the shortest cycle containing that vertex

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to use BFS from each vertex to find the shortest cycle containing that vertex. When BFS encounters a visited vertex through a different path, we've found a cycle. The cycle length is the sum of distances from both endpoints plus 1. Best approach uses BFS from each vertex. Time: O(V*(V+E)), Space: O(V+E)

Common Approaches

Approach	Time	Space	Notes
✓ Try All Paths (DFS)	O(V * (V + E))	O(V + E)	Use DFS from each vertex to explore all possible paths and detect cycles
BFS from Each Vertex	O(V * (V + E))	O(V + E)	Use BFS from each vertex to find the shortest cycle containing that vertex

Try All Paths (DFS) — Algorithm Steps

Build adjacency list from edges
For each vertex, start DFS
Track visited vertices and path length
When revisiting a non-parent vertex, calculate cycle length

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin DFS from each vertex

Track Path

Mark visited nodes and track path length

Find Cycle

When we revisit starting vertex, we found a cycle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_VERTICES 1000

int graph[MAX_VERTICES][MAX_VERTICES];
int degree[MAX_VERTICES];
int visited[MAX_VERTICES];
int minCycle;

void dfs(int node, int parent, int start, int length, int n) {
    if (visited[node]) {
        if (node == start && length >= 3) {
            if (length < minCycle) {
                minCycle = length;
            }
        }
        return;
    }
    
    visited[node] = 1;
    for (int i = 0; i < degree[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            dfs(neighbor, node, start, length + 1, n);
        }
    }
    visited[node] = 0;
}

int solution(int edges[][2], int edgeCount) {
    if (edgeCount == 0) return -1;
    
    // Initialize
    memset(degree, 0, sizeof(degree));
    minCycle = INT_MAX;
    
    // Build adjacency list
    int vertices[MAX_VERTICES];
    int vertexCount = 0;
    
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0], v = edges[i][1];
        
        graph[u][degree[u]++] = v;
        graph[v][degree[v]++] = u;
        
        // Track unique vertices
        int found = 0;
        for (int j = 0; j < vertexCount; j++) {
            if (vertices[j] == u) {
                found = 1;
                break;
            }
        }
        if (!found) vertices[vertexCount++] = u;
        
        found = 0;
        for (int j = 0; j < vertexCount; j++) {
            if (vertices[j] == v) {
                found = 1;
                break;
            }
        }
        if (!found) vertices[vertexCount++] = v;
    }
    
    // Try starting from each vertex
    for (int i = 0; i < vertexCount; i++) {
        memset(visited, 0, sizeof(visited));
        dfs(vertices[i], -1, vertices[i], 0, vertexCount);
    }
    
    return minCycle == INT_MAX ? -1 : minCycle;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    int edges[1000][2];
    int edgeCount = 0;
    
    char* ptr = line;
    while (*ptr && edgeCount < 1000) {
        if (*ptr == '[') {
            ptr++;
            if (*ptr >= '0' || *ptr == '-') {
                int u, v;
                sscanf(ptr, "%d,%d", &u, &v);
                edges[edgeCount][0] = u;
                edges[edgeCount][1] = v;
                edgeCount++;
            }
        }
        ptr++;
    }
    
    printf("%d\n", solution(edges, edgeCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V * (V + E))

DFS from each vertex takes O(V + E), done V times

✓ Linear Growth

Space Complexity

O(V + E)

Adjacency list storage and recursion stack

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Paths (DFS) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler