C++ Solution, enumerating edges, with explanation
We use the standard MST algorithm as a baseline, and denote the total MST weight as origin_mst.\nTo generate critical and pseudo-critical lists, we enumerate ea
We use the standard MST algorithm as a baseline, and denote the total MST weight as `origin_mst`.\nTo generate critical and pseudo-critical lists, we enumerate each edge:\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```\nclass UnionFind {\npublic:\n    UnionFind(int n) {\n        rank = vector<int>(n, 1);\n        f.resize(n);\n        for (int i = 0; i < n; ++i) f[i] = i;\n    }\n    \n    int Find(int x) {\n        if (x == f[x]) return x;\n        else return f[x] = Find(f[x]);\n    }\n    \n    void Union(int x, int y) {\n        int fx = Find(x), fy = Find(y);\n        if (fx == fy) return;\n        if (rank[fx] > rank[fy]) swap(fx, fy);\n        f[fx] = fy;\n        if (rank[fx] == rank[fy]) rank[fy]++;\n    }\n    \nprivate:\n    vector<int> f, rank;\n};\n\nclass Solution {\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 origin_mst = GetMST(n, edges, -1);\n        vector<int> critical, non_critical;\n        for (int i = 0; i < edges.size(); ++i) {\n            if (origin_mst < GetMST(n, edges, i)) {\n                critical.push_back(edges[i][3]);\n            } else if (origin_mst == GetMST(n, edges, -1, i)) {\n                non_critical.push_back(edges[i][3]);\n            }\n        }\n        return {critical, non_critical};\n    }\n    \nprivate:\n    int GetMST(const int n, const vector<vector<int>>& edges, int blockedge, int pre_edge = -1) {\n        UnionFind uf(n);\n        int weight = 0;\n        if (pre_edge != -1) {\n            weight += edges[pre_edge][2];\n            uf.Union(edges[pre_edge][0], edges[pre_edge][1]);\n        }\n        for (int i = 0; i < edges.size(); ++i) {\n            if (i == blockedge) continue;\n            const auto& edge = edges[i];\n            if (uf.Find(edge[0]) == uf.Find(edge[1])) continue;\n            uf.Union(edge[0], edge[1]);\n            weight += edge[2];\n        }\n        for (int i = 0; i < n; ++i) {\n            if (uf.Find(i) != uf.Find(0)) return 1e9+7;\n        }\n        return weight;\n    }\n};\n```
[]