Count unreachable pairs of nodes in an undirected graph

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

49.8% acceptance

Feb 25, 2026

2258

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [ai, bi]. Return the number of pairs of different nodes that are unreachable from each other.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>) -> i64 {
    let n = n as usize;
    let mut parent: Vec<usize> = (0..n).collect();
    let mut size = vec![1usize; n];

    for e in &edges {
      let a = e[0] as usize;
      let b = e[1] as usize;
      let ra = Self::find(&mut parent, a);
      let rb = Self::find(&mut parent, b);
      if ra != rb {
        if size[ra] < size[rb] {
          parent[ra] = rb;
          size[rb] += size[ra];
        } else {
          parent[rb] = ra;
          size[ra] += size[rb];
        }
      }
    }

    let mut remaining = n as i64;
    let mut ans: i64 = 0;
    let mut visited = vec![false; n];
    for i in 0..n {
      let root = Self::find(&mut parent, i);
      if !visited[root] {
        visited[root] = true;
        let sz = size[root] as i64;
        remaining -= sz;
        ans += sz * remaining;
      }
    }
    ans
  }

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