Graph valid tree

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

49.9% acceptance

Mar 31, 2026

3462

116

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph. Return true if the edges of the given graph make up a valid tree, and false otherwise.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn valid_tree(n: i32, edges: Vec<Vec<i32>>) -> bool {
    let n = n as usize;
    if edges.len() != n - 1 {
      return false;
    }
    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0usize; n];
    
    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 (a, b) = (edge[0] as usize, edge[1] as usize);
      let (ra, rb) = (find(&mut parent, a), find(&mut parent, b));
      if ra == rb {
        return false;
      }
      if rank[ra] < rank[rb] {
        parent[ra] = rb;
      } else if rank[ra] > rank[rb] {
        parent[rb] = ra;
      } else {
        parent[rb] = ra;
        rank[ra] += 1;
      }
    }
    true
  }
}