#2076
Process Restricted Friend Requests
expert · 1190 · lc hard +32 · verified · 59.6% accepted · 666 likes · top 57%
Description
There are n people labeled 0 to n - 1. Some pairs are restricted: restrictions[i] = [xi, yi] means xi and yi must never end up in the same friend group, even transitively. Process each requests[j] = [uj, vj] in order: the request succeeds if connecting uj and vj's groups would not violate any restriction (already-connected pairs always succeed). Approved requests permanently merge the two groups. Return a boolean array indicating success or failure for each request.
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).
Code
1
2
3