✅ [C++] Simple Solution using Kruskal Algorithm
Intuition\n- Firstly, run the MST algorithm to find the total weight of Minimum Spanning Tree of the graph.\n- To find if one edge is critical, delete that edge
# Intuition\n- Firstly, run the MST algorithm to find the total weight of Minimum Spanning Tree of the graph.\n- To 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- To find if a non-critical edge is peudo-critical, include that edge and re-run the MST algorithm and see if the weight of the new MST the same.\n- Since we only interactive with edges of the MST, so Kruskal\'s Algorithm is a best fit to solve this problem.\n\n# Approach\nWe use the kruskal MST algorithm, and denote the total MST weight as `original_mst`.\nTo generate critical and pseudo-critical lists, we enumerate each edge:\n\n1. If deleting the edge and re-calculating the mst again makes mst total weight increase (or can\'t form mst), then the edge goes into critical list.\n2. If we force adding the edge to the mst (by first adding the edge to the mst edge set and run the standard MST algorithm for the rest of the edges), and find that the mst doesn\'t change, then the edge goes into pseudo-critical list. (This is because if an edge can be in any mst, we can always add it to the edge set first, without changing the final mst total weight).\n\n# Complexity\n- Time complexity: `O(ElogE + ElogV)`, which is approximately `O(ElogV)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(V + E)`, where V is the number of vertices and E is the number of edges in the graph.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass DisjointSet {\n    vector<int> parent, size;\npublic:\n    DisjointSet(int n) {\n        parent.resize(n+1);\n        size.resize(n+1);\n        for (int i=0; i<=n; i++) {\n            parent[i] = i;\n            size[i] = 1;\n        }\n    }\n    int findUPar(int node) {\n        if (node == parent[node]) {\n            return node;\n        }\n        return parent[node] = findUPar(parent[node]);\n    }\n    void unionBySize(int u, int v) {\n        int ulp_u = findUPar(u);\n        int ulp_v = findUPar(v);\n        if (ulp_u == ulp_v) {\n            return;\n        }\n        if (ulp_u < ulp_v) {\n            parent[ulp_u] = ulp_v;\n            size[ulp_u] += size[ulp_v];\n        } else {\n            parent[ulp_v] = ulp_u;\n            size[ulp_v] += size[ulp_u];\n        }\n    }\n};\n\nclass Solution {\n    int kruskal(int n, vector<vector<int>>& edges, int skip, int prev = -1) {\n        DisjointSet ds(n);\n        int mst_weight = 0;\n        if (prev != -1) {\n            mst_weight += edges[prev][2];\n            ds.unionBySize(edges[prev][0], edges[prev][1]);\n        }\n        for (int i=0; i<edges.size(); i++) {\n            if (i == skip) {\n                continue;\n            }\n            int u = edges[i][0];\n            int v = edges[i][1];\n            int wt = edges[i][2];\n            if (ds.findUPar(u) == ds.findUPar(v)) {\n                continue;\n            }\n            ds.unionBySize(u, v);\n            mst_weight += wt;\n        }\n        for (int i=0; i<n; i++) {\n            if (ds.findUPar(i) != ds.findUPar(0)) {\n                return INT_MAX;\n            }\n        }\n        return mst_weight;\n    }\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        for (int i=0; i<edges.size(); i++) {\n            edges[i].push_back(i);\n        }\n        sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[2] < b[2];\n        });\n        int original_mst = kruskal(n, edges, -1);\n        vector<int> critical, non_critical;\n        for (int i=0; i<edges.size(); i++) {\n            if (original_mst < kruskal(n, edges, i)) {\n                critical.push_back(edges[i][3]);\n            } else if (original_mst == kruskal(n, edges, -1, i)) {\n                non_critical.push_back(edges[i][3]);\n            }\n        }\n        return {critical, non_critical};\n    }\n};\n```
['Union Find', 'Graph', 'Minimum Spanning Tree', 'C++']