EASY SPANNING TREE SOLUTION
\n# PLS UPVOTE MY SOLUTION IF YOU LIKE IT AND COMMENT FOR DOUBTS\n# Approach\nClass UnionFind:\n\nThis class implements the Union-Find data structure with path 
\n# **PLS UPVOTE MY SOLUTION IF YOU LIKE IT AND COMMENT FOR DOUBTS**\n# Approach\nClass UnionFind:\n\nThis class implements the Union-Find data structure with path compression and union by rank optimizations. It is used to efficiently track and merge connected components.\nFunction findCriticalAndPseudoCriticalEdges:\n\nThis function takes the number of nodes n and a vector of edges representing the graph\'s edges.\nIt sorts the edges based on their weights in ascending order.\nFor each edge, it pushes its index into the vector to keep track of its original position.\nIt calculates the MST of the original graph (origin_mst) by calling the GetMST function without blocking any edge.\nIt iterates through all edges and calculates their impact on the MST:\nIf the MST weight increases after removing an edge, that edge is marked as critical.\nIf the MST weight remains the same after removing an edge, that edge is marked as non-critical.\nReturns a vector containing two sub-vectors: critical edges and non-critical edges.\nFunction GetMST:\n\nThis function calculates the weight of the MST using Kruskal\'s algorithm.\nIt takes the number of nodes n, the edges vector, an index of an edge to be blocked (blockedge), and an index of a potential edge to be included in the MST (pre_edge).\nInitializes Union-Find and weight variables.\nIf a pre_edge is provided, adds its weight to the MST and unions its endpoints.\nIterates through edges (excluding the blocked edge if specified):\nIf the endpoints of an edge are not in the same connected component, it is added to the MST and the endpoints are united.\nChecks if all nodes are in the same connected component (MST is formed).\nReturns the total weight of the MST.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:O(E log E)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(E)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\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```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'C++']