LeetCode 2204 - Distance to a Cycle in Undirected Graph

LeetCode Problem 2204

Difficulty: 🔴 Hard
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem gives us a connected undirected graph with n nodes and exactly n edges. A connected graph with n nodes normally forms a tree when it has n - 1 edges. Since this graph has one extra edge, it contains exactly one cycle.

Our goal is to compute, for every node, the minimum distance from that node to any node that belongs to the cycle.

The graph is undirected, so every edge can be traversed in both directions. The distance between two nodes is simply the minimum number of edges along a path connecting them.

For nodes that are part of the cycle itself, the answer is 0, because they are already on the cycle. For nodes outside the cycle, we must determine how many edges away they are from the nearest cycle node.

The constraints are important:

• n can be as large as 100000
• The graph is connected
• There is exactly one cycle

These constraints immediately tell us that we need a near linear solution. Any algorithm with quadratic complexity would be too slow.

The most important structural property is that every node not on the cycle belongs to a tree attached to the cycle. Since there is exactly one cycle, removing the cycle would leave several independent trees rooted at cycle nodes.

Several edge cases are important:

• The entire graph itself could be just a cycle, in which case every answer is 0
• Some nodes may be long chains extending from the cycle
• The cycle may be very small, such as a triangle
• The graph may be extremely skewed, producing very deep branches
• Recursive DFS could overflow the stack for large inputs, so iterative approaches are safer

Approaches

Brute Force Approach

A brute force solution would first determine which nodes belong to the cycle, then for every node perform a BFS to find the nearest cycle node.

One possible implementation is:

1. Detect all cycle nodes
2. For every node:

• Run BFS
• Stop once a cycle node is reached
• Record the distance

This works because BFS in an unweighted graph always finds the shortest path.

However, this is far too expensive. Running BFS from every node costs O(n * (n + e)), which becomes O(n^2) since e = n.

With n = 100000, this is not feasible.

Optimal Approach

The key insight is that nodes not on the cycle behave like leaves in trees attached to the cycle.

If we repeatedly remove leaf nodes, eventually only the cycle nodes remain.

This is similar to topological trimming:

• Nodes with degree 1 cannot belong to a cycle
• Remove all leaves
• Their neighbors may become leaves afterward
• Continue until no more leaves exist

After this process, the remaining nodes are exactly the cycle nodes.

Once we know the cycle nodes, we can perform a multi source BFS starting from all cycle nodes simultaneously.

This BFS computes the shortest distance from every node to the nearest cycle node in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Run BFS from every node
Optimal	O(n)	O(n)	Leaf trimming + multi source BFS

Algorithm Walkthrough

Step 1, Build the Graph

Create an adjacency list for the graph and compute the degree of every node.

The adjacency list allows efficient traversal of neighbors, and the degree array helps identify leaves.

Step 2, Find Initial Leaves

Any node with degree 1 is definitely not part of the cycle.

Push all such nodes into a queue.

These nodes form the starting layer for the trimming process.

Step 3, Trim Leaves Iteratively

Process the queue:

1. Remove a leaf node
2. Mark it as not part of the cycle
3. Reduce the degree of all its neighbors
4. If a neighbor becomes degree 1, push it into the queue

This process peels away outer tree layers one by one.

Eventually, only cycle nodes remain because cycle nodes always maintain degree at least 2 within the remaining graph.

Step 4, Initialize BFS from Cycle Nodes

After trimming finishes:

• Nodes not removed are cycle nodes
• Their distance is 0

Push all cycle nodes into a BFS queue.

Step 5, Run Multi Source BFS

Perform BFS starting from all cycle nodes simultaneously.

For each popped node:

1. Visit its neighbors
2. If a neighbor has not been assigned a distance:

• Set distance = current distance + 1
• Push neighbor into the queue

Because BFS expands level by level, the first time a node is visited gives the shortest distance to the cycle.

Why it works

The trimming phase correctly identifies cycle nodes because any node outside the cycle eventually becomes a leaf after repeatedly removing outer layers.

Cycle nodes are never removed because every cycle node always retains at least two neighbors inside the cycle.

The multi source BFS is correct because BFS in an unweighted graph computes shortest path distances. Starting BFS from all cycle nodes simultaneously guarantees that each node receives the minimum distance to any cycle node.

Python Solution

from collections import deque
from typing import List

class Solution:
    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]
        degree = [0] * n

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            degree[u] += 1
            degree[v] += 1

        queue = deque()

        for node in range(n):
            if degree[node] == 1:
                queue.append(node)

        in_cycle = [True] * n

        while queue:
            node = queue.popleft()
            in_cycle[node] = False

            for neighbor in graph[node]:
                degree[neighbor] -= 1

                if degree[neighbor] == 1:
                    queue.append(neighbor)

        distance = [-1] * n
        queue = deque()

        for node in range(n):
            if in_cycle[node]:
                distance[node] = 0
                queue.append(node)

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:
                if distance[neighbor] == -1:
                    distance[neighbor] = distance[node] + 1
                    queue.append(neighbor)

        return distance

The implementation begins by constructing the adjacency list and computing node degrees.

The first BFS style process performs leaf trimming. Every node with degree 1 is removed, and its neighbors have their degrees reduced. Nodes that survive this process are exactly the cycle nodes.

The second BFS computes shortest distances. Since all cycle nodes are inserted initially with distance 0, the BFS naturally expands outward layer by layer, assigning the minimum distance to every non cycle node.

The use of iterative queues avoids recursion depth problems that could occur with deep graphs.

Go Solution

package main

import "container/list"

func distanceToCycle(n int, edges [][]int) []int {
	graph := make([][]int, n)
	degree := make([]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)

		degree[u]++
		degree[v]++
	}

	queue := list.New()

	for i := 0; i < n; i++ {
		if degree[i] == 1 {
			queue.PushBack(i)
		}
	}

	inCycle := make([]bool, n)

	for i := 0; i < n; i++ {
		inCycle[i] = true
	}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		node := front.Value.(int)
		inCycle[node] = false

		for _, neighbor := range graph[node] {
			degree[neighbor]--

			if degree[neighbor] == 1 {
				queue.PushBack(neighbor)
			}
		}
	}

	distance := make([]int, n)

	for i := 0; i < n; i++ {
		distance[i] = -1
	}

	queue = list.New()

	for i := 0; i < n; i++ {
		if inCycle[i] {
			distance[i] = 0
			queue.PushBack(i)
		}
	}

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		node := front.Value.(int)

		for _, neighbor := range graph[node] {
			if distance[neighbor] == -1 {
				distance[neighbor] = distance[node] + 1
				queue.PushBack(neighbor)
			}
		}
	}

	return distance
}

The Go implementation follows the same logic as the Python version.

The primary difference is queue management. Go does not have a built in deque like Python, so container/list is used for BFS queues.

Slices are used for adjacency lists and arrays. Since all distances are bounded by n, integer overflow is not a concern.

Worked Examples

Example 1

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

Initial Graph

Node	Neighbors	Degree
0	[1]	1
1	[2,3,0]	3
2	[1,4,5]	3
3	[4,1]	2
4	[2,3]	2
5	[2,6]	2
6	[5]	1

Leaf Trimming

Initial queue:

[0, 6]

Process node 0:

• Remove 0
• Degree of 1 becomes 2

Queue:

[6]

Process node 6:

• Remove 6
• Degree of 5 becomes 1
• Push 5

Queue:

[5]

Process node 5:

• Remove 5
• Degree of 2 becomes 2

Queue becomes empty.

Remaining cycle nodes:

1, 2, 3, 4

Multi Source BFS

Initial distances:

Node	Distance
1	0
2	0
3	0
4	0

Queue:

[1,2,3,4]

From node 1:

• Visit 0
• distance[0] = 1

From node 2:

• Visit 5
• distance[5] = 1

From node 5:

• Visit 6
• distance[6] = 2

Final result:

[1,0,0,0,0,1,2]

Example 2

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

Initial Degrees

Node	Degree
0	3
1	2
2	3
3	3
4	1
5	1
6	3
7	1
8	1

Initial leaves:

[4,5,7,8]

Trimming Process

Remove 4:

• Degree of 3 becomes 2

Remove 5:

• Degree of 3 becomes 1
• Push 3

Remove 7:

• Degree of 6 becomes 2

Remove 8:

• Degree of 6 becomes 1
• Push 6

Remove 3:

• Degree of 0 becomes 2

Remove 6:

• Degree of 2 becomes 2

Remaining cycle nodes:

0, 1, 2

BFS Distances

Cycle nodes start with distance 0.

BFS expands:

• Node 3 gets distance 1
• Node 6 gets distance 1
• Nodes 4 and 5 get distance 2
• Nodes 7 and 8 get distance 2

Final result:

[0,0,0,1,2,2,1,2,2]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each edge and node is processed a constant number of times
Space	O(n)	Adjacency list, degree array, queue, and distance array

The graph contains exactly n edges, so the number of edges is linear in the number of nodes.

During leaf trimming, every node enters the queue at most once, and every edge is examined at most twice.

During BFS, each node and edge is again processed at most once.

Therefore, the overall complexity remains linear.

Test Cases

from typing import List

class Solution:
    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:
        from collections import deque

        graph = [[] for _ in range(n)]
        degree = [0] * n

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
            degree[u] += 1
            degree[v] += 1

        queue = deque()

        for i in range(n):
            if degree[i] == 1:
                queue.append(i)

        in_cycle = [True] * n

        while queue:
            node = queue.popleft()
            in_cycle[node] = False

            for neighbor in graph[node]:
                degree[neighbor] -= 1

                if degree[neighbor] == 1:
                    queue.append(neighbor)

        distance = [-1] * n
        queue = deque()

        for i in range(n):
            if in_cycle[i]:
                distance[i] = 0
                queue.append(i)

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:
                if distance[neighbor] == -1:
                    distance[neighbor] = distance[node] + 1
                    queue.append(neighbor)

        return distance

sol = Solution()

# Example 1
assert sol.distanceToCycle(
    7,
    [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]
) == [1,0,0,0,0,1,2]

# Example 2
assert sol.distanceToCycle(
    9,
    [[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]]
) == [0,0,0,1,2,2,1,2,2]

# Smallest possible cycle, all nodes in cycle
assert sol.distanceToCycle(
    3,
    [[0,1],[1,2],[2,0]]
) == [0,0,0]

# Single chain attached to cycle
assert sol.distanceToCycle(
    5,
    [[0,1],[1,2],[2,0],[2,3],[3,4]]
) == [0,0,0,1,2]

# Multiple branches attached to cycle
assert sol.distanceToCycle(
    8,
    [[0,1],[1,2],[2,0],[0,3],[3,4],[1,5],[5,6],[6,7]]
) == [0,0,0,1,2,1,2,3]

# Long linear branch
assert sol.distanceToCycle(
    6,
    [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5]]
) == [0,0,0,1,2,3]

# Cycle not involving node 0
assert sol.distanceToCycle(
    6,
    [[1,2],[2,3],[3,1],[0,1],[3,4],[4,5]]
) == [1,0,0,0,1,2]

Test	Why
Example 1	Verifies standard mixed structure
Example 2	Verifies multiple trees attached to cycle
Pure cycle graph	Ensures all answers become zero
Single branch	Tests increasing distance propagation
Multiple branches	Tests BFS expansion from several cycle nodes
Long chain	Tests deep distance computation
Cycle excluding node 0	Ensures no assumptions about cycle position

Edge Cases

One important edge case occurs when the entire graph is a cycle. In this situation, no node has degree 1, so the trimming queue starts empty. The algorithm correctly identifies every node as part of the cycle, and the BFS initializes all distances to 0.

Another important case is a very deep branch attached to the cycle. A recursive DFS implementation could overflow the call stack when the depth approaches 100000. This implementation avoids that issue entirely by using iterative queues for both trimming and BFS.

A third important edge case involves cycle placement. The cycle can appear anywhere in the graph and does not necessarily involve node 0. Some incorrect solutions accidentally assume the cycle begins near the start of traversal. This algorithm avoids such assumptions because it identifies cycle nodes purely through degree reduction.

A subtle edge case occurs when removing one leaf causes another node to become a leaf. If the algorithm does not dynamically update degrees and enqueue newly formed leaves, some non cycle nodes would incorrectly remain marked as cycle nodes. The implementation handles this correctly by decrementing neighbor degrees immediately during trimming.