Union find with rollback
Algorithm Union Find\n\n# Approach\nFor each request, process it, and check restrictions. If restricted rollback to previous state. \n\n# Complexity\n- Time com
# Algorithm `Union Find`\n\n# Approach\nFor each request, process it, and check restrictions. If restricted rollback to previous state. \n\n# Complexity\n- Time complexity: $$O(restrictions.length*requests.length*log(n))$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass UnionFind {\nprivate:\n    int n,set_size, *parent, *rank;\n    stack<pair<int,pair<int,int>>> st;\npublic:\n    UnionFind(){}\n    UnionFind(int a) { //a: set size, {1,2...n}\n        n=set_size=a;\n        parent=new int[n+1];\n        rank=new int[n+1];\n        for (int i=1;i<=n;i++) parent[i]=i, rank[i]=1;\n    }\n\n    int find(int x) { //O(logn)\n        if (x!=parent[x]) return find(parent[x]);\n        return x;\n    }\n\n    bool merge(int x, int y) { //O(logn)\n        int xroot=find(x), yroot=find(y);\n        if (xroot!=yroot) { //rank-compression\n            if (rank[xroot]>=rank[yroot]) {\n                st.push({yroot,{parent[yroot],rank[xroot]}});\n                parent[yroot]=xroot;\n                rank[xroot]+=rank[yroot];\n            } else {\n                st.push({xroot,{parent[xroot],rank[yroot]}});\n                parent[xroot]=yroot;\n                rank[yroot]+=rank[xroot];\n            }\n            set_size--;     \n            return 1;\n        }\n        return 0;\n    }\n\n    bool rollback() { //O(1)\n        if (st.empty()) return 0;\n        auto &his=st.top();\n        rank[parent[his.first]]=his.second.second;\n        parent[his.first]=his.second.first;\n        st.pop();\n        set_size++;\n        return 1;\n    }\n\n    void reset() {\n        set_size=n;\n        for (int i=1;i<=n;i++) parent[i]=i, rank[i]=1;  \n    }    \n};\n\nclass Solution {\npublic:\nvector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {\n    UnionFind frds(n);\n    vector<bool> ans;\n    for (const auto &req:requests) {\n        bool _=1;\n        frds.merge(req[0]+1,req[1]+1);\n        for (const auto &res:restrictions)\n            if (frds.find(res[0]+1)==frds.find(res[1]+1)) {_=0;break;}\n        if (!_) frds.rollback();\n        ans.push_back(_);\n    }\n    return ans;\n}\n};\n```
['C++']