Process restricted friend requests

Union-Find Graph Theory

59.5% acceptance

Feb 25, 2026

664

You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n - 1. You are also given a 0-indexed 2D integer array restrictions, where restrictions[i] = [xi, yi] means that person xi and person yi cannot become friends, either directly or indirectly through other people. Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests, where requests[j] = [uj, vj] is a friend request between person uj and person vj. A friend request is successful if uj and vj can be friends. Each friend request is processed in the given order, and upon a successful request, uj and vj become direct friends for all future friend requests. Return a boolean array result, where each result[j] is true if the jth friend request is successful or false if it is not. Note: If uj and vj are already direct friends, the request is still successful.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

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

impl Solution {
  pub fn friend_requests(n: i32, restrictions: Vec<Vec<i32>>, requests: Vec<Vec<i32>>) -> Vec<bool> {
    let n = n as usize;
    let mut parent: Vec<usize> = (0..n).collect();
    let mut rank: Vec<usize> = vec![0; n];

    let mut result = Vec::new();

    for req in &requests {
      let u = req[0] as usize;
      let v = req[1] as usize;

      // Save state to allow rollback
      let saved_parent = parent.clone();
      let saved_rank = rank.clone();

      // Try to union u and v
      let ru = uf_find(&mut parent, u);
      let rv = uf_find(&mut parent, v);

      if ru != rv {
        if rank[ru] < rank[rv] {
          parent[ru] = rv;
        } else if rank[ru] > rank[rv] {
          parent[rv] = ru;
        } else {
          parent[rv] = ru;
          rank[ru] += 1;
        }
      }

      // Check if any restriction is violated
      let mut violated = false;
      for r in &restrictions {
        let rx = r[0] as usize;
        let ry = r[1] as usize;
        if uf_find(&mut parent, rx) == uf_find(&mut parent, ry) {
          violated = true;
          break;
        }
      }

      if violated {
        // Rollback
        parent = saved_parent;
        rank = saved_rank;
        result.push(false);
      } else {
        result.push(true);
      }
    }

    result
  }
}