DSU with Rollback
Intuition\n Describe your first thoughts on how to solve this problem. \nDSU with rollback\nbrute force according to me\n\n# Approach\n Describe your approach t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nDSU with rollback\nbrute force according to me\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\ndo union\ncheck if it violates conditions or not\nif it is then rollback\notherwise move on\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n*n*logn)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n\n# Code\n```\nclass DisjointSet {\npublic :\n    vector<int> size, parent;\n    stack<pair<int, int>> parentHistory, sizeHistory; // {element, currentValue of element}\n    DisjointSet(int n) {\n        parent.resize(n + 1);\n        size.resize(n + 1, 1);\n        \n        for(int i = 0 ; i <= n ; i++) {\n            parent[i] = i;\n        }\n    }\n    // T.C = O(logN) as no path compression is there\n    int findUltimateParent(int node) {\n        if(node == parent[node]) {\n            return node;\n        }\n        return findUltimateParent(parent[node]);\n    }\n    // T.C = O(logN)\n    void unionBySize(int node1, int node2) {\n        int ultimateParent1 = findUltimateParent(node1);\n        int ultimateParent2 = findUltimateParent(node2);\n        \n        if(ultimateParent1 == ultimateParent2) return;\n        \n        if(size[ultimateParent1] > size[ultimateParent2]) {\n            parentHistory.push({ultimateParent2, ultimateParent2});\n            sizeHistory.push({ultimateParent1, size[ultimateParent1]});\n            \n            parent[ultimateParent2] = ultimateParent1;\n            size[ultimateParent1] += size[ultimateParent2];\n        }\n        else{\n            parentHistory.push({ultimateParent1, ultimateParent1});\n            sizeHistory.push({ultimateParent2, size[ultimateParent2]});\n            \n            parent[ultimateParent1] = ultimateParent2;\n            size[ultimateParent2] += size[ultimateParent1];\n        }\n    }\n    // T.C = O(1)\n    void rollback() {\n        // restore the previous state of size and parent\n        // if(sizeHistory.size() == 0 || parentHistory.size() == 0) return ;\n\n        int node = sizeHistory.top().first;\n        int previousSize = sizeHistory.top().second;\n        sizeHistory.pop();\n        \n        size[node] = previousSize;\n        \n        int targetNode = parentHistory.top().first;\n        int previousParent = parentHistory.top().second;\n        parentHistory.pop();\n        \n        parent[targetNode] = previousParent;\n    }\n};\nclass Solution {\npublic:\n    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {\n        DisjointSet ds(n);\n        vector<bool> ans(requests.size(), false);\n\n        // Traversing requests vector\n        for(int i = 0 ; i < requests.size() ; i++) {\n            int node1 = requests[i][0];\n            int node2 = requests[i][1];\n\n            ds.unionBySize(node1, node2);\n            ans[i] = true;\n\n            // Traversing restrictions vector\n            for(auto it : restrictions) {\n                if(ds.findUltimateParent(it[0]) == ds.findUltimateParent(it[1])) {\n                    ds.rollback();\n                    ans[i] = false;\n                    break;\n                }\n            }\n        }\n\n        return ans;\n    }\n};\n```
['Stack', 'Union Find', 'Graph', 'C++']