Welcome to Subscribe On Youtube
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 <= 10000 <= restrictions.length <= 1000restrictions[i].length == 20 <= xi, yi <= n - 1xi != yi1 <= requests.length <= 1000requests[j].length == 20 <= uj, vj <= n - 1uj != 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; }