1019. Friend Requests With Restrictions

A network has n people. There are r RESTRICTIONS, each naming two different people who must never end up in the same group.

Then q requests arrive, each naming two people. A request is ACCEPTED if granting it would break no restriction, and granting it merges their two groups. A request is REJECTED otherwise, and then nothing changes and the later requests carry on against the groups as they stand.

Print ACCEPTED or REJECTED for each request, in order.

4 people, restriction (1 4) requests (1 2)(3 4)(2 3) -> ACCEPTED ACCEPTED REJECTED

The third request would put 1, 2, 3 and 4 into one group, which would place 1 beside 4. Notice that the restriction names neither person in that request: it is broken by what the earlier requests already built.

3 people, restriction (1 3), requests (1 2)(1 3) -> ACCEPTED REJECTED 4 people, restriction (1 4), requests (1 2)(3 4)(2 3)(1 2) -> ACCEPTED ACCEPTED REJECTED ACCEPTED

The last request of the third example is one that has already been granted. Its two people are already in one group, so granting it changes nothing and cannot break anything, and it is accepted even though the request before it was refused.

## What most people try first

Grant the request, then check every restriction by a traversal, and undo if something broke. The undo is the problem: the structure has no way to take a merge back, so this needs the whole set of granted requests kept and the structure rebuilt from scratch, which is O(q(q + n)) at best.

## Test before merging, never after

for each request (u, v): ru = find(u); rv = find(v) if ru == rv: print ACCEPTED and continue nothing would change ok = true for each restriction (a, b): if (find(a) == ru and find(b) == rv) or (find(a) == rv and find(b) == ru): ok = false if ok: merge ru and rv, print ACCEPTED else: print REJECTED

The structure is only ever changed after the answer is known, so nothing ever has to be undone.

## Why checking the roots of the restricted pair is enough

Granting the request makes one group out of the two whose roots are ru and rv, and it changes no other group. A restriction (a, b) is broken afterwards exactly when a and b end up together, which happens exactly when one of them is currently in ru's group and the other in rv's. If both are already in the same group the restriction was broken before this request, which cannot happen; if both are outside, the merge does not touch them.

## The request whose two people are already together

It must be accepted without scanning the restrictions at all. Scanning anyway is not just slower: with ru equal to rv the test find(a) == ru and find(b) == rv fires for any restriction with both ends in that group, and no such restriction can exist, so it happens to be harmless here. Handling it explicitly makes the reason clear and saves the scan.

## Cost, and why the limits are small

Each request scans every restriction, so the sweep is O(q r alpha(n)), about 10^6 at these limits. That is why n, r and q are in the thousands. Keeping, for each root, the list of roots it is forbidden to join would bring it down, and merging those lists small to large is the same technique as problem 1014.

## Cross-reference

Problem 988 also mixes statements that join with statements that forbid, and it can sort them: every equality first, then every inequality. Here the requests arrive in an order that matters, because a rejected request must not be granted later by accident, so the restrictions have to be checked repeatedly against a structure that keeps changing.

## Cost

Time O(q r alpha(n)). Space O(n + r).

Constraints - `1 ≤ n ≤ 1000` - `0 ≤ r ≤ 1000` - `1 ≤ q ≤ 1000` - `1 ≤ a, b, u, v ≤ n` - `a` is never equal to `b`. - `u` may equal `v`.