You are given a positive integer n representing n nodes in a connected undirected graph, where the nodes are numbered from 0 to n - 1.
You are also given an array edges, where edges[i] = [ui, vi] denotes that there is an edge between nodes ui and vi in the graph.
The distance from a node v to a cycle is the minimum number of edges needed to reach a node in a cycle from node v. If node v is part of a cycle, its distance is 0.
Return an array answer of length n, where answer[i] is the distance from node i to a cycle.
Example 1:
Input: n = 9, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6],[6,1],[2,7],[7,8]] Output: [1,0,0,0,1,2,1,1,2]
Example 2:
Input: n = 7, edges = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5],[5,6]] Output: [0,0,0,1,2,3,4]
Constraints:
3 <= n <= 105n <= edges.length <= 2 * nedges[i].length == 20 <= ui, vi <= n - 1ui != viWhen you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
A walk is started from every node, and a back edge to a node already on the current path records a cycle when that cycle has at least three nodes. Cycles are stored once in sorted label order. A node that appears in any stored cycle gets distance zero, and every other node breadth-first searches toward the stored cycle nodes in that order, keeping the distance of the first search that reaches its target.
Here's how the algorithm would work step-by-step:
from collections import deque
def distance_to_cycle(number_of_nodes, edges):
adjacency_list = [[] for _ in range(number_of_nodes)]
for source, destination in edges:
adjacency_list[source].append(destination)
adjacency_list[destination].append(source)
all_cycles = []
def find_all_cycles_dfs(current_node, parent_node, path, visited_nodes):
path.append(current_node)
visited_nodes.add(current_node)
for neighbor in adjacency_list[current_node]:
if neighbor == parent_node:
continue
if neighbor in visited_nodes:
try:
cycle_start_index = path.index(neighbor)
new_cycle = path[cycle_start_index:]
if len(new_cycle) > 2:
# We sort the cycle to store a canonical representation, avoiding duplicates.
sorted_cycle = tuple(sorted(new_cycle))
if sorted_cycle not in all_cycles:
all_cycles.append(sorted_cycle)
except ValueError:
pass
else:
find_all_cycles_dfs(neighbor, current_node, list(path), set(visited_nodes))
# Systematically explore from every node to find all possible cycles.
for start_node in range(number_of_nodes):
find_all_cycles_dfs(start_node, -1, [], set())
all_cycle_nodes = set()
for cycle in all_cycles:
for node in cycle:
all_cycle_nodes.add(node)
distances = [0] * number_of_nodes
for current_node in range(number_of_nodes):
if current_node in all_cycle_nodes:
distances[current_node] = 0
continue
min_distance_to_any_cycle = float('inf')
# For a given node, we must check its distance to every cycle to find the absolute minimum.
for cycle in all_cycles:
for node_in_cycle in cycle:
# A breadth-first search guarantees finding the shortest path in an unweighted graph.
queue = deque([(current_node, 0)])
visited_bfs = {current_node}
found_path = False
while queue:
bfs_node, distance = queue.popleft()
if bfs_node == node_in_cycle:
min_distance_to_any_cycle = min(min_distance_to_any_cycle, distance)
found_path = True
break
for neighbor in adjacency_list[bfs_node]:
if neighbor not in visited_bfs:
visited_bfs.add(neighbor)
queue.append((neighbor, distance + 1))
if found_path:
# Optimization for this inner loop, we found dist to this cycle
break
distances[current_node] = min_distance_to_any_cycle
return distancesLeaves are removed repeatedly until every remaining node has more than one neighbor, which leaves the unique cycle. Those cycle nodes start a breadth-first walk at distance zero. Each following layer is exactly one edge farther from the cycle, so the first time a node is reached is its distance.
Here's how the algorithm would work step-by-step:
def distance_to_cycle(number_of_nodes, edges):
adjacency_list = [[] for _ in range(number_of_nodes)]
degrees = [0] * number_of_nodes
for node1, node2 in edges:
adjacency_list[node1].append(node2)
adjacency_list[node2].append(node1)
degrees[node1] += 1
degrees[node2] += 1
# This queue holds nodes that are not part of a cycle, starting with leaf nodes.
trimming_queue = []
for node_index in range(number_of_nodes):
if degrees[node_index] == 1:
trimming_queue.append(node_index)
nodes_on_cycle = [True] * number_of_nodes
while trimming_queue:
current_node = trimming_queue.pop(0)
nodes_on_cycle[current_node] = False
for neighbor_node in adjacency_list[current_node]:
degrees[neighbor_node] -= 1
# When a neighbor's degree becomes 1, it's now on a branch that can be trimmed.
if degrees[neighbor_node] == 1:
trimming_queue.append(neighbor_node)
distances = [-1] * number_of_nodes
breadth_first_search_queue = []
for node_index in range(number_of_nodes):
if nodes_on_cycle[node_index]:
distances[node_index] = 0
breadth_first_search_queue.append(node_index)
current_distance_from_cycle = 0
# A multi-source BFS starting from all cycle nodes simultaneously finds the shortest path for all other nodes.
while breadth_first_search_queue:
queue_size_for_this_level = len(breadth_first_search_queue)
current_distance_from_cycle += 1
for _ in range(queue_size_for_this_level):
current_node = breadth_first_search_queue.pop(0)
for neighbor_node in adjacency_list[current_node]:
if distances[neighbor_node] == -1:
distances[neighbor_node] = current_distance_from_cycle
breadth_first_search_queue.append(neighbor_node)
return distances| Case | How to Handle |
|---|---|
| The node lies on the cycle | Its distance is zero and no walk away from the cycle is required. |
| The graph is only a cycle | Every node stays on the cycle, so every distance is zero. |
| A tail hangs off the cycle | Nodes on the cycle stay at zero, and nodes farther along the tail receive larger distances. |
| A leaf is several edges from the cycle | The outward walk reports the number of edges from that leaf back to the cycle. |
| The same cycle is discovered from many starting nodes | One sorted copy is kept, and later walks reuse that copy. |
| A node is not on the recorded cycle | The slow search walks toward the stored cycle nodes in label order and keeps the distance from the first successful walk. |