Process Restricted Friend Requests

hard graph union find

Problem

There are n people numbered 0 to n - 1. You are given a list of restrictions, where each pair [x, y] means person x and person y can never become friends — not even indirectly through other friends. You are also given a list of requests, where each pair [u, v] asks to make u and v friends. Process the requests in order: a request succeeds only if accepting it would not place any restricted pair into the same friend group. Return a boolean array telling whether each request was accepted.

Inputn = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]

Output[true, false, true, false]

Request [0,4] is fine. [1,2] is restricted directly, so reject. [3,1] is allowed. [3,4]: by now 0 and 4 are friends and 1,3 are friends; joining 3 and 4 would link group {3,1} with {4,0}, putting restricted pair (0,1) together — reject.

restrictions (e.g. 0-1, 1-2, 2-3)

requests (e.g. 0-4, 1-2, 3-1, 3-4)

def friend_requests(n, restrictions, requests):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    answer = []
    for u, v in requests:
        ru, rv = find(u), find(v)
        ok = True
        if ru != rv:
            for x, y in restrictions:
                rx, ry = find(x), find(y)
                if {rx, ry} == {ru, rv}:
                    ok = False
                    break
        if ok:
            parent[ru] = rv
        answer.append(ok)
    return answer

function friendRequests(n, restrictions, requests) {
  const parent = Array.from({ length: n }, (_, i) => i);
  function find(x) { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
  const answer = [];
  for (const [u, v] of requests) {
    const ru = find(u), rv = find(v);
    let ok = true;
    if (ru !== rv) {
      for (const [x, y] of restrictions) {
        const rx = find(x), ry = find(y);
        if ((rx === ru && ry === rv) || (rx === rv && ry === ru)) { ok = false; break; }
      }
    }
    if (ok) parent[ru] = rv;
    answer.push(ok);
  }
  return answer;
}

class Solution {
    int[] parent;
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        boolean[] answer = new boolean[requests.length];
        for (int i = 0; i < requests.length; i++) {
            int ru = find(requests[i][0]), rv = find(requests[i][1]);
            boolean ok = true;
            if (ru != rv) {
                for (int[] r : restrictions) {
                    int rx = find(r[0]), ry = find(r[1]);
                    if ((rx == ru && ry == rv) || (rx == rv && ry == ru)) { ok = false; break; }
                }
            }
            if (ok) parent[ru] = rv;
            answer[i] = ok;
        }
        return answer;
    }
}

vector<int> parent;
int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
    parent.resize(n);
    for (int i = 0; i < n; i++) parent[i] = i;
    vector<bool> answer;
    for (auto& req : requests) {
        int ru = find(req[0]), rv = find(req[1]);
        bool ok = true;
        if (ru != rv) {
            for (auto& r : restrictions) {
                int rx = find(r[0]), ry = find(r[1]);
                if ((rx == ru && ry == rv) || (rx == rv && ry == ru)) { ok = false; break; }
            }
        }
        if (ok) parent[ru] = rv;
        answer.push_back(ok);
    }
    return answer;
}

Explanation

Friendship is "sticky": if a befriends b and b befriends c, then a and c are in the same friend group too. Grouping that spreads transitively is exactly what Union-Find models, so we keep every person in a group and use find to get the root (the representative) of each group.

For each request [u, v], we look at the roots ru and rv of their two groups. If they are already in the same group, the request is automatically accepted (no merge needed). Otherwise we have to check whether merging the two groups would put any forbidden pair together.

The key insight: merging group ru with group rv only endangers a restriction [x, y] when one of x, y sits in group ru and the other sits in group rv. In root terms, that is when {find(x), find(y)} equals {ru, rv}. If any restriction matches that, the merge would link a banned pair, so we reject and leave the groups untouched. If none matches, we accept and union the two groups.

Tracing the example with restrictions = [[0,1],[1,2],[2,3]]: request [0,4] merges {0} and {4} with no restriction spanning them, so accept → groups {0,4}. [1,2] is restricted directly (1 and 2 land in the two groups being joined), so reject. [3,1] has no restriction spanning {3} and {1}, so accept → {1,3}. Finally [3,4] would merge {1,3} with {0,4}; restriction [0,1] has 0 in one group and 1 in the other, so reject. The answer is [true, false, true, false].

Because we only union after confirming no restriction is violated, the friend groups always stay consistent with every accepted request seen so far.

Time: O(q · r · α(n)) Space: O(n)