2204. Distance to a Cycle in Undirected Graph

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.

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:

1. Create a graph representation using an adjacency list where each node is a key to a set of adjacent nodes.
2. Identify leaf nodes (nodes with a single connection). These are the furthest from the cycle and will be our starting point.
3. 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.
4. Queue up any nodes that become leaves after removing a leaf node.
5. Record the removal sequence and for each node, keep track of the adjacent node that brings it closest to the cycle.
6. 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.
7. 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.

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

Example Walkthrough

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

Suppose we have the following graph with 6 nodes:

11---2---3
2        |
3        4
4        |
5        5
6        |
7        6

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:

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

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

2. Identifying leaves: We would put 1 and 6 in a queue q since these nodes have only a single connection:

   1q = [1, 6]

3. 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.

4. 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.

5. 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.

6. 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.

   1ans = [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

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:

1. 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.

2. 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).

3. 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).

4. 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:

1. Graph storage: Each edge is stored twice (once for each vertex it connects), so graph storage is O(E).

2. Queue storage: In the worst case, the queue could contain all vertices before processing starts. So it's O(n).

3. seq list: The seq list eventually contains all the vertices, so it is O(n).

4. 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.