##### Welcome to Subscribe On Youtube

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] = [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 (i.e., requests[j] occurs before requests[j + 1]), 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.

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 <= xi, yi <= n - 1
• xi != yi
• 1 <= requests.length <= 1000
• requests[j].length == 2
• 0 <= uj, vj <= n - 1
• uj != vj

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;
}
};

• class Solution:
def friendRequests(
self, n: int, restrictions: List[List[int]], requests: List[List[int]]
) -> List[bool]:
p = list(range(n))

def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]

ans = []
i = 0
for u, v in requests:
if find(u) == find(v):
ans.append(True)
else:
valid = True
for x, y in restrictions:
if (find(u) == find(x) and find(v) == find(y)) or (
find(u) == find(y) and find(v) == find(x)
):
valid = False
break
ans.append(valid)
if valid:
p[find(u)] = find(v)
return ans

############

# 2076. Process Restricted Friend Requests
# https://leetcode.com/problems/process-restricted-friend-requests

class DSU:
def __init__(self, n):
self.graph = list(range(n))

def find(self, x):
if self.graph[x] != x:
self.graph[x] = self.find(self.graph[x])

return self.graph[x]

def union(self, x, y):
px = self.find(x)
py = self.find(y)

self.graph[px] = py

class Solution:
def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
dsu = DSU(n)
res = []

for x, y in requests:
px, py = dsu.find(x), dsu.find(y)
valid = True

for a, b in restrictions:
pa, pb = dsu.find(a), dsu.find(b)

if set([pa, pb]) == set([px, py]):
valid = False
break

res.append(valid)
if valid:
dsu.union(x, y)

return res


• class Solution {
private int[] p;

public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
p = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
}
boolean[] ans = new boolean[requests.length];
int i = 0;
for (int[] req : requests) {
int u = req[0], v = req[1];
if (find(u) == find(v)) {
ans[i++] = true;
} else {
boolean valid = true;
for (int[] res : restrictions) {
int x = res[0], y = res[1];
if ((find(u) == find(x) && find(v) == find(y))
|| (find(u) == find(y) && find(v) == find(x))) {
valid = false;
break;
}
}
if (valid) {
p[find(u)] = find(v);
ans[i++] = true;
} else {
ans[i++] = false;
}
}
}
return ans;
}

private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}

• var p []int

func friendRequests(n int, restrictions [][]int, requests [][]int) []bool {
p = make([]int, n)
for i := 0; i < n; i++ {
p[i] = i
}
var ans []bool
for _, req := range requests {
u, v := req[0], req[1]
if find(u) == find(v) {
ans = append(ans, true)
} else {
valid := true
for _, res := range restrictions {
x, y := res[0], res[1]
if (find(u) == find(x) && find(v) == find(y)) || (find(u) == find(y) && find(v) == find(x)) {
valid = false
break
}
}
ans = append(ans, valid)
if valid {
p[find(u)] = find(v)
}
}
}
return ans
}

func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}


## Discuss

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