Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

2204. Distance to a Cycle in Undirected Graph - Leetcode Solution

Code Implementation

from collections import deque, defaultdict

class Solution:
    def distanceToCycle(self, n, edges):
        # Build adjacency list
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        # Step 1: Find all nodes in the cycle using BFS and degree
        degree = [0] * n
        for u in range(n):
            degree[u] = len(graph[u])
        queue = deque()
        for i in range(n):
            if degree[i] == 1:
                queue.append(i)
        inCycle = [True] * n
        while queue:
            node = queue.popleft()
            inCycle[node] = False
            for neighbor in graph[node]:
                degree[neighbor] -= 1
                if degree[neighbor] == 1:
                    queue.append(neighbor)
        
        # Step 2: BFS from all cycle nodes to calculate distances
        res = [-1] * n
        queue = deque()
        for i in range(n):
            if inCycle[i]:
                res[i] = 0
                queue.append(i)
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if res[neighbor] == -1:
                    res[neighbor] = res[node] + 1
                    queue.append(neighbor)
        return res
      
#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> distanceToCycle(int n, vector<vector<int>>& edges) {
        vector<vector<int>> graph(n);
        for (auto& e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        vector<int> degree(n, 0);
        for (int i = 0; i < n; ++i)
            degree[i] = graph[i].size();
        queue<int> q;
        vector<bool> inCycle(n, true);
        for (int i = 0; i < n; ++i)
            if (degree[i] == 1)
                q.push(i);
        while (!q.empty()) {
            int node = q.front(); q.pop();
            inCycle[node] = false;
            for (int neighbor : graph[node]) {
                degree[neighbor]--;
                if (degree[neighbor] == 1)
                    q.push(neighbor);
            }
        }
        vector<int> res(n, -1);
        for (int i = 0; i < n; ++i)
            if (inCycle[i]) {
                res[i] = 0;
                q.push(i);
            }
        while (!q.empty()) {
            int node = q.front(); q.pop();
            for (int neighbor : graph[node]) {
                if (res[neighbor] == -1) {
                    res[neighbor] = res[node] + 1;
                    q.push(neighbor);
                }
            }
        }
        return res;
    }
};
      
import java.util.*;

class Solution {
    public int[] distanceToCycle(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] e : edges) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        int[] degree = new int[n];
        for (int i = 0; i < n; i++) degree[i] = graph.get(i).size();
        Queue<Integer> q = new LinkedList<>();
        boolean[] inCycle = new boolean[n];
        Arrays.fill(inCycle, true);
        for (int i = 0; i < n; i++)
            if (degree[i] == 1) q.offer(i);
        while (!q.isEmpty()) {
            int node = q.poll();
            inCycle[node] = false;
            for (int neighbor : graph.get(node)) {
                degree[neighbor]--;
                if (degree[neighbor] == 1) q.offer(neighbor);
            }
        }
        int[] res = new int[n];
        Arrays.fill(res, -1);
        for (int i = 0; i < n; i++)
            if (inCycle[i]) {
                res[i] = 0;
                q.offer(i);
            }
        while (!q.isEmpty()) {
            int node = q.poll();
            for (int neighbor : graph.get(node)) {
                if (res[neighbor] == -1) {
                    res[neighbor] = res[node] + 1;
                    q.offer(neighbor);
                }
            }
        }
        return res;
    }
}
      
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[]}
 */
var distanceToCycle = function(n, edges) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    const degree = Array(n).fill(0).map((_,i)=>graph[i].length);
    const inCycle = Array(n).fill(true);
    const queue = [];
    for (let i = 0; i < n; i++) {
        if (degree[i] === 1) queue.push(i);
    }
    while (queue.length) {
        const node = queue.shift();
        inCycle[node] = false;
        for (const neighbor of graph[node]) {
            degree[neighbor]--;
            if (degree[neighbor] === 1) queue.push(neighbor);
        }
    }
    const res = Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        if (inCycle[i]) {
            res[i] = 0;
            queue.push(i);
        }
    }
    while (queue.length) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
            if (res[neighbor] === -1) {
                res[neighbor] = res[node] + 1;
                queue.push(neighbor);
            }
        }
    }
    return res;
};

Problem Description

Given an undirected connected graph with n nodes labeled from 0 to n - 1 and a list of edges, you are to find, for each node, the minimum number of edges you need to traverse to reach any node that is part of a cycle in the graph. The graph is guaranteed to have exactly one simple cycle (i.e., a cycle that does not repeat nodes or edges). For each node, output the minimum distance (in number of edges) to any node that is part of the cycle. If the node itself is in the cycle, its distance is 0.
  • The input is n (number of nodes) and edges (list of pairs [u, v]).
  • The output is a list res where res[i] is the minimum distance from node i to any cycle node.
  • Each edge is bidirectional, and the graph is connected and contains exactly one cycle.

Thought Process

When approaching this problem, the first step is to realize that the graph is almost a tree, except for one extra edge that forms the single cycle. This means that every node is either in the cycle or in a tree attached to the cycle. A brute-force solution might try to find all cycles (using DFS or BFS) and, for each node, compute the shortest path to any cycle node. However, this is inefficient and unnecessary given the graph's structure. Instead, we can:
  • Efficiently identify which nodes are in the cycle.
  • For nodes not in the cycle, find the shortest distance to the nearest cycle node.
The key insight is that nodes not in the cycle are leaves or part of branches that can be "peeled off" from the cycle one by one, just like peeling an onion.

Solution Approach

To solve the problem efficiently, we use a two-step process:
  1. Identify Cycle Nodes:
    • Since there's exactly one cycle, we can iteratively remove all leaf nodes (degree 1) from the graph.
    • Every time we remove a leaf, we decrease the degree of its neighbor.
    • We repeat this process until only the cycle nodes remain (nodes with degree > 1 after all leaves are removed).
  2. BFS from Cycle Nodes:
    • Initialize the distance for all cycle nodes as 0.
    • Perform a Breadth-First Search (BFS) starting from all cycle nodes, spreading outwards.
    • For every non-cycle node, the first time it is visited in BFS, we set its distance to its parent’s distance plus one.

This method is efficient because each node and edge is processed only a constant number of times, and the BFS guarantees minimal distances.

Example Walkthrough

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

  1. Identify Cycle Nodes:
    The cycle is among nodes 0, 1, 2 (since 0-1-2-0 forms a cycle). All others are in branches attached to the cycle.
  2. Peel Off Leaves:
    - Remove leaf 6 (connected to 5), then 5 becomes a leaf.
    - Remove 5 (connected to 4), then 4 becomes a leaf.
    - Remove 4 (connected to 3), then 3 becomes a leaf.
    - Remove 3 (connected to 1), now only 0, 1, 2 remain, which form the cycle.
  3. BFS from Cycle Nodes:
    - Nodes 0, 1, 2 get distance 0.
    - Node 3 (neighbor of 1): distance 1.
    - Node 4 (neighbor of 3): distance 2.
    - Node 5 (neighbor of 4): distance 3.
    - Node 6 (neighbor of 5): distance 4.

Final output: [0, 0, 0, 1, 2, 3, 4]

Time and Space Complexity

  • Brute-force Approach:
    For each node, run BFS or DFS to check for cycles and compute distances. This can take O(n^2) time.
  • Optimized Approach:
    • Building the adjacency list: O(n + m) where m is the number of edges.
    • Peeling leaves to find the cycle: O(n) (each node is processed at most once).
    • BFS from cycle nodes: O(n) (each node is visited once).

    Total Time Complexity: O(n + m)

    Space Complexity: O(n + m) for the adjacency list and extra arrays.

Summary

The problem leverages the unique property of the input graph: exactly one cycle. By repeatedly removing leaves, we isolate the cycle, and then use BFS to efficiently assign the minimum distance from each node to the cycle. This approach is both intuitive and optimal for the problem constraints, ensuring every node is processed only a minimal number of times. The elegance comes from reducing a potentially complex graph problem to a series of simple, linear-time steps.