Distance to a Cycle in Undirected Graph - Practice Coding Problems

Distance to a Cycle in Undirected Graph - Problem

You are given a positive integer n representing the number of nodes in a connected undirected graph containing exactly one cycle. The nodes are numbered from 0 to n - 1 (inclusive).

You are also given a 2D integer array edges, where edges[i] = [node1i, node2i] denotes that there is a bidirectional edge connecting node1i and node2i in the graph.

The distance between two nodes a and b is defined to be the minimum number of edges that are needed to go from a to b.

Return an integer array answer of size n, where answer[i] is the minimum distance between the ith node and any node in the cycle.

Input & Output

Example 1 — Basic Cycle with Branches

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

› Output: [1,0,0,0,0,1,2]

💡 Note: The cycle is nodes 1→2→4→3→1. Node 0 is distance 1 from cycle node 1. Node 5 is distance 1 from cycle node 4. Node 6 is distance 2 from cycle (via node 5 to node 4).

Example 2 — Simple Triangle

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

› Output: [0,0,0]

💡 Note: All nodes 0, 1, 2 form the cycle, so distance to cycle is 0 for all nodes.

Example 3 — Cycle with Long Chain

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

› Output: [0,0,0,1,2,3]

💡 Note: Cycle is 0→1→2→0. Node 3 connects to cycle node 1 (distance 1). Node 4 connects via node 3 (distance 2). Node 5 connects via nodes 4→3→1 (distance 3).

Constraints

3 ≤ n ≤ 10⁵
n - 1 ≤ edges.length ≤ 10⁵
edges[i].length == 2
0 ≤ node1_i, node2_i ≤ n - 1
node1_i != node2_i
The graph is connected.
The graph has exactly one simple cycle.

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Connected graph with exactly one cycle and some nodes branching off

Find Cycle

Use DFS to identify all nodes that are part of the cycle

Calculate Distances

Multi-source BFS from cycle nodes to find minimum distances

Key Takeaway

🎯 Key Insight: Find the cycle first using DFS, then run multi-source BFS from all cycle nodes to efficiently compute minimum distances in one pass

Asked in

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

The key insight is to first identify the cycle using DFS, then use multi-source BFS starting from all cycle nodes simultaneously. This approach finds minimum distances efficiently in O(n) time by expanding outward from the cycle.

Common Approaches

Approach	Time	Space	Notes
✓ Multi-Source BFS (Optimal)	O(n)	O(n)	Find cycle first, then run BFS from all cycle nodes simultaneously
Brute Force BFS from Every Node	O(n²)	O(n)	For each node, run BFS to find distance to closest cycle node

Multi-Source BFS (Optimal) — Algorithm Steps

Step 1: Build adjacency list from edges
Step 2: Find cycle nodes using DFS with parent tracking
Step 3: Initialize BFS queue with all cycle nodes at distance 0
Step 4: Run BFS expanding outward from cycle to calculate distances

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Cycle

Identify cycle nodes using DFS

Initialize BFS

Start BFS from all cycle nodes at distance 0

Expand Outward

BFS expands to calculate minimum distances

Code -

solution.c — C

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

#define MAX_N 1005

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
bool visited[MAX_N];
int parent[MAX_N];
bool cycleNodes[MAX_N];

bool dfs(int node, int par, int n) {
    visited[node] = true;
    parent[node] = par;
    
    for (int i = 0; i < graphSize[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor == par) continue;
        
        if (visited[neighbor]) {
            int curr = node;
            cycleNodes[neighbor] = true;
            while (curr != neighbor) {
                cycleNodes[curr] = true;
                curr = parent[curr];
            }
            return true;
        } else if (dfs(neighbor, node, n)) {
            return true;
        }
    }
    return false;
}

void findCycle(int n) {
    memset(visited, false, sizeof(visited));
    memset(cycleNodes, false, sizeof(cycleNodes));
    for (int i = 0; i < n; i++) parent[i] = -1;
    
    dfs(0, -1, n);
}

int* solution(int n, int** edges, int edgesSize) {
    // Initialize graph
    memset(graphSize, 0, sizeof(graphSize));
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][graphSize[u]++] = v;
        graph[v][graphSize[v]++] = u;
    }
    
    findCycle(n);
    
    int* result = (int*)malloc(n * sizeof(int));
    int queue[MAX_N];
    int front = 0, rear = 0;
    
    // Initialize with cycle nodes
    for (int i = 0; i < n; i++) {
        if (cycleNodes[i]) {
            result[i] = 0;
            queue[rear++] = i;
        } else {
            result[i] = -1;
        }
    }
    
    // BFS to find distances
    while (front < rear) {
        int node = queue[front++];
        
        for (int i = 0; i < graphSize[node]; i++) {
            int neighbor = graph[node][i];
            if (result[neighbor] == -1) {  // Not visited
                result[neighbor] = result[node] + 1;
                queue[rear++] = neighbor;
            }
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Read edges array - simplified parsing
    int edgesSize;
    scanf("%d", &edgesSize);
    
    int** edges = (int**)malloc(edgesSize * sizeof(int*));
    for (int i = 0; i < edgesSize; i++) {
        edges[i] = (int*)malloc(2 * sizeof(int));
        scanf("%d %d", &edges[i][0], &edges[i][1]);
    }
    
    int* result = solution(n, edges, edgesSize);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", result[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    for (int i = 0; i < edgesSize; i++) {
        free(edges[i]);
    }
    free(edges);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

DFS to find cycle takes O(n), then single BFS traversal takes O(n)

✓ Linear Growth

Space Complexity

O(n)

Adjacency list takes O(n) space, plus BFS queue and visited arrays

⚡ Linearithmic Space

15.7K Views

Medium Frequency

~25 min Avg. Time

342 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

Multi-Source BFS (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler