2204. Distance to a Cycle in Undirected Graph

HardDepth-First SearchBreadth-First SearchUnion FindGraph

Problem Description

This problem describes a graph which contains exactly one cycle, and our task is to find the minimum distance from each node to any of the nodes that are part of the cycle. To put it simply, suppose you have an undirected graph with a certain number of nodes, and this graph forms exactly one cycle, that is, a closed loop where you can start from one node and return to it by traversing through other connected nodes without repeating any node except the starting/ending node.

For example, if you have a triangle (which is a simple 3-node cycle) connected to a line of several more nodes, then the task is to find out how many steps you would have to take to get from any of the nodes in the line to any of the nodes in the cycle.

The information given to solve this problem includes:

n: The total number of nodes in the graph.
edges: A list of pairs, where each pair represents a bidirectional edge between the two nodes mentioned in the pair.

The output is an array where the value at each index i corresponds to the minimum number of steps needed to reach the cycle from node i.

Flowchart Walkthrough

Let's proceed by using the Flowchart to analyze LeetCode 2204, "Distance to a Cycle in Undirected Graph," and determine the appropriate algorithm pattern:

Is it a graph?

Yes: This problem involves an undirected graph where the goal is to find distances to a cycle in the graph.

Is it a tree?

No: The presence of cycles means that the graph cannot be a tree.

Is the problem related to directed acyclic graphs (DAGs)?

No: The primary feature of this problem is the existence of cycles, which conflicts with the acyclical nature of DAGs.

Is the problem related to shortest paths?

Yes: The task is to compute the shortest path from nodes to any node in a cycle.

Is the graph weighted?

No: The description does not specify that edges have varying weights; the concern is merely the count of edges (steps).

Conclusion: Even though the direct flowchart paths specifically suggest algorithms like Dijkstra's for weighted graphs, the absence of weights simplifies our approach. Considering the requirement for shortest paths in an unweighted graph, BFS (Breadth-First Search) is typically the more fitting choice than DFS for unweighted shortest path problems. However, let's add that if the problem had additional constraints or required exploring structures like paths or backtracking, DFS could potentially be useful. Yet, for finding shortest distances in an unweighted setting, BFS is more straightforward and effective, given its ability to handle levels of depth (or distance) using queues efficiently.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The solution approach uses a technique similar to topological sorting, which is often applied to Directed Acyclic Graphs (DAGs). Here, although we have an undirected graph with a cycle, we can use a similar layer-by-layer peeling approach.

Since the problem guarantees that there's only one cycle, every node that is not a part of the cycle will have either one or two connections. The nodes with one connection are leaf nodes, which are not part of the cycle and are at the end of paths leading to the cycle.

Here's how we arrive at the solution with this insight:

Create a graph representation using an adjacency list where each node is a key to a set of adjacent nodes.
Identify leaf nodes (nodes with a single connection). These are the furthest from the cycle and will be our starting point.
Remove the leaf nodes from the graph and update the connection count of their connected nodes. Like peeling an onion, we're stripping the graph from the outside in.
Queue up any nodes that become leaves after removing a leaf node.
Record the removal sequence and for each node, keep track of the adjacent node that brings it closest to the cycle.
Once we reach the core cycle (no more leaves can be removed), we can reverse the removal sequence and count back from the cycle, incrementing the distance for each node from the node that brought it closest to the cycle.
After processing all nodes, the final array will represent the minimum distance of each node from the closest cycle node.

The implementation details such as tracking the removal sequence, counting distances, and the queuing mechanism make the solution efficient with a time complexity of O(n), which means it operates directly proportional to the number of nodes in the graph.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Solution Approach

The implementation of the solution involves a smart use of graph properties and breadth-first search, which allows us to systematically remove leaves until we find the cycle. Here is a closer look at the approach, referring to the Reference Solution Approach above.

Graph representation: We start by constructing an adjacency list g, where g[i] will contain a set of all adjacent nodes to the node i. This facilitates efficient addition and removal of edges.
Identifying leaves: We initialize a queue q and populate it with all nodes that have a degree of 1, which indicates they are leaves. Nodes with only one connection are leaves and are removed first.
Removing leaves: With the queue populated initially with leaves, we proceed to remove these nodes from the graph. We use a loop to pop elements from q and, for each, we remove the corresponding edge from the graph by deleting the node from its neighbor's set. If deletion of the node causes any of its neighbors to become a leaf, we add that neighbor to the queue.
Tracking node relations: Parallel to removal, we record the sequence of removal in a list seq to keep track of which node came from which in reverse order. Along with this, we use an array f to keep track of which neighbor node a given node should go towards to get closer to the cycle – f[i] is set to j when node i is removed and j is its neighbor.
Computing distances: Once we have removed all nodes except for those in the cycle (queue is empty), we have each node's direct connection that is closest to the cycle. We then initialize an array ans to hold the distances for each node. We reverse the sequence seq and start backtracking, setting ans[i] = ans[f[i]] + 1, which means each node's distance is one more than its connected node's distance that is closer to the cycle.
Returning results: The final array ans now contains the minimum distance from the cycle for all nodes. We return this array.

This method effectively peels away layers of the graph until the cycle is exposed. It leverages the fact that a node becomes a leaf when all its other connections have been removed in the process. Since we only traverse each node and edge once, the time complexity of the algorithm is O(n).

The pattern used here is similar to the one used in topological sorting, but instead of sorting, we use it to calculate distances from the cycle. The Python code implements this algorithm using a deque from the collections module for efficient removal of elements from both ends of the queue and a defaultdict from the collections module to handle the adjacency list without having to check for the existence of keys.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a simple example to illustrate the solution approach described above:

Suppose we have the following graph with 6 nodes:

Here, nodes 1, 2, and 3 form a cycle, and nodes 4, 5, and 6 form a path leading to the cycle, with 6 being the last node.

Now, let's walk through the implementation steps:

Graph representation: We create an adjacency list representation of the graph:

g = {1: {2}, 2: {1, 3}, 3: {2, 4}, 4: {3, 5}, 5: {4, 6}, 6: {5}}

Identifying leaves: We would put 1 and 6 in a queue q since these nodes have only a single connection:
```
q = [1, 6]
```
Removing leaves: We begin by dequeuing 1 and then 6 and removing them from the graph representation. We also check their neighbors:
- Upon removing 1, 2 still has two connections, so it's not added to the queue.
- Upon removing 6, we find that 5 now is a leaf, so we enqueue 5.
Tracking node relations: As we remove each node, we would record its neighbor node:
- f[1] is not relevant since it's part of the cycle.
- f[6] would be 5, since that is the neighbor leading towards the cycle.
Computing distances: We continue this process, removing 5, and then 4. 4 becomes a leaf node after 5 is removed. As we go, we update f[5] = 4 and f[4] = 3. Now nodes 2 and 3 are both part of the cycle and q is empty, so we stop.
Returning results: We then assign distances using our f array, where each node's minimum distance to the cycle is 1 more than the distance of f[i] to the cycle.
```
ans = [0, 0, 0, 1, 2, 3]
```
Nodes 1, 2, and 3 are part of the cycle and have a distance of 0 from the cycle. Node 4 is next to 3, which is in the cycle, so its distance is 1. Node 5 is next to 4, so its distance is ans[4] + 1 = 2. Similarly, 6 is ans[5] + 1 = 3.

Thus, we have walked through this small example graph using the described solution approach, resulting in the final answer for the minimum distance of each node to the cycle.

Solution Implementation

1from collections import defaultdict, deque
2from typing import List
3
4class Solution:
5    def distanceToCycle(self, n: int, edges: List[List[int]]) -> List[int]:
6        # Create a graph using a dictionary of sets to represent adjacency lists
7        graph = defaultdict(set)
8        # Build the graph from the edges list
9        for a, b in edges:
10            graph[a].add(b)
11            graph[b].add(a)
12      
13        # Initialize a queue with all nodes that have only one connection (leaf nodes)
14        queue = deque(i for i in range(n) if len(graph[i]) == 1)
15      
16        # 'parent' will hold the next node in graph for leaf nodes
17        parent = [0] * n
18      
19        # 'sequence' will record the order in which nodes are visited
20        sequence = []
21      
22        # Process the nodes until the queue is empty
23        while queue:
24            # Pop the first node from the left of the deque
25            current = queue.popleft()
26            # Append to the visitation sequence
27            sequence.append(current)
28          
29            # Check all neighbouring nodes
30            for neighbor in graph[current]:
31                # Remove the current node from the neighbor's set
32                graph[neighbor].remove(current)
33                # Record the neighbor as the parent
34                parent[current] = neighbor
35                # If the neighbor has become a leaf node, add it to the queue
36                if len(graph[neighbor]) == 1:
37                    queue.append(neighbor)
38            # Clear the nodes set to mark it as visited
39            graph[current].clear()
40      
41        # 'distances' will store the distance from each node to the cycle
42        distances = [0] * n
43      
44        # Propagate distances from the leaf nodes to their parents
45        for node in reversed(sequence):
46            distances[node] = distances[parent[node]] + 1  # Increment distance from the cycle
47
48        # Return the calculated distances
49        return distances
50

1class Solution {
2
3    public int[] distanceToCycle(int n, int[][] edges) {
4        // Create an adjacency list to represent the graph
5        Set<Integer>[] graph = new Set[n];
6        // Initialize each node with a new hash set.
7        Arrays.setAll(graph, k -> new HashSet<>());
8        // Populate the adjacency list with the edges given.
9        for (var edge : edges) {
10            int node1 = edge[0], node2 = edge[1];
11            graph[node1].add(node2);
12            graph[node2].add(node1);
13        }
14      
15        Deque<Integer> queue = new ArrayDeque<>();
16        // Enqueue nodes with only one neighbor, which are leaf nodes in the tree.
17        for (int i = 0; i < n; ++i) {
18            if (graph[i].size() == 1) {
19                queue.offer(i);
20            }
21        }
22      
23        // Array to keep track of the farthest node in the path from each node.
24        int[] pathFarthestNode = new int[n];
25        Deque<Integer> sequence = new ArrayDeque<>();
26        // Process nodes in the queue until empty.
27        while (!queue.isEmpty()) {
28            int currentNode = queue.poll();
29            sequence.push(currentNode);
30            for (int neighbor : graph[currentNode]) {
31                // Remove the edge between currentNode and its neighbor to 'shrink' the tree.
32                graph[neighbor].remove(currentNode);
33                // Record the neighbor as the farthest node in the path from the current node.
34                pathFarthestNode[currentNode] = neighbor;
35                // If after removal, neighbor becomes a leaf node, enqueue it.
36                if (graph[neighbor].size() == 1) {
37                    queue.offer(neighbor);
38                }
39            }
40        }
41      
42        // This will hold the distances from each node to the cycle.
43        int[] distances = new int[n];
44        // Backtrack from leaf nodes towards the cycle, assigning distances.
45        while (!sequence.isEmpty()) {
46            int currentNode = sequence.pop();
47            distances[currentNode] = distances[pathFarthestNode[currentNode]] + 1;
48        }
49        return distances;
50    }
51  
52}
53

1#include <vector>
2#include <queue>
3#include <unordered_set>
4
5using namespace std;
6
7class Solution {
8public:
9    vector<int> distanceToCycle(int n, vector<vector<int>>& edges) {
10        // Create graph with adjacency list representation.
11        vector<unordered_set<int>> graph(n);
12        for (auto& edge : edges) {
13            int a = edge[0], b = edge[1];
14            graph[a].insert(b);
15            graph[b].insert(a);
16        }
17
18        // Initialize a queue for leaf nodes.
19        queue<int> leaves;
20        // Step 1: Start by adding all leaves to the queue.
21        for (int i = 0; i < n; ++i) {
22            if (graph[i].size() == 1) {
23                leaves.push(i);
24            }
25        }
26
27        // Initialize an array to store the "parent" for each node.
28        vector<int> parents(n, -1);
29        // Initialize an array to record the order of processed nodes.
30        vector<int> processingOrder;
31
32        // Step 2: Keep removing leaves until the queue is empty.
33        while (!leaves.empty()) {
34            int currentLeaf = leaves.front();
35            leaves.pop();
36            processingOrder.push_back(currentLeaf);
37
38            // Process all adjacent nodes.
39            for (int neighbor : graph[currentLeaf]) {
40                // Remove the connection to the leaf.
41                graph[neighbor].erase(currentLeaf);
42                // Set the parent of the current leaf.
43                parents[currentLeaf] = neighbor;
44              
45                // If the neighbor turned into a leaf, add it to the queue.
46                if (graph[neighbor].size() == 1) {
47                    leaves.push(neighbor);
48                }
49            }
50            // Clear the node's adjacency list now that it's been processed.
51            graph[currentLeaf].clear();
52        }
53
54        // Initialize an array to hold the answer (distances to the cycle).
55        vector<int> distances(n, 0);
56
57        // Step 3: Traverse nodes in reverse order of their processing 
58        // to calculate the distance from each node to the cycle.
59        for (int i = processingOrder.size() - 1; i >= 0; --i) {
60            int currentNode = processingOrder[i];
61            if (parents[currentNode] != -1) {
62                distances[currentNode] = distances[parents[currentNode]] + 1;
63            }
64        }
65
66        // Return the array containing distances to the cycle for each node.
67        return distances;
68    }
69};
70

1// Define a function that calculates the distance of each node to the nearest cycle in a graph
2function distanceToCycle(n: number, edges: number[][]): number[] {
3    // Initialize an array to represent the adjacency list of the graph
4    const adjacencyList: Set<number>[] = new Array(n).fill(0).map(() => new Set<number>());
5  
6    // Populate the adjacency list with the given edges
7    for (const [node1, node2] of edges) {
8        adjacencyList[node1].add(node2);
9        adjacencyList[node2].add(node1);
10    }
11  
12    // Initialize a queue to store nodes with only one neighbor (leaf nodes)
13    const queue: number[] = [];
14  
15    // Loop through all nodes to find leaf nodes
16    for (let i = 0; i < n; ++i) {
17        if (adjacencyList[i].size === 1) {
18            queue.push(i);
19        }
20    }
21  
22    // Initialize an array to store the parent/following node in the path for each node
23    const followingNode: number[] = Array(n).fill(0);
24  
25    // Initialize an array to store the processing sequence of nodes
26    const sequence: number[] = [];
27  
28    // Process the graph starting from the leaf nodes
29    while (queue.length) {
30        const currentNode = queue.pop()!;
31        sequence.push(currentNode);
32      
33        // Process all adjacent nodes of the current node
34        for (const adjacentNode of adjacencyList[currentNode]) {
35            // Remove the current node from its neighbor's set to simulate "peeling" the graph
36            adjacencyList[adjacentNode].delete(currentNode);
37            followingNode[currentNode] = adjacentNode;
38          
39            // If after removal, the neighbor becomes a leaf node, add it to the queue
40            if (adjacencyList[adjacentNode].size === 1) {
41                queue.push(adjacentNode);
42            }
43        }
44      
45        // Clear the current node's neighbors as it has already been processed
46        adjacencyList[currentNode].clear();
47    }
48  
49    // Initialize an array to hold the distances to the nearest cycle for each node
50    const distances: number[] = Array(n).fill(0);
51  
52    // Calculate the distances starting from the leaf nodes and moving towards the cycle
53    while (sequence.length) {
54        const currentNode = sequence.pop()!;
55        distances[currentNode] = distances[followingNode[currentNode]] + 1;
56    }
57  
58    // Return an array of distances to the nearest cycle for each node
59    return distances;
60}
61

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the number of edges and the number of vertices (n) in the graph. Here's the breakdown:

Building the graph: The code iterates through each edge once to build the graph, which takes O(E) time, with E being the number of edges.
Creating the initial queue: The queue is populated with nodes of degree 1. In the worst case, this could be all nodes, so it's O(n).
Processing the queue: Each node is processed once and removed from the graph. When a node is processed, it updates its neighbors and reduces their degrees. Since each edge is effectively considered twice (once for each vertex it connects), and since each removal is an O(1) operation due to the set data structure used for adjacency lists, this part of the algorithm is O(n + E).
Reversing the seq list and computing the answer: The reversal is O(n), and then for each node in seq, computing the distance is O(1). Hence, this part is also O(n).

Overall, the time complexity is the sum of these operations which is O(E) + O(n) + O(n + E) + O(n), simplifying to O(n + E).

Space Complexity

The space complexity is determined by the space needed to store the graph, queue, and the answer:

Graph storage: Each edge is stored twice (once for each vertex it connects), so graph storage is O(E).
Queue storage: In the worst case, the queue could contain all vertices before processing starts. So it's O(n).
seq list: The seq list eventually contains all the vertices, so it is O(n).
Auxiliary arrays f and ans: Each requires O(n) space.

The overall space complexity is the sum of these, O(E) + O(n) + O(n) + O(n) + O(n), which simplifies to O(n + E).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan: