Beats 98 %🔥 | Intuition + Approach Explained | Hard made Easy ✅
Intuition\nThe intuition behind this solution lies in the fact that critical edges directly impact the MST\'s weight, while pseudo-critical edges do not necessa
# Intuition\nThe intuition behind this solution lies in the fact that critical edges directly impact the MST\'s weight, while pseudo-critical edges do not necessarily affect the MST\'s weight. By building the MST and analyzing the impact of removing edges, the algorithm can categorize edges into critical and pseudo-critical groups.\n\n# Approach\nLet\'s break down the solution step by step :\n\n1. **Understanding the DSU:**\n   - You start by understanding that you need a data structure called **Disjoint Set Union (DSU)** to manage the connectivity of vertices. This data structure has two main operations: finding the parent of a set (group) and uniting two sets.\n   \n2. **Sorting Edges for Greedy Selection:**\n   - You have a list of edges, each with a weight representing its importance. You realize that you can prioritize selecting edges based on their weights to build the Minimum Spanning Tree (MST) greedily.\n   - So, you sort the edges in ascending order of their weights. This will help you pick edges with the lowest weights first while building the MST.\n   \n3. **Building the Minimum Spanning Tree (MST):**\n   - Now that the edges are sorted, you\'re ready to construct the MST using a greedy approach.\n   - You iterate through the sorted edges one by one. For each edge:\n     - You check if the two nodes of the edge are not already in the same group (set) using the DSU.\n     - If they are not, you unite the sets containing those nodes (DSU\'s union operation), signifying that they are now connected in the MST, and you add the edge to the MST.\n   \n4. **Finding Critical Edges:**\n   - With the MST constructed, you focus on identifying critical edges, which are edges that, when removed, would increase the total weight of the MST.\n   - To find these, you iterate through the edges in your MST:\n     - For each edge, you temporarily remove it from the MST and calculate the weight of the new MST.\n     - If this new weight is greater than the original MST weight, you mark the edge as critical. Otherwise, you leave it in the MST.\n\n5. **Finding Pseudo-Critical Edges:**\n   - Next, you want to find pseudo-critical edges, which are edges that could be in some MSTs but not all.\n   - You iterate through each edge (including the ones not in the MST):\n     - For each edge, you simulate building an MST without that edge.\n     - If the weight of this new MST is the same as the weight of the original MST, you consider the edge as pseudo-critical.\n\n6. **Final Categorization and Cleaning Up:**\n   - Now you have two lists: one for critical edges and one for pseudo-critical edges.\n   - However, some edges could be both critical and pseudo-critical, which you don\'t want. So you make sure to remove those from the pseudo-critical list.\n   - Finally, you have a complete list of critical edges and pseudo-critical edges that you can return as the result.\n\n# Complexity\n- Time complexity: $$O(E * log E)$$  mainly comes from the sorting step O(E log E) where E is the number of edges and the DSU operations O(E)\n\n- Space complexity: $$O(n + len)$$ where n is the number of vertices and len is the number of edges in the graph.\n\n# Code\n```\nclass Solution {\npublic:\n    class DSU {\n    public:\n        int findParent(int node, vector<int>& par) {\n            if (par[node] == node) return node;\n            return par[node] = findParent(par[node], par);\n        }\n        void Union(int u, int v, vector<int>& size, vector<int>& par) {\n            int pu = findParent(u, par);\n            int pv = findParent(v, par);\n            if (pu == pv) return;\n            if (size[pu] <= size[pv]) {\n                par[pu] = pv;\n                size[pv]++;\n            } else {\n                par[pv] = pu;\n                size[pu]++;\n            }\n        }\n    };\n\n    static bool comp(vector<int>& v1, vector<int>& v2) {\n        return v1[2] < v2[2];\n    }\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        int len = edges.size();\n        for (int i = 0; i < len; i++)\n            edges[i].push_back(i);\n\n        sort(edges.begin(), edges.end(), comp);\n\n        DSU dsu;\n        int cost = 0;\n        vector<int> par(n);\n        vector<int> size(n, 1);\n        for (int i = 0; i < n; i++) par[i] = i;\n        vector<bool> isPart(len, 0);\n        int c = 0;\n        for (int i = 0; i < len; i++) {\n            if (c == n - 1) break;\n            if (dsu.findParent(edges[i][0], par) != dsu.findParent(edges[i][1], par)) {\n                dsu.Union(edges[i][0], edges[i][1], size, par);\n                isPart[edges[i][3]] = 1;\n                cost += edges[i][2];\n                ++c;\n            }\n        }\n        vector<int> critical, pseudocritical;\n        for (int i = 0; i < len; i++) {\n            DSU tempDSU;\n            vector<int> tempPar(n, 0);\n            for (int j = 0; j < n; j++) tempPar[j] = j;\n\n            vector<int> tempSize(n, 1);\n            int tempCost = 0;\n            vector<bool> temp(len, 0);\n            int c = 0;\n            for (int j = 0; j < len; j++) {\n                if (c == n - 1) break;\n                if (j == i) continue;\n                if (tempDSU.findParent(edges[j][0], tempPar) != tempDSU.findParent(edges[j][1], tempPar)) {\n                    tempDSU.Union(edges[j][0], edges[j][1], tempSize, tempPar);\n                    temp[edges[j][3]] = 1;\n                    tempCost += edges[j][2];\n                    c++;\n                }\n            }\n            if (tempCost == cost) {\n                for (int k = 0; k < len; k++) {\n                    if (temp[k]) isPart[k] = 1;\n                }\n            } else\n                critical.push_back(edges[i][3]);\n        }\n\n        for (int i = 0; i < len; i++) {\n            if (isPart[edges[i][3]]) continue;\n            DSU tempDSU;\n            vector<int> tempPar(n, 0);\n            for (int j = 0; j < n; j++) tempPar[j] = j;\n            vector<int> tempSize(n, 1);\n            int tempCost = 0;\n            tempDSU.Union(edges[i][0], edges[i][1], tempSize, tempPar);\n            tempCost += edges[i][2];\n            int c = 0;\n            for (int j = 0; j < len; j++) {\n                if (c == n - 1) break;\n                if (j == i) continue;\n                if (tempDSU.findParent(edges[j][0], tempPar) != tempDSU.findParent(edges[j][1], tempPar)) {\n                    tempDSU.Union(edges[j][0], edges[j][1], tempSize, tempPar);\n                    tempCost += edges[j][2];\n                    ++c;\n                }\n            }\n            if (tempCost == cost)\n                pseudocritical.push_back(edges[i][3]);\n        }\n        for (auto& it : critical)\n            isPart[it] = 0;\n        for (int i = 0; i < len; i++) {\n            if (isPart[i])\n                pseudocritical.push_back(i);\n        }\n        return { critical, pseudocritical };\n    }\n};\n\n```
['Union Find', 'Sorting', 'Minimum Spanning Tree', 'C++']