Easy Union Find Video Solution 🔥 || Math ✅ || why DSU ?
Easy Video Solution (Why DSU ?)\n\nhttps://youtu.be/K2MlRRGEUog\n\n# Code\n\nclass Solution {\npublic:\n    vector<int>par;\n    vector<int>rank;\n    vector<in
# Easy Video Solution (Why DSU ?)\n\nhttps://youtu.be/K2MlRRGEUog\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int>par;\n    vector<int>rank;\n    vector<int>wgt;\n    int find(int n) {\n        if(par[n]!=n)\n            return find(par[n]);\n        return par[n];\n    }\n    void merge(int s,int d,int w) {\n        int ps=find(s);\n        int pd=find(d);\n        if(ps==pd) {\n            if(wgt[ps]==-1)\n                wgt[ps]=w;\n            else\n                wgt[ps]=(wgt[ps]&w);\n            return;\n            \n        }\n        if(rank[ps]>rank[pd]) {\n            par[pd]=ps;\n            if(wgt[ps]==-1)\n                wgt[ps]=w;\n            else\n                wgt[ps]=(wgt[ps]&w&wgt[pd]);\n            rank[ps]++;\n            \n        } else {\n            par[ps]=pd;\n            if(wgt[pd]==-1)\n                wgt[pd]=w;\n            else\n                wgt[pd]=(wgt[pd]&w&wgt[ps]);\n            rank[pd]++;\n        }\n    }\n    vector<int> minimumCost(int n, vector<vector<int>>& v, vector<vector<int>>& q) {\n        for(int i=0;i<n;i++) {\n            par.push_back(i);\n            rank.push_back(0);\n            wgt.push_back(-1);\n        }\n        vector<int>ans;\n        for(int i=0;i<v.size();i++) {\n            int s=v[i][0],d=v[i][1],w=v[i][2];\n            merge(s,d,w);\n        }\n        int m=q.size();\n        for(int i=0;i<m;i++) {\n            int s=q[i][0],d=q[i][1];\n            if(s==d) {\n                ans.push_back(0);\n                continue;\n            }\n            int ps=find(s);\n            int pd=find(d);\n            if(ps!=pd)\n                ans.push_back(-1);\n            else\n                ans.push_back(wgt[ps]);\n        }\n        return ans;\n    }\n};\n```
['Math', 'Union Find', 'C++']