Formatted question description: https://leetcode.ca/all/2076.html

# 2076. Process Restricted Friend Requests (Hard)

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] = [x`

means that person _{i}, y_{i}]`x`

and person _{i}`y`

_{i}**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] = [u`

is a friend request between person _{j}, v_{j}]`u`

and person _{j}`v`

._{j}

A friend request is **successful **if `u`

and _{j}`v`

can be _{j}**friends**. Each friend request is processed in the given order (i.e., `requests[j]`

occurs before `requests[j + 1]`

), and upon a successful request, `u`

and _{j}`v`

_{j}**become direct friends** for all future friend requests.

Return *a boolean array *

`result`

,*where each*

`result[j]`

*is*

`true`

*if the*

`j`^{th}

*friend request is*

**successful**or`false`

*if it is not*.

**Note:** If `u`

and _{j}`v`

are already direct friends, the request is still _{j}**successful**.

**Example 1:**

Input:n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]Output:[true,false]Explanation:Request 0: Person 0 and person 2 can be friends, so they become direct friends. Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).

**Example 2:**

Input:n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]Output:[true,false]Explanation:Request 0: Person 1 and person 2 can be friends, so they become direct friends. Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).

**Example 3:**

Input:n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]Output:[true,false,true,false]Explanation:Request 0: Person 0 and person 4 can be friends, so they become direct friends. Request 1: Person 1 and person 2 cannot be friends since they are directly restricted. Request 2: Person 3 and person 1 can be friends, so they become direct friends. Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).

**Constraints:**

`2 <= n <= 1000`

`0 <= restrictions.length <= 1000`

`restrictions[i].length == 2`

`0 <= x`

_{i}, y_{i}<= n - 1`x`

_{i}!= y_{i}`1 <= requests.length <= 1000`

`requests[j].length == 2`

`0 <= u`

_{j}, v_{j}<= n - 1`u`

_{j}!= v_{j}

**Similar Questions**:

## Solution 1. Union Find

Given the constraints, a solution with `O(R * B)`

is acceptable – for each request, check if it obeys all the bans.

For the check, we can do it in `O(1)`

time using UnionFind. For each prior valid requests, we connect the two friends. For a new request, we just need to check if the leaders of the two parties are in any of those bans.

```
// OJ: https://leetcode.com/problems/process-restricted-friend-requests/
// Time: O(R * B) where `R`/`B` is the length of `requests`/`bans`
// Space: O(N)
class UnionFind {
vector<int> id;
public:
UnionFind(int n) : id(n) {
iota(begin(id), end(id), 0);
}
void connect(int a, int b) {
id[find(a)] = find(b);
}
int find(int a) {
return id[a] == a ? a : (id[a] = find(id[a]));
}
int connected(int a, int b) {
return find(a) == find(b);
}
};
class Solution {
public:
vector<bool> friendRequests(int n, vector<vector<int>>& bans, vector<vector<int>>& requests) {
vector<bool> ans;
UnionFind uf(n);
for (auto &r : requests) {
int p = uf.find(r[0]), q = uf.find(r[1]); // the leaders of the two parties
bool valid = true;
if (!uf.connected(p, q)) { // Only need to check the bans if the two parties are not already connected
for (auto &b : bans) {
int x = uf.find(b[0]), y = uf.find(b[1]); // the leaders of the two banned parties
if ((x == p && y == q) || (x == q && y == p)) {
valid = false;
break;
}
}
}
ans.push_back(valid);
if (valid) uf.connect(p, q); // connect two parties if request is valid
}
return ans;
}
};
```

## Discuss

https://leetcode.com/problems/process-restricted-friend-requests/discuss/1576935/C%2B%2B-Union-Find