2076. Process Restricted Friend Requests

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.

#define all(a) begin(a),end(a)
class Solution {
    unordered_set<int> us[1000];
    unordered_set<int> lazy;
    unordered_set<int> rst[1000];
    int uf[1000];
    int N;
    int find(int u) {
        return uf[u] == u ? u : uf[u] = find(uf[u]);
    }
    
    void merge(int u, int v) {
        int pu = find(u), pv = find(v);
        uf[pu] = uf[pv] = min(pu, pv);
        lazy.insert(min(pu,pv));
    }
    
    void updateLazy(int u) {
        if(lazy.count(u)) {
            for(int i = 0; i < N; i++)
                if(find(i) == u and !us[u].count(i)) {
                    us[u].insert(all(us[i]));
                    rst[u].insert(all(rst[i]));
                    us[i].clear();
                    rst[i].clear();
                }
            lazy.erase(u);
        }
    }
    
    unordered_set<int> group(int u) {
        updateLazy(u);
        return us[u];
    }
    
    bool disjoint(unordered_set<int>& A, unordered_set<int>& B) {
        if(A.size() > B.size())
            return disjoint(B,A);
        for(auto& a : A)
            if(B.count(a))
                return true;
        return false;
    }
    
    bool deny(int u, int v) {
        int pu = find(u), pv = find(v);
        if(pu == pv) return false;
        auto gu = group(pu), gv = group(pv);

        return disjoint(rst[pu], gv) or disjoint(rst[pv], gu);
    }
    
public:
    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
        N = n;
        for(auto& r : restrictions) {
            rst[r[0]].insert(r[1]);
            rst[r[1]].insert(r[0]);
        }
        for(int i = 0; i < n; i++) us[i].insert(uf[i] = i);
        
        vector<bool> res;
        for(auto& r : requests) {
            int u = r[0], v = r[1];
            if(!deny(u, v)) {
                res.push_back(true);
                merge(u,v);
            } else res.push_back(false);
        }
        return res;
    }
};