C++ | MST | Fastest | Easy to Understand
C++ | MST | Fastest | Easy to Understand\n\nclass UnionFind {\npublic:\n    UnionFind(int n) {\n        rank = vector<int>(n, 1);\n        f.resize(n);\n       
# C++ | MST | Fastest | Easy to Understand\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```
['C', 'C++']