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