Distance to a Cycle in Undirected Graph

Explore More Solutions

Problem Description

Ah, the classic “Distance to a Cycle in Undirected Graph” problem! Imagine you’re at a party, and you realize that everyone is just going around in circles—literally! You want to find out how far each person is from the nearest cycle of friends. In graph terms, this means figuring out the shortest distance from each node to the nearest cycle in an undirected graph.

So, if you have a group of friends (nodes) and their connections (edges), your task is to determine how far each friend is from the nearest group of friends that are just going around in circles. Sounds like a typical day in social life, right?

Code Solution


class Solution {
 public:
  vector distanceToCycle(int n, vector>& edges) {
    vector ans(n);
    vector> graph(n);

    for (const vector& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    vector cycle;
    getRank(graph, 0, 0, vector(n, NO_RANK), cycle);

    queue q;
    vector seen(n);
    for (const int u : cycle) {
      q.push(u);
      seen[u] = true;
    }

    for (int step = 1; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const int u = q.front();
        q.pop();
        for (const int v : graph[u]) {
          if (seen[v])
            continue;
          q.push(v);
          seen[v] = true;
          ans[v] = step;
        }
      }

    return ans;
  }

 private:
  static constexpr int NO_RANK = -2;

  int getRank(const vector>& graph, int u, int currRank,
              vector&& rank, vector& cycle) {
    if (rank[u] != NO_RANK)
      return rank[u];

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

    for (const int v : graph[u]) {
      if (rank[v] == rank.size() || rank[v] == currRank - 1)
        continue;
      const int nextRank =
          getRank(graph, v, currRank + 1, std::move(rank), cycle);
      if (nextRank <= currRank)
        cycle.push_back(v);
      minRank = min(minRank, nextRank);
    }

    rank[u] = rank.size();
    return minRank;
  }
};

Approach Explanation

The solution employs a depth-first search (DFS) to explore the graph and identify cycles. It maintains a ranking system to track the minimum distance from each node to the nearest cycle. Once the cycles are identified, a breadth-first search (BFS) is used to calculate the shortest distance from each node to the nearest cycle.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N + E)
Space Complexity	O(N)

Real-World Example

Imagine you're at a large family reunion, and everyone is mingling. Some family members are in a tight-knit group (the cycle), while others are scattered around. You want to find out how far each person is from that group. By applying the algorithm, you can determine the shortest distance for each family member to reach the group, ensuring no one feels left out—just like in the graph!