C++ Make Friends
Hint/Thought Process\n- If x is a friend of y, and y is a friend of z, then x will be a friend of z. So, we can say, friends will form a connected component.\n\
**Hint/Thought Process**\n- If x is a friend of y, and y is a friend of z, then x will be a friend of z. So, we can say, friends will form a connected component.\n\t- => Hint for using disjoint set union.\n\n**Algorithm**\n- We process requests sequentially.\n\t- Let\'s say we are processing request[ i ] = [u,v]\n\t\n\t- Then, from previous requests, we know u & v will be part of some components.\n\t- Let say u\'s component contains: [u1,u2,u3,..., ux] and v\'s component contains: [v1,v2,v3,...,vy]\n\t\t- Now, after processing the current request, every pair (u_i, v_j) will be friends, for all i<=x and j<=y\n\t\t- Thus, if any of such pairs is restricted, i.e. (u_i, v_j) can\'t be friends \n\t\t\t- => We can\'t process the current request i.\n\t- Hence, we iterate over the Restrictions array for every request and check if any of the restriction is violated.\n\t\t- If no restriction is violated, we can process the current request.\n\t\t- Otherwise, we can\'t process the current request.\n\n\n**Time Complexity**\n- Let N = requests.size(), M = restrictions.size(), n = # people\n- O(N*M)\n\n**Code**\n```\nint find(vector<int> &ds, int i) {\n    return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]);\n}\n\nbool Union(vector<int> &ds, int i, int j){\n\t i = find(ds, i), j = find(ds, j);\n\t if(i==j) return false;\n\t if(abs(ds[i]) < abs(ds[j])) swap(i,j); \n\t ds[i]+=ds[j]; \n\t ds[j]=i;\n\t return true;\n}\n\nclass Solution {\npublic:\n    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {\n        vector<bool> res;\n        vector<int> ds(n, -1);\n        for(auto &r : requests){\n            int u = find(ds,r[0]), v = find(ds,r[1]), can = 1;\n\t\t\t\n            for(auto &rt : restrictions){\n                int u1 = find(ds,rt[0]), v1 = find(ds, rt[1]);\n                if((u1==u && v1 == v) || (u1==v && v1==u)){ \n                    //restricted pair will be connected!! => Do not process the request\n                    can = 0;\n                    break;\n                }\n            }\n            if(can) Union(ds,u,v);\n            res.push_back(can);   \n        }\n        return res;\n    }\n};\n```
[]