Easy to Understand | C++ | Kruskal's MST |
Code\n\nclass Solution {\npublic:\n    bool static cmp(vector<int>p1,vector<int>p2){\n        return p1[2]<p2[2];\n    }\n    int find(int i,vector<int>&parent)
# Code\n```\nclass Solution {\npublic:\n    bool static cmp(vector<int>p1,vector<int>p2){\n        return p1[2]<p2[2];\n    }\n    int find(int i,vector<int>&parent){\n        if (parent[i] == -1)\n            return i;\n \n        return parent[i] = find(parent[i],parent);\n    }\n    void unite(int x, int y,vector<int>&parent,vector<int>&rank){\n        int s1 = find(x,parent);\n        int s2 = find(y,parent);\n \n        if (s1 != s2) {\n            if (rank[s1] < rank[s2]) {\n                parent[s1] = s2;\n            }\n            else if (rank[s1] > rank[s2]) {\n                parent[s2] = s1;\n            }\n            else {\n                parent[s2] = s1;\n                rank[s1] += 1;\n            }\n        }\n    }\n    void kruskal(int n,vector<vector<int>>edges,int &ans,int temp=-1,int src =-1,int dest=-1){\n        \n        vector<int>parent(n,-1);\n        vector<int>rank(n,1);\n        \n        if(temp!=-1){\n            ans+=edges[temp][2];\n            unite(edges[temp][0],edges[temp][1],parent,rank);\n        }\n\n        for(auto it:edges){\n            int x = it[0];\n            int y = it[1];\n            int w = it[2];\n            int idx = it[3];\n\n            if(x==src and y==dest) continue;\n\n            if(find(x,parent) != find(y,parent)){\n                unite(x,y,parent,rank);\n                ans+=w;\n            }\n        }\n\n        for(int i =0;i<n;i++){\n            if(find(i,parent)!=find(0,parent)) ans= INT_MAX;\n        }\n    }\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n\n        int weig = 0;\n\n        for(int i=0;i<edges.size();i++){\n            edges[i].push_back(i);\n        }\n\n        sort(edges.begin(),edges.end(),cmp);\n\n        kruskal(n,edges,weig);\n\n        vector<int>ans1;\n        vector<int>ans2;\n\n        for(int i=0;i<edges.size();i++){\n            int src = edges[i][0];\n            int dest = edges[i][1];\n            int curr_weig =0;\n\n            kruskal(n,edges,curr_weig,-1,src,dest);\n\n            if(curr_weig>weig){\n                ans1.push_back(edges[i][3]);\n            }\n            else{\n                curr_weig =0;\n                kruskal(n,edges,curr_weig,i,src,dest);\n                if(curr_weig==weig){\n                    ans2.push_back(edges[i][3]);\n                }\n            }\n        }\n        return {ans1,ans2};\n    }\n};\n```
['Union Find', 'Graph', 'Sorting', 'C++']