We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distance to a Cycle in Undirected Graph

Number: 1347

Difficulty: Hard

Paid? Yes

Companies: Akuna Capital

Problem Description

Given a connected undirected graph with n nodes and exactly one cycle, where nodes are numbered from 0 to n - 1, determine for each node the minimum distance to any node that is part of the cycle. The graph is represented by an edge list and the distance between nodes is defined as the minimum number of edges required to travel between them.

Key Insights

  • The graph contains exactly one cycle; hence, all nodes not on the cycle are attached as trees.
  • A strategy to identify the cycle is to iteratively remove leaf nodes (nodes with degree 1) until a cycle remains.
  • Once the cycle nodes are identified, a multi-source BFS from these nodes efficiently computes the minimum distance for every node.
  • Using a deque or queue makes the BFS traversal efficient for level-order propagation.
  • The solution leverages both DFS-like (or topological peeling) and BFS techniques.

Space and Time Complexity

Time Complexity: O(n) – Each node and edge is processed a constant number of times during the leaf removal and BFS steps. Space Complexity: O(n) – Additional storage is used for the graph representation, degree count, and auxiliary queues/arrays.

Solution

The solution follows a two-step approach:

  1. Identify cycle nodes by iterative leaf removal. Build an adjacency list from the edges and track the degree of each node. Enqueue nodes with degree 1 and remove them until no leaves remain. The remaining nodes are part of the cycle.
  2. Perform a multi-source BFS starting from all cycle nodes (distance assigned as 0). Propagate the distance to every other node in the graph by updating the neighbor’s distance if not already visited.

This approach simplifies cycle detection without needing complex DFS backtracking and then efficiently computes distances using breadth-first traversal.

Code Solutions

from collections import deque

def distanceToCycle(n, edges):
    # Build adjacency list and count degrees
    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

    # Initialize queue with leaves (degree == 1)
    q = deque([i for i in range(n) if degree[i] == 1])
    inCycle = [True] * n  # mark all nodes as potential cycle nodes

    # Remove leaves iteratively
    while q:
        node = q.popleft()
        inCycle[node] = False  # this node is not in the cycle
        for neighbor in graph[node]:
            degree[neighbor] -= 1
            if degree[neighbor] == 1:
                q.append(neighbor)

    # Initialize answer array with -1 (unvisited)
    distance = [-1] * n
    q = deque()
    # Multi-source BFS: start from cycle nodes
    for i in range(n):
        if inCycle[i]:
            distance[i] = 0
            q.append(i)

    # Perform BFS to compute distance from cycle nodes
    while q:
        current = q.popleft()
        for neighbor in graph[current]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[current] + 1
                q.append(neighbor)
    return distance

# Example usage:
n = 7
edges = [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]
print(distanceToCycle(n, edges))  # Expected Output: [1,0,0,0,0,1,2]
← Back to All Questions