2204. Distance to a Cycle in Undirected Graph - Detailed Explanation

Problem Statement

You are given an undirected graph with n nodes and exactly n edges. Such a graph is guaranteed to have a single cycle with one or more trees (or “branches”) attached to it. For every node in the graph, your task is to calculate its shortest distance (in number of edges) to any node that belongs to the cycle.

For nodes that are part of the cycle, the distance is 0. For nodes attached to the cycle by some path, the distance is the minimum number of edges to traverse from that node to reach any cycle node.

Example 1

• Input:

  • n = 4
  • Edges: [[0,1], [1,2], [2,3], [3,0]]

• Explanation:
  The graph forms a perfect cycle where every node is part of the cycle.

• Output: [0, 0, 0, 0]

Example 2

• Input:
  • n = 6
  • Edges: [[0,1], [1,2], [2,0], [2,3], [3,4], [2,5]]
• Explanation:
  Nodes 0, 1, and 2 form the cycle. Nodes 3 and 5 are directly attached to node 2, and node 4 is attached to node 3.
• Output: [0, 0, 0, 1, 2, 1]
  • Detail:

    • Nodes 0, 1, 2 → distance 0 (they are on the cycle)

    • Node 3 → distance 1 (direct neighbor of node 2)

    • Node 5 → distance 1 (direct neighbor of node 2)

    • Node 4 → distance 2 (node 4 → node 3 → node 2)

Example 3

• Input:
  • n = 7
  • Edges: [[0,1], [1,2], [2,0], [2,3], [3,4], [4,5], [2,6]]
• Explanation:
  The cycle is between nodes 0, 1, and 2. Node 3 is connected to the cycle via node 2; node 4 via node 3; node 5 via node 4; and node 6 is directly connected to node 2.
• Output: [0, 0, 0, 1, 2, 3, 1]

Constraints

• The graph has n nodes and n edges.

• The graph is connected.

• 3 ≤ n ≤ 10⁵ (for example; actual constraint limits may vary).

Hints

1. Cycle Identification:
   Since the graph has exactly one cycle, consider methods to identify the cycle first. One effective strategy is to repeatedly “peel off” the leaves (nodes with degree 1). The remaining nodes after this process are the ones on the cycle.

2. Distance Calculation:
   Once you know the cycle nodes, you can use a multi-source Breadth-First Search (BFS) starting from all cycle nodes simultaneously. This will allow you to calculate the shortest distance for every node from the cycle.

Approaches

Approach 1: Brute Force (Not Recommended)

Explanation

A brute force method would be to, for each node, try to run a DFS or BFS to determine if it is on a cycle or calculate its distance to the cycle by exploring all possible paths. For every node not on the cycle, you would try all paths to see when a cycle node is reached.

Drawbacks

• Inefficient: The repeated searches for each node can lead to high time complexity, especially on larger graphs.

• Complexity: In the worst case, the approach could end up exploring many overlapping subtrees, leading to redundant computations.

Approach 2: Optimal - Peeling Leaves and Multi-Source BFS

This approach is efficient and works in two phases.

Phase 1: Identifying Cycle Nodes (Peeling Leaves)

1. Initialization:

   • Create an array (or list) to record the degree of each node.
   • Use an adjacency list to represent the graph.

2. Peel Off Leaves:

   • Start by adding all nodes with a degree of 1 (leaves) to a queue.

   • Iteratively remove a node from the queue. For each removed leaf, reduce the degree count of its neighbors by 1.

   • If any neighbor becomes a leaf (degree becomes 1) after removal, enqueue it.

   • Continue until no leaves remain. The remaining nodes will be the ones on the cycle.

Phase 2: Calculating Distance Using Multi-Source BFS

1. Initialization:

   • Create a distance array (or list) initialized with -1 for every node.
   • For every node identified as part of the cycle, set its distance to 0 and add it to the BFS queue.

2. Multi-Source BFS:

   • Process nodes from the queue.

   • For each neighboring node, if its distance has not been set (i.e., -1), update it as distance[current] + 1 and add it to the queue.

   • Continue until all reachable nodes are processed.

Complexity Analysis

• Time Complexity: O(n)

  • Peeling off leaves is O(n) since each edge is processed at most once.
  • BFS is also O(n) as each edge is traversed once.

• Space Complexity: O(n)

  • The adjacency list, degree array, and distance array all require O(n) space.

Code Solutions

Python Implementation