🌟Easy to understand C++ | Kruskal's Algorithm | Commented code |Runtime 110ms
Intuition\n Describe your first thoughts on how to solve this problem. \nAs the question deas with MST\'s, we have two standard algorithms in our arsenal - Prim
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs the question deas with MST\'s, we have two standard algorithms in our arsenal - Prim\'s and Kruskal\'s. We can use disjoint Set to form MST\'s and keep track of size of components. So, we will be using Kruskal\'s algorithm.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFind the MST wt of the entire graph. Now remove each edge and check if removing that edge increase the MST wt or if this edge is a bridge between components, if it does/is, then it is a critical edge, else we check if it is a pseudo-critical edge. For this, we check if we include this edge in an MST, and form the MST, will the MST weight remain same or increase. If it remains same, then this edge need not be present in all MSTs. This is because we already checked if this edge is critical, and as removing this edge doesn\'t increase MST weight and including this edge also doesn\'t have any effect, then this edge is pseudo critical.\n\nTip: Use another vector that also stores the index of the edge with it and sort it for kruskal, we call this ```edgeCopy```.\n# Complexity\n- Time complexity: $$O(m^2\u22C5 \u03B1(n))$$, where m is the number of edges, n is the number of nodes and \u03B1 is the inverse Ackermann function.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(m+n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass DisjointSet {\n    public:\n    vector<int> size, parent;\n\n    DisjointSet(int n)\n    {\n        size.resize(n, 1);\n        parent.resize(n + 1);\n        for (int i = 0; i < n; i++)\n        parent[i] = i;\n    }\n\n    int findUPar(int node)\n    {\n        if (parent[node] == node)\n        return node;\n\n        return parent[node] = findUPar(parent[node]);\n    }\n\n    void unionBySize(int u, int v)\n    {\n        int ulp_u = findUPar(u);\n        int ulp_v = findUPar(v);\n\n        if (ulp_u == ulp_v)\n        return;\n\n        if (size[ulp_u] >= size[ulp_v])\n        {\n            parent[ulp_v] = ulp_u;\n            size[ulp_u] += size[ulp_v];\n        }\n        else\n        {\n            parent[ulp_u] = ulp_v;\n            size[ulp_v] += size[ulp_u];\n        }\n    }\n};\n\nclass Solution {\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        // Step 1 - Find the MST wt of the entire graph. Now remove each edge and check if removing that edge increase the MST wt, if it does, then it is a critical edge, else we check if it is a pseudo-critical edge.\n        // Use another vector that also stores the index of the edge with it and sort it for kruskal\n        vector<vector<int>> edgeCopy;\n        for (int i = 0; i < edges.size(); i++)\n        {\n            int u = edges[i][0], v = edges[i][1], wt = edges[i][2];\n            edgeCopy.push_back({wt, u, v, i});\n        }\n        sort(edgeCopy.begin(), edgeCopy.end());\n\n        // Figure out the weight of MST!\n        DisjointSet MST(n);\n        int mstWt = 0;\n        for (auto &it: edgeCopy)\n        {\n            int wt = it[0], u = it[1], v = it[2];\n            if (MST.findUPar(u) != MST.findUPar(v))\n            {\n                mstWt += wt;\n                MST.unionBySize(u, v);\n            }\n        }\n\n        vector<int> criticalEdges;\n        vector<int> pseudocritEdges;\n\n        // Iterate edgeCopy and try removing an edge and check if it\'s critical.\n        for (int i = 0; i < edgeCopy.size(); i++)\n        {\n            // If weight increases or if all nodes aren\'t in 1 component, this edge is critical\n            int newMSTwt = 0;\n            DisjointSet ds(n);\n            int edgeIndex = edgeCopy[i][3];\n            // Ignoring the edge to check for criticality\n            for (int j = 0; j < edgeCopy.size(); j++)\n            {\n                if (i != j) // ignore edge\n                {\n                    int wt = edgeCopy[j][0], u = edgeCopy[j][1], v = edgeCopy[j][2];\n                    if (ds.findUPar(u) != ds.findUPar(v))\n                    {\n                        newMSTwt += wt;\n                        ds.unionBySize(u, v);\n                    }\n                }\n            }\n            if (newMSTwt > mstWt || ds.size[ds.findUPar(0)] < n) // weight increased or more than 1 component MST\n            criticalEdges.push_back(edgeIndex);\n            else\n            {\n                // We only check for pseudoCritical when we know it\'s not critical!\n                // Iterate edgeCopy and try forcing this edge and check if it\'s pseudo critical.\n                // If the total weight of the resulting MST is the same as the mstWt, this edge is pseudo-critical.\n            int forcedMSTwt = 0;\n            DisjointSet forcedDs(n);\n            int forcedWt = edgeCopy[i][0], forcedU = edgeCopy[i][1], forcedV = edgeCopy[i][2];\n            forcedDs.unionBySize(forcedU, forcedV);\n            forcedMSTwt += forcedWt;\n            // add this edge to Ds and create MST to check if it\'s psedo critical or not\n            for (int j = 0; j < edgeCopy.size(); j++)\n            {\n                if (i != j) // ignore edge as already counted\n                {\n                    int wt = edgeCopy[j][0], u = edgeCopy[j][1], v = edgeCopy[j][2];\n                    if (forcedDs.findUPar(u) != forcedDs.findUPar(v))\n                    {\n                        forcedMSTwt += wt;\n                        forcedDs.unionBySize(u, v);\n                    }\n                }\n            }\n            if (forcedMSTwt == mstWt) // weight remained  same\n            pseudocritEdges.push_back(edgeIndex);\n            }\n        }\n        vector<vector<int>> res;\n        res.push_back(criticalEdges);\n        res.push_back(pseudocritEdges);\n        return res;\n    }\n};\n```\n\n![Screenshot 2023-08-19 151429.png](https://assets.leetcode.com/users/images/5d5eb943-02d7-4758-ae58-6c75492851f5_1692438273.183074.png)\n
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'C++']