Distance to a Cycle in Undirected Graph

Ah, the classic problem of finding the distance to a cycle in an undirected graph! It’s like trying to find your way back to the buffet after getting lost in a maze of tables at a wedding. You know there’s a cycle (the buffet line), but how do you get there without bumping into the same guests (nodes) over and over again?

In this problem, you’re given a graph represented by nodes and edges, and your task is to determine the shortest distance from each node to the nearest cycle. It’s like trying to figure out how far you are from the nearest slice of cake—except in this case, the cake is a cycle, and the guests are the nodes.

Solution Links

If you’re feeling adventurous and want to explore other languages, here are some links for you:

Code Solution


class Solution {
  public int[] distanceToCycle(int n, int[][] edges) {
    int[] ans = new int[n];
    List[] graph = new List[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    int[] rank = new int[n];
    Arrays.fill(rank, NO_RANK);
    List cycle = new ArrayList<>();
    getRank(graph, 0, 0, rank, cycle);

    Queue q = cycle.stream().collect(Collectors.toCollection(ArrayDeque::new));
    boolean[] seen = new boolean[n];
    for (final int u : cycle)
      seen[u] = true;

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int u = q.poll();
        for (final int v : graph[u]) {
          if (seen[v])
            continue;
          q.offer(v);
          seen[v] = true;
          ans[v] = step;
        }
      }

    return ans;
  }

  private static final int NO_RANK = -2;

  private int getRank(List[] graph, int u, int currRank, int[] rank, List cycle) {
    if (rank[u] != NO_RANK)
      return rank[u];

    rank[u] = currRank;
    int minRank = currRank;

    for (final int v : graph[u]) {
      if (rank[u] == rank.length || rank[v] == currRank - 1)
        continue;
      final int nextRank = getRank(graph, v, currRank + 1, rank, cycle);
      if (nextRank <= currRank)
        cycle.add(v);
      minRank = Math.min(minRank, nextRank);
    }

    rank[u] = rank.length;
    return minRank;
  }
}

Approach Explanation

The code begins by constructing a graph from the given edges. It initializes a rank array to keep track of the minimum node that can be reached with forward edges. The getRank function is a recursive method that explores the graph to identify cycles and their ranks. Once the cycles are identified, a breadth-first search (BFS) is performed to calculate the distance from each node to the nearest cycle.

Time and Space Complexity

Time Complexity: O(N + E), where N is the number of nodes and E is the number of edges. This is because we traverse each node and edge once.
Space Complexity: O(N), primarily for storing the graph and the rank array.

Real-World Example

Imagine you’re at a theme park, and you want to find the nearest restroom (the cycle). You start at your current location (a node) and ask around (traverse the graph). Some paths lead you in circles (cycles), while others take you further away. The goal is to find the shortest path to the restroom without getting lost in the maze of attractions (nodes).