Beats 100% solution || C++ || Easy To understand || Union - Find || Kruskal's algorithm | | MST
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem revolves around understanding the roles of edges in a Minimum Spanning Tree
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem revolves around understanding the roles of edges in a Minimum Spanning Tree (MST). To determine whether an edge is critical or pseudo-critical:\n- **Critical Edge:** Removing this edge prevents the formation of an MST or increases its weight.\n- **Pseudo-Critical Edge:** Including this edge does not change the MST\'s weight but ensures it is part of some MST.\n\nUsing Kruskal\'s algorithm and concepts like union-find (disjoint-set), we can simulate different scenarios by forcibly including or excluding edges.\n\n---\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Input Preparation:**\n   - Store edges as a list of structures containing source, destination, weight, and the original index.\n   - Sort the edges by weight, as required by Kruskal\'s algorithm.\n\n2. **MST Calculation:**\n   - Use a standard Kruskal\'s algorithm to calculate the weight of the MST for the original graph (`mstWeight`).\n\n3. **Critical Edges:**\n   - For each edge, skip it while running Kruskal\'s algorithm. If skipping the edge increases the MST weight or makes it impossible to form an MST (disconnected graph), the edge is **critical**.\n\n4. **Pseudo-Critical Edges:**\n   - For each edge, forcibly include it first in the MST and then run Kruskal\'s algorithm. If the MST weight remains the same, the edge is **pseudo-critical**.\n\n5. **Union-Find Optimization:**\n   - Use a disjoint-set union (DSU) data structure to optimize the merging of nodes and detect cycles efficiently.\n\n6. **Edge Categorization:**\n   - Categorize edges into critical and pseudo-critical based on the results of the above operations and return them.\n\n---\n\n# Complexity\n- # Time complexity: \\(O(E^2 log V)\\).\n-  # Space complexity: \\(O(V + E)\\).\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n---\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    int find(vector<int> &parent, int a) {\n        return parent[a] = ((parent[a] == a) ? a : find(parent, parent[a]));\n    }\n\n    void Union(vector<int> &par, vector<int> &rank, int a, int b) {\n        a = find(par, a);\n        b = find(par, b);\n        if(a == b) return;\n        if(rank[a] >= rank[b]) {\n            rank[a]++;\n            par[b] = a;\n        } else {\n            rank[b]++;\n            par[a] = b;\n        }\n    }\n\n    struct Edge {\n        int src;\n        int dest;\n        int wt;\n        int index;\n    };\n\n    static bool cmp(Edge e1, Edge e2) {\n        return e1.wt < e2.wt;\n    }\n\n    int kruskals(vector<Edge> &input, int n,int skip_edge,int add_edge) { // O(V + ElgE)\n        vector<int> parent(n);\n        vector<int> rank(n, 1);\n        for(int i = 0; i < n; i++) {\n            parent[i] = i;\n        }\n        int edgeCount = 0; // n-1\n        int i = 0;\n        int ans = 0;\n        if(add_edge != -1){\n            Edge &e = input[add_edge];\n            Union(parent, rank, e.src, e.dest);\n            edgeCount++;\n            ans+=e.wt;\n        }\n        while(edgeCount < n-1 and i < input.size()) { // V-1 -> O(Vlg*V)\n            if(i==skip_edge){\n                i++;\n                continue;\n            } \n            Edge curr = input[i]; // because input is sorted so we will get min wt edge\n            int srcPar = find(parent, curr.src);\n            int destpar = find(parent, curr.dest);\n\n            if(srcPar != destpar) {\n                // include edge as this will not make cycle\n                Union(parent, rank, srcPar, destpar);\n                ans += curr.wt;\n                edgeCount++;\n            }\n\n            i++; // doesnt matter u picked the last edge or not, we still need to go to next edge\n        }\n        if (edgeCount < n - 1) return INT_MAX;\n        return ans;\n    }\n\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<Edge> v(edges.size());\n        for(int i = 0; i < edges.size(); i++) {\n            v[i]={edges[i][0], edges[i][1], edges[i][2], i};\n        }\n        sort(v.begin(), v.end(), cmp); // ElgE\n        int mst_weight=kruskals(v,n,-1,-1);\n        vector<int>critcal;\n        vector<int>Pseudo_critcal;\n        for(int i=0;i<edges.size();i++){\n            if(kruskals(v,n,i,-1)>mst_weight){//skiping i th edge\n                critcal.push_back(v[i].index);\n            }\n            else if(kruskals(v,n,-1,i)==mst_weight){//force add this edge\n                Pseudo_critcal.push_back(v[i].index);\n            }\n        }\n        return {critcal,Pseudo_critcal};\n    }\n};\n```\n\n---\n\n# Thanks for watching my code! \uD83D\uDE0A\n
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'C++']