Number of connected components in an undirected graph

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

64.9% acceptance

Mar 31, 2026

2808

110

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph. Return the number of connected components in the graph.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_components(n: i32, edges: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank = vec![0u8; n];
    let mut components = n as i32;

    for e in &edges {
      let (a, b) = (e[0] as usize, e[1] as usize);
      let pa = Self::find_cc(&mut parent, a);
      let pb = Self::find_cc(&mut parent, b);
      if pa != pb {
        if rank[pa] < rank[pb] {
          parent[pa] = pb;
        } else if rank[pa] > rank[pb] {
          parent[pb] = pa;
        } else {
          parent[pb] = pa;
          rank[pa] += 1;
        }
        components -= 1;
      }
    }
    components
  }

  fn find_cc(parent: &mut Vec<usize>, mut x: usize) -> usize {
    while parent[x] != x {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    x
  }
}