Graph connectivity with threshold

Array Math Union-Find Number Theory

49.2% acceptance

Feb 25, 2026

611

We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true: x % z == 0, y % z == 0, and z > threshold. Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly. Return an array answer, where answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn are_connected(n: i32, threshold: i32, queries: Vec<Vec<i32>>) -> Vec<bool> {
    let n = n as usize;
    let mut parent: Vec<usize> = (0..=n).collect();
    let mut rank_uf = vec![0usize; n + 1];

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

    fn union(parent: &mut Vec<usize>, rank_uf: &mut Vec<usize>, x: usize, y: usize) {
      let px = find(parent, x);
      let py = find(parent, y);
      if px == py { return; }
      if rank_uf[px] < rank_uf[py] { parent[px] = py; }
      else if rank_uf[px] > rank_uf[py] { parent[py] = px; }
      else { parent[py] = px; rank_uf[px] += 1; }
    }

    // For each z > threshold, union all multiples of z
    for z in (threshold as usize + 1)..=n {
      let mut multiple = z * 2;
      while multiple <= n {
        union(&mut parent, &mut rank_uf, z, multiple);
        multiple += z;
      }
    }

    queries.iter().map(|q| {
      find(&mut parent, q[0] as usize) == find(&mut parent, q[1] as usize)
    }).collect()
  }
}