# 2076. Process Restricted Friend Requests

## Description

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

## Solutions

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

• class Solution {
public:
vector<int> p;

vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
p.resize(n);
for (int i = 0; i < n; ++i) p[i] = i;
vector<bool> ans;
for (auto& req : requests) {
int u = req[0], v = req[1];
if (find(u) == find(v))
ans.push_back(true);
else {
bool valid = true;
for (auto& 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;
}
}
ans.push_back(valid);
if (valid) p[find(u)] = find(v);
}
}
return ans;
}

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

• 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


• 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]
}

• function friendRequests(n: number, restrictions: number[][], requests: number[][]): boolean[] {
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
const ans: boolean[] = [];
for (const [u, v] of requests) {
const pu = find(u);
const pv = find(v);
if (pu === pv) {
ans.push(true);
} else {
let ok = true;
for (const [x, y] of restrictions) {
const px = find(x);
const py = find(y);
if ((px === pu && py === pv) || (px === pv && py === pu)) {
ok = false;
break;
}
}
ans.push(ok);
if (ok) {
p[pu] = pv;
}
}
}
return ans;
}