Distance to a cycle in undirected graph

Depth-First Search Breadth-First Search Graph Theory Topological Sort

74.1% acceptance

Mar 31, 2026

154

You are given a positive integer n representing the number of nodes in a connected undirected graph containing exactly one cycle. The nodes are numbered from 0 to n - 1 (inclusive). You are also given a 2D integer array edges, where edges[i] = [node1i, node2i] denotes that there is a bidirectional edge connecting node1i and node2i in the graph. The distance between two nodes a and b is defined to be the minimum number of edges that are needed to go from a to b. Return an integer array answer of size n, where answer[i] is the minimum distance between the ith node and any node in the cycle.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn distance_to_cycle(n: i32, edges: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    let mut degree = vec![0u32; n];
    for e in &edges {
      let (u, v) = (e[0] as usize, e[1] as usize);
      adj[u].push(v);
      adj[v].push(u);
      degree[u] += 1;
      degree[v] += 1;
    }
    let mut queue = std::collections::VecDeque::new();
    let mut on_cycle = vec![true; n];
    for i in 0..n {
      if degree[i] == 1 {
        queue.push_back(i);
      }
    }
    while let Some(u) = queue.pop_front() {
      on_cycle[u] = false;
      for &v in &adj[u] {
        if on_cycle[v] {
          degree[v] -= 1;
          if degree[v] == 1 {
            queue.push_back(v);
          }
        }
      }
    }
    let mut answer = vec![-1i32; n];
    let mut queue = std::collections::VecDeque::new();
    for i in 0..n {
      if on_cycle[i] {
        answer[i] = 0;
        queue.push_back(i);
      }
    }
    while let Some(u) = queue.pop_front() {
      for &v in &adj[u] {
        if answer[v] == -1 {
          answer[v] = answer[u] + 1;
          queue.push_back(v);
        }
      }
    }
    answer
  }
}