Distance to a Cycle in Undirected Graph

Distance to a Cycle in Undirected Graph

What is this problem about?

In the Distance to a Cycle in Undirected Graph coding problem, you are given a connected undirected graph that contains exactly one cycle (a unicyclic graph). Your goal is to find the shortest distance from every node in the graph to the nearest node that is part of that cycle. Nodes that are part of the cycle itself have a distance of 0.

Why is this asked in interviews?

Akuna Capital uses this problem to test a candidate's mastery of Graph interview patterns, specifically cycle detection and multi-source traversal. It requires a two-step process: first identifying the "core" cycle and then propagating distances outward. It tests your ability to use Breadth-First Search (BFS) and Topological Sort (Kahn's algorithm) concepts in a creative way.

Algorithmic pattern used

The most efficient approach uses a modified Topological Sort (Kahn's algorithm for cycles) followed by BFS.

1. Identify the Cycle: In an undirected graph with one cycle, you can repeatedly remove all nodes with degree 1 (leaves) until only the cycle remains.
2. Multi-source BFS: Once the cycle nodes are identified, add them all to a BFS queue with distance 0.
3. Propagate: Use BFS to visit all other nodes. The distance to a node will be the distance of its "parent" (the node that added it to the queue) plus 1.

Example explanation

Graph: 0-1, 1-2, 2-0 (cycle), and 2-3 (leaf).

1. Node 3 has degree 1. It is not part of the cycle.
2. Nodes 0, 1, 2 remain. They all have degree 2. They form the cycle.
3. Queue: [0, 1, 2]. Distances: {0:0, 1:0, 2:0}.
4. Process 2: It is connected to 3. Dist[3] = dist[2] + 1 = 1. Result: [0, 0, 0, 1].

Common mistakes candidates make

• Inefficient Cycle Detection: Using DFS to find every cycle node, which can be tricky to implement correctly in an undirected graph compared to the degree-reduction method.
• Redundant BFS: Running a separate BFS for every single node to find the cycle ($O(V \times (V+E))$), which is too slow.
• Graph Representation: Not correctly building an adjacency list for an undirected graph (missing the back-edges).

Interview preparation tip

Understand the relationship between degree and cycles. In a tree, every node can be removed by degree reduction. In a graph with cycles, the "cycle" is the structure that remains after all degree-1 nodes are pruned. This is a powerful Graph interview pattern for reducing complex graphs to their cores.