Count the number of complete components

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

77.8% acceptance

Feb 25, 2026

1268

You are given an integer n. There is an undirected graph with n vertices, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting vertices ai and bi. Return the number of complete connected components of the graph. A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph. A connected component is said to be complete if there exists an edge between every pair of its vertices.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_complete_components(n: i32, edges: Vec<Vec<i32>>) -> i32 {
    let n = n as usize;
    let mut parent = (0..n).collect::<Vec<_>>();
    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 e in &edges {
      let (a, b) = (e[0] as usize, e[1] as usize);
      let ra = find(&mut parent, a);
      let rb = find(&mut parent, b);
      if ra != rb {
        if rank[ra] < rank[rb] { parent[ra] = rb; }
        else if rank[ra] > rank[rb] { parent[rb] = ra; }
        else { parent[rb] = ra; rank[ra] += 1; }
      }
    }
    
    // Count nodes and edges per component
    use std::collections::HashMap;
    let mut comp_nodes: HashMap<usize, usize> = HashMap::new();
    let mut comp_edges: HashMap<usize, usize> = HashMap::new();
    for i in 0..n {
      *comp_nodes.entry(find(&mut parent, i)).or_insert(0) += 1;
    }
    for e in &edges {
      let root = find(&mut parent, e[0] as usize);
      *comp_edges.entry(root).or_insert(0) += 1;
    }
    
    let mut count = 0i32;
    for (root, k) in comp_nodes.iter() {
      let k = *k;
      let e = comp_edges.get(root).copied().unwrap_or(0);
      if e == k * (k - 1) / 2 { count += 1; }
    }
    count
  }
}