Redundant connection

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

67.3% acceptance

Feb 20, 2026

7133

450

Given an undirected graph that was once a tree with one extra edge added, return the redundant edge.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_redundant_connection(edges: Vec<Vec<i32>>) -> Vec<i32> {
    let n = edges.len();
    let mut parent: Vec<usize> = (0..=n).collect();
    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x {
        parent[x] = find(parent, parent[x]);
      }
      parent[x]
    }
    for edge in &edges {
      let (u, v) = (edge[0] as usize, edge[1] as usize);
      let pu = find(&mut parent, u);
      let pv = find(&mut parent, v);
      if pu == pv {
        return edge.clone();
      }
      parent[pu] = pv;
    }
    vec![]
  }
}