96% | Best reusable DisjointSet Template | Bonus tip inside!!
Intuition\n Describe your first thoughts on how to solve this problem. \nThis problem is pretty straightforwad. Basically they are saying that two people can be
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem is pretty straightforwad. Basically they are saying that two people can be friends if they have no restrictions or any of their mutual friends have no restriction.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe simplest way to solve this would be to use the union-find technique to link all the persons with mutual friends to one common ancestor. Now for every request we simply check that whether those ancestors have any restrictions or not. If they do they can\'t be friends or else they can be.\n\nPLEASE UPVOTE IF YOU FIND THIS BLOG ANY DIFF THAN OTHERS!!\n# Complexity\n- Time complexity: $$O(n*m)$$ -> n = restrictions.length, m = requests.length\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n            \n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int find(int node, vector<int> &par){\n        if(par[node] == node){\n            return node;\n        }\n        return par[node] = find(par[node], par);\n    }\n    int join(int u, int v, vector<int> &par, vector<int> &si){\n        int pu = find(u, par);\n        int pv = find(v, par);\n\n        if(pu!=pv){\n            if(si[pu]>=si[pv]){\n                par[pv] = pu;\n                si[pu] += si[pv];\n            }\n            else{\n                par[pu] = pv;\n                si[pv] += si[pu];\n            }\n            return 0;\n        }\n        return 1;\n    }\n    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {\n        vector<bool> ans;\n        vector<int> par(n,-1), si(n,1);\n        for(int i=0; i<n; ++i){\n            par[i] = i;\n        }\n\n        for(auto &edge:requests){ // putting & changes 1800ms code \n            int u = edge[0], v = edge[1]; // to 200 ms!!!\n            int pu = find(u, par), pv = find(v, par);\n\n            bool flag = true;\n\n            for(auto &ed:restrictions){ // same by putting & here\n                int uu = ed[0], vv = ed[1];\n                int puu = find(uu, par), pvv = find(vv, par);\n                if((puu==pu && pvv==pv) || (puu==pv && pvv==pu)){\n                    flag = false;\n                    break;\n                }\n            }\n\n            if(flag) join(u,v,par,si);\n            ans.push_back(flag);\n        }\n        return ans;\n    }\n};\n```
['C++']