Taro Logo

Distance to a Cycle in Undirected Graph

Hard
Asked by:
Profile picture
18 views
Topics:
GraphsTrees

You are given a positive integer n representing n nodes in a connected undirected graph, where the nodes are numbered from 0 to n - 1.

You are also given an array edges, where edges[i] = [ui, vi] denotes that there is an edge between nodes ui and vi in the graph.

The distance from a node v to a cycle is the minimum number of edges needed to reach a node in a cycle from node v. If node v is part of a cycle, its distance is 0.

Return an array answer of length n, where answer[i] is the distance from node i to a cycle.

Example 1:

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

Example 2:

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

Constraints:

  • 3 <= n <= 105
  • n <= edges.length <= 2 * n
  • edges[i].length == 2
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • There are no repeated edges.
  • The graph is connected and has exactly one cycle.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Is the graph undirected and connected, with exactly one simple cycle?
  2. Is distance measured in edges, with every node on the cycle at distance zero?
  3. Are node labels consecutive integers starting at zero?
  4. Should a repeated discovery of the same cycle be stored only once?
  5. For a node off the cycle, is the distance the number of edges in a breadth-first walk?

Brute Force Solution

Approach

A walk is started from every node, and a back edge to a node already on the current path records a cycle when that cycle has at least three nodes. Cycles are stored once in sorted label order. A node that appears in any stored cycle gets distance zero, and every other node breadth-first searches toward the stored cycle nodes in that order, keeping the distance of the first search that reaches its target.

Here's how the algorithm would work step-by-step:

  1. Build an undirected adjacency list from the edges.
  2. From every node, walk simple paths while copying the path and the nodes already visited.
  3. When a neighbor is already on the path, record the cycle from that neighbor to the current node if it is longer than two.
  4. Store each cycle once, sorted by node label.
  5. Give distance zero to every node that belongs to a stored cycle.
  6. For every other node, search outward toward the cycle nodes in label order.
  7. Keep the distance of the first search that reaches its target, then move to the next cycle if one exists.

Code Implementation

from collections import deque

def distance_to_cycle(number_of_nodes, edges):
    adjacency_list = [[] for _ in range(number_of_nodes)]
    for source, destination in edges:
        adjacency_list[source].append(destination)
        adjacency_list[destination].append(source)

    all_cycles = []

    def find_all_cycles_dfs(current_node, parent_node, path, visited_nodes):
        path.append(current_node)
        visited_nodes.add(current_node)

        for neighbor in adjacency_list[current_node]:
            if neighbor == parent_node:
                continue
            if neighbor in visited_nodes:
                try:
                    cycle_start_index = path.index(neighbor)
                    new_cycle = path[cycle_start_index:]
                    if len(new_cycle) > 2:
                        # We sort the cycle to store a canonical representation, avoiding duplicates.
                        sorted_cycle = tuple(sorted(new_cycle))
                        if sorted_cycle not in all_cycles:
                            all_cycles.append(sorted_cycle)
                except ValueError:
                    pass
            else:
                find_all_cycles_dfs(neighbor, current_node, list(path), set(visited_nodes))
    
    # Systematically explore from every node to find all possible cycles.
    for start_node in range(number_of_nodes):
        find_all_cycles_dfs(start_node, -1, [], set())

    all_cycle_nodes = set()
    for cycle in all_cycles:
        for node in cycle:
            all_cycle_nodes.add(node)

    distances = [0] * number_of_nodes

    for current_node in range(number_of_nodes):
        if current_node in all_cycle_nodes:
            distances[current_node] = 0
            continue

        min_distance_to_any_cycle = float('inf')
        
        # For a given node, we must check its distance to every cycle to find the absolute minimum.
        for cycle in all_cycles:
            for node_in_cycle in cycle:
                # A breadth-first search guarantees finding the shortest path in an unweighted graph.
                queue = deque([(current_node, 0)])
                visited_bfs = {current_node}
                found_path = False
                while queue:
                    bfs_node, distance = queue.popleft()
                    if bfs_node == node_in_cycle:
                        min_distance_to_any_cycle = min(min_distance_to_any_cycle, distance)
                        found_path = True
                        break
                    for neighbor in adjacency_list[bfs_node]:
                        if neighbor not in visited_bfs:
                            visited_bfs.add(neighbor)
                            queue.append((neighbor, distance + 1))
                if found_path:
                    # Optimization for this inner loop, we found dist to this cycle
                    break

        distances[current_node] = min_distance_to_any_cycle

    return distances

Big(O) Analysis

Time Complexity
O(n^3) – Let n be the number of nodes. A fresh walk starts at every node, and each step copies the path and the set of nodes already on that path. On a connected graph with one cycle, a walk from one start creates a linear number of calls, and each copy scans a path of length up to n, so discovery from every start is cubic. After the cycles are known, every node off a cycle searches toward the stored cycle nodes, and each search walks the edges once. Those searches add another cubic term, so the total time is O(n^3).
Space Complexity
O(n^2) – Each recursive call keeps its own copy of the path and of the visited nodes. The deepest path has one entry per node, and the stack can hold one such copy per level, which is quadratic. The list of cycles and the adjacency lists are proportional to n when the number of edges is linear. The distance array has one entry per node. The extra memory is O(n^2).

Optimal Solution

Approach

Leaves are removed repeatedly until every remaining node has more than one neighbor, which leaves the unique cycle. Those cycle nodes start a breadth-first walk at distance zero. Each following layer is exactly one edge farther from the cycle, so the first time a node is reached is its distance.

Here's how the algorithm would work step-by-step:

  1. Build the undirected adjacency list and the degree of every node.
  2. Queue every node whose degree is one.
  3. Remove a queued node from the cycle set and decrease the degree of each neighbor.
  4. Queue a neighbor when its degree falls to one.
  5. Give every surviving cycle node distance zero and place it in a shared queue.
  6. Process the queue one layer at a time, increasing the distance before the layer is expanded.
  7. Write that distance onto each unvisited neighbor and return the distance array.

Code Implementation

def distance_to_cycle(number_of_nodes, edges):
    adjacency_list = [[] for _ in range(number_of_nodes)]
    degrees = [0] * number_of_nodes
    for node1, node2 in edges:
        adjacency_list[node1].append(node2)
        adjacency_list[node2].append(node1)
        degrees[node1] += 1
        degrees[node2] += 1

    # This queue holds nodes that are not part of a cycle, starting with leaf nodes.
    trimming_queue = []
    for node_index in range(number_of_nodes):
        if degrees[node_index] == 1:
            trimming_queue.append(node_index)

    nodes_on_cycle = [True] * number_of_nodes
    while trimming_queue:
        current_node = trimming_queue.pop(0)
        nodes_on_cycle[current_node] = False
        for neighbor_node in adjacency_list[current_node]:
            degrees[neighbor_node] -= 1

            # When a neighbor's degree becomes 1, it's now on a branch that can be trimmed.
            if degrees[neighbor_node] == 1:
                trimming_queue.append(neighbor_node)
    
    distances = [-1] * number_of_nodes
    breadth_first_search_queue = []
    for node_index in range(number_of_nodes):
        if nodes_on_cycle[node_index]:
            distances[node_index] = 0
            breadth_first_search_queue.append(node_index)
    
    current_distance_from_cycle = 0

    # A multi-source BFS starting from all cycle nodes simultaneously finds the shortest path for all other nodes.
    while breadth_first_search_queue:
        queue_size_for_this_level = len(breadth_first_search_queue)
        current_distance_from_cycle += 1
        for _ in range(queue_size_for_this_level):
            current_node = breadth_first_search_queue.pop(0)
            for neighbor_node in adjacency_list[current_node]:
                if distances[neighbor_node] == -1:
                    distances[neighbor_node] = current_distance_from_cycle
                    breadth_first_search_queue.append(neighbor_node)

    return distances

Big(O) Analysis

Time Complexity
O(n) – Let n be the number of nodes. Leaf trimming inspects each node and each edge a constant number of times, because a node is queued when its degree drops to one and is removed once. The later walk starts from every cycle node and moves outward layer by layer. Each node is queued at most once, and each edge is examined a constant number of times. With a linear number of edges, both passes are linear, so the total time is O(n).
Space Complexity
O(n) – The adjacency lists store each edge twice and are proportional to the number of edges, which is linear in n. Degree marks, cycle marks, and distances each use one slot per node. The two queues hold at most every node. No path copies are kept. The extra memory is O(n).

Edge Cases

The node lies on the cycle
How to Handle:
Its distance is zero and no walk away from the cycle is required.
The graph is only a cycle
How to Handle:
Every node stays on the cycle, so every distance is zero.
A tail hangs off the cycle
How to Handle:
Nodes on the cycle stay at zero, and nodes farther along the tail receive larger distances.
A leaf is several edges from the cycle
How to Handle:
The outward walk reports the number of edges from that leaf back to the cycle.
The same cycle is discovered from many starting nodes
How to Handle:
One sorted copy is kept, and later walks reuse that copy.
A node is not on the recorded cycle
How to Handle:
The slow search walks toward the stored cycle nodes in label order and keeps the distance from the first successful walk.