Redundant connection ii

Depth-First Search Breadth-First Search Union-Find Graph Theory

35.9% acceptance

Feb 20, 2026

2513

330

Redundant Connection II (directed graph). Return the edge to remove so the graph becomes a rooted tree.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_redundant_directed_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
    let n = edges.len();
    let mut parent = vec![0usize; n + 1];
    let mut cand1: Option<Vec<i32>> = None;
    let mut cand2: Option<Vec<i32>> = None;

    // Find a node with two parents
    for edge in &edges {
      let v = edge[1] as usize;
      if parent[v] == 0 {
        parent[v] = edge[0] as usize;
      } else {
        cand1 = Some(vec![parent[v] as i32, v as i32]);
        cand2 = Some(edge.clone());
      }
    }

    // Reset parent for union-find
    let mut uf: Vec<usize> = (0..=n).collect();
    fn find(uf: &mut Vec<usize>, x: usize) -> usize {
      if uf[x] != x { uf[x] = find(uf, uf[x]); }
      uf[x]
    }

    for edge in &edges {
      let (u, v) = (edge[0] as usize, edge[1] as usize);
      // Skip cand2 if it exists
      if let Some(ref c2) = cand2 {
        if edge == c2 { continue; }
      }
      let pu = find(&mut uf, u);
      let pv = find(&mut uf, v);
      if pu == pv {
        // Cycle found
        return cand1.unwrap_or_else(|| edge.clone());
      }
      uf[pu] = pv;
    }
    cand2.unwrap_or_default()
  }
}