Number of provinces

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

70.0% acceptance

Feb 19, 2026

11053

421

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of directly or indirectly connected cities and no other cities outside of the group. You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise. Return the total number of provinces.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_circle_num(is_connected: Vec<Vec<i32>>) -> i32 {
    let n = is_connected.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]
    }
    let mut count = n as i32;
    for i in 0..n {
      for j in (i+1)..n {
        if is_connected[i][j] == 1 {
          let pi = find(&mut parent, i);
          let pj = find(&mut parent, j);
          if pi != pj { parent[pi] = pj; count -= 1; }
        }
      }
    }
    count
  }
}