[C++] | Union Find | Simple Straightforward Idea Explained
\n\nThis problem is generous in terms of constraints and we can leverage that to come up with an easily understandable solution!\n\nUnion Find\nA Union Find dat
\n\nThis problem is generous in terms of constraints and we can leverage that to come up with an easily understandable solution!\n\n**Union Find**\nA Union Find data structure, also known as the Disjoint Set data structure, stores a collection of disjoint (non overlapping) sets. It mainly has two operations:\n* Union(x, y): It unifies the two arguments into a single set\n* Find(x): It finds the root or the parent of the set which the argument belongs to.\n\nThis data structure is perfect for our current problem as we can group all the friends in disjoint sets and make use of the operations to efficiently do so. I also employ something known as path compression which makes the complexity of both *union* and *find* operations to be amortized O(1). You can learn more about Union Find on Hackerearth and GFG. In fact, I have prepared my template from these sites. \n\n**Idea**\nNow that it is clear we are going to use Union Find here, let us proceed to discussing about how exactly are we planning to do so. \nThe idea is simple and straightforward. We maintain a Union Find data structure which stores all the friends. When we encounter a new friend request, we *accept* it but not really! What I mean is we temporarily accept to check whether it causes any violation of the restrictions or not. \nHow do we do so? \nBy making a copy of our Union Find data structure and unifying the participants of the request in the copy. Then we traverse the list of restrictions and individually check if we are violating any. This is done by checking that the roots/parents of the members of the restriction are same or not. If they are, then they belong to the same friend group which is a violation. If we face no violations, then we can *accept* this friend request in our original data structure as well.\n\nThat\'s it!\n\nThe code might look big, but that is only because of the template. \n\n**C++**\n```\nclass UnionFind {\npublic:\n    vector<int> parent;\n\n    UnionFind(int n) {\n        parent.resize(n + 1, -1);\n    }\n\n    int find(int x) {\n        int root = x;\n        while (parent[root] >= 0) {\n            root = parent[root];\n        }\n\n        // Path Compression\n        while (parent[x] >= 0) {\n            int next = parent[x];\n            parent[x] = root;\n            x = next;\n        }\n\n        return root;\n    }\n\n    void unionz(int x, int y) {\n        int root1 = find(x);\n        int root2 = find(y);\n\n        if (root1 == root2)\n            return;\n\n        if (parent[root1] < parent[root2]) {\n            parent[root1] += parent[root2];\n            parent[root2] = root1;\n        } else {\n            parent[root2] += parent[root1];\n            parent[root1] = root2;\n        }\n    }\n};\n\nclass Solution {\npublic:\n    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {\n        int m = requests.size();\n        vector<bool> ans(m, 0);\n        \n        UnionFind UF(n);\n        \n        for(int i = 0; i < m; i++) {\n            UnionFind temp = UF;\n            temp.unionz(requests[i][0], requests[i][1]);\n            bool flag = true;\n            for(vector<int>& v : restrictions) {\n                if(temp.find(v[0]) == temp.find(v[1])) {\n                    flag = false;\n                    break;\n                }\n            }\n            \n            if(flag) {\n                ans[i] = true;\n                UF.unionz(requests[i][0], requests[i][1]);\n            }\n        }\n        \n        return ans;\n    }\n};\n```\n\n**Complexity Analysis**\n*Space Complexity (Auxiliary): O(n)*\n*Time Complexity: O(m * n)*
['Union Find']