Process friend requests one by one while rejecting any request that would violate a restriction between two users.
You are given users labeled from $0n - 1$, a list of restrictions, and a sequence of friend requests.
Each restriction is a pair meaning users and must never end up in the same connected friend group, directly or indirectly.
Process the friend requests in order. For each request :
- If connecting and would place any restricted pair in the same connected group, reject the request.
- Otherwise, accept it and merge their friend groups.
Return an array of booleans indicating whether each request is accepted.
The key challenge is to maintain connected components efficiently while checking whether a proposed merge conflicts with any restriction.
Input Format
- An integer .
- A list of restrictions, where each restriction is a pair of user IDs.
- A list of friend requests, where each request is a pair of user IDs.
Users are labeled from $0n - 1$.
Output Format
Return a boolean array of length equal to the number of requests, where the -th value is true if the -th request is accepted and false otherwise.
Constraints
- Each user ID is in the range
- Restriction and request pairs contain valid user IDs
- The number of restrictions and requests can be large enough that an check per request may be too slow
Example 1
Input
n = 3 restrictions = [[0,1]] requests = [[0,2],[2,1]]
Output
[true,false]
Explanation
Request [0,2] is accepted because users 0 and 2 can be connected without violating the restriction. After that, users 0 and 2 are in the same group, so accepting [2,1] would place 0 and 1 in the same group, which violates the restriction.
Example 2
Input
n = 5 restrictions = [[0,1],[2,3]] requests = [[0,2],[2,4],[1,4],[1,3]]
Output
[true,true,false,false]
Explanation
- [0,2] is accepted.
- [2,4] is accepted, so group {0,2,4} forms.
- [1,4] would connect 1 with 0 through 4, violating restriction [0,1].
- [1,3] would connect 1 with 2 through 3 and the existing group, violating restriction [2,3].
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.