✅✅Beats 100%🔥🔥 | C++ | Kruskal's Algorithm | Beginner Friendly | Easy to Understand | Disjoint Set
Intuition\nUse the Kruskal\'s algorithm to find the minimum spanning tree by sorting the edges and picking edges from ones with smaller weights.\nUse a disjoint
# Intuition\nUse the Kruskal\'s algorithm to find the minimum spanning tree by sorting the edges and picking edges from ones with smaller weights.\nUse a disjoint set to avoid adding redundant edges that result in a cycle.\n\nTo find if one edge is critical, delete that edge and re-run the MST algorithm and see if the weight of the new MST increases.\n\nTo find if one edge is non-critical (in any MST), include that edge to the accepted edge list and continue the MST algorithm, then see if the resulting MST has the same weight of the initial MST of the entire graph.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: **O(E\u2217logE) + 2E*O(E\\*4\u03B1\\*2))**\nfor sorting + then applying Kruskal for each edge to check if its critical/pseudo-critical\nTC of every Kruskal:\nWe are using the disjoint set operations inside a loop. The loop will continue to E times. Inside that loop, there are two disjoint set operations like findParent() and unionByRank() each taking 4 and so it will result in 4\u03B1\\*2. That is why the last term O(E*4\u03B1\\*2) is added.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(N)**\n    Disjoint set takes O(N) space for storing each node\'s parent and rank\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass DSU{\n    public:\n    vector<int> rank,parent;\n    DSU(int n)\n    {\n        rank.resize(n);\n        parent.resize(n);\n        for(int i=0;i<n;i++)\n        {\n            parent[i]=i;\n            rank[i]=0;\n        }\n    }\n    int findParent(int i)\n    {\n        if(parent[i]==i)    return i;\n        return parent[i]=findParent(parent[i]);\n    }\n    void unionByRank(int u,int v)\n    {\n        u=findParent(u);\n        v=findParent(v);\n        if(u==v) return;\n        if(rank[u]>rank[v])\n            parent[v]=u;\n        else if(rank[u]<rank[v])\n            parent[u]=v;\n        else{\n            parent[v]=u;\n            rank[u]++;\n        }\n        return;\n    }\n    bool sameComponent(int u,int v){\n        return findParent(u)==findParent(v);\n    }\n};\nclass Solution {\npublic:\n    static bool comparator(vector<int>& e1,vector<int>& e2)\n    {\n        return e1[2]<e2[2];\n    }\n    int kruskal(int n, vector<vector<int>>& edges,int exclude=-1,int include=-1)\n    {\n        DSU dsu(n+1);\n        int mstWt=0;\n        int cnt=0;\n        if(include!=-1)\n        {\n            int u=edges[include][0];\n            int v=edges[include][1];\n            int wt=edges[include][2];\n            mstWt+=wt;\n            cnt++;\n            dsu.unionByRank(u,v);\n        }\n        for(int i=0;i<edges.size();i++)\n        {\n            if(i==exclude)  continue;\n            int u=edges[i][0];\n            int v=edges[i][1];\n            int wt=edges[i][2];\n            if(dsu.sameComponent(u,v))  continue;\n            mstWt+=wt;\n            cnt++;\n            dsu.unionByRank(u,v);\n        }\n        return (cnt==n-1)?mstWt:INT_MAX;\n    }\n\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        int E=edges.size();\n        for(int i=0;i<E;i++)\n            edges[i].push_back(i);  //numbering all edges\n        sort(edges.begin(),edges.end(),comparator);\n        int mstWt=kruskal(n,edges,-1,-1);\n        set<int> critical,pcritical;\n        for(int i=0;i<E;i++)\n        {\n            int newMstWt=kruskal(n,edges,i,-1);\n            if(newMstWt!=mstWt)\n                critical.insert(edges[i][3]);\n        }\n        for(int i=0;i<E;i++)\n        {\n            int newMstWt=kruskal(n,edges,-1,i);\n            if(newMstWt==mstWt && critical.find(edges[i][3])==critical.end())\n                pcritical.insert(edges[i][3]);\n        }\n        vector<vector<int>> ans(2);\n        for(auto it:critical)\n            ans[0].push_back(it);\n        for(auto it:pcritical)\n            ans[1].push_back(it);\n        return ans;\n    }\n};\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'Strongly Connected Component', 'C++']