C++ | Striver | Kruskal's | DSU | Easy to Understand
Approach\nIt is an extenstion of Kruskal\'s Algorithm to find the critical and pseudo critical edges.\n\n# Complexity\n- Time complexity: E^2 + ElogE\n Add your
# Approach\nIt is an extenstion of Kruskal\'s Algorithm to find the critical and pseudo critical edges.\n\n# Complexity\n- Time complexity: E^2 + E*logE\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: V , V is nodes\n*Neglecting the space required to store answer.*\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n\n    class DSU{\n\n        public:\n\n        vector <int> parent;\n        vector <int> size;\n\n        DSU(int n){\n\n            parent.resize(n,0);\n            size.resize(n,1);\n\n            for(int i=0 ; i<n ; i++){\n                parent[i] = i;\n            }\n        }\n\n        int findUPar(int node){\n\n            if(node == parent[node]){\n                return node;\n            }\n\n            return parent[node] = findUPar(parent[node]);\n\n        }\n\n        void unionBySize(int u , int v){\n\n            int up_u = findUPar(u);\n            int up_v = findUPar(v);\n\n            // Already connected to the same set\n            if(up_u == up_v) return;\n\n            if(size[up_u] > size[up_v]){\n                size[up_u] += size[up_v];\n                parent[up_v] = up_u; \n            }\n\n            else{\n\n                size[up_v] += size[up_u];\n                parent[up_u] = up_v;\n            }\n\n        }\n\n    };\n\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n\n        // DSU object d\n        DSU d(n);\n\n        auto newEdges = edges;\n        \n        // Add index to edges for tracking\n        int m = newEdges.size();\n        \n        for (int i = 0; i < m; i++) {\n            newEdges[i].push_back(i);\n        }\n\n        // Sort edges based on weight\n        sort(newEdges.begin(), newEdges.end(), [](auto& a, auto& b) {\n            return a[2] < b[2];\n        });\n\n\n        int mst = 0;\n\n        // Now traverse in edges and check if already being connected or not\n\n        for(auto &edge: newEdges){\n\n            int u = edge[0];\n            int v = edge[1];\n            int wt = edge[2];\n\n            // Check if not already connected\n\n            if(d.findUPar(u) != d.findUPar(v)){\n\n                d.unionBySize(u,v);\n                mst += wt;\n            }\n\n        }\n\n        // Now finding out the critical edges\n        vector <int> criticalEdges;\n        vector <int> pseudocriticalEdges;\n\n        for(int i=0 ; i<m ; i++){\n\n            // Deleting or ignoring the ith edges while calculating MST\n            DSU x(n);\n            int currMst = 0;\n\n            for(int j = 0 ; j<m ; j++){\n\n                if(i != j){\n\n                    int u = newEdges[j][0];\n                    int v = newEdges[j][1];\n                    int wt = newEdges[j][2];\n\n                    // Check if not already connected\n\n                    if(x.findUPar(u) != x.findUPar(v)){\n\n                        x.unionBySize(u,v);\n                        currMst += wt;\n\n                    }\n\n                }\n            }\n\n            // Now if my CurrMST is greater than mst means we have ignored a critical edge\n            // ot currMst is smaller than even the standard MST value means , removing ith edge leads to disconnected components , hence i is also an critical edge\n\n            if(currMst > mst or currMst < mst){\n\n                criticalEdges.push_back(newEdges[i][3]);\n            }\n\n            // Now find the pseudo critical nodes\n\n            else{\n\n                // Force this ith edge and again calculate the MST , if forcing this node has does not have any effect on the original mst that means it a pseduo critical node\n\n                DSU y(n);\n\n                // forced the edge ant took UNION\n                y.unionBySize(newEdges[i][0] , newEdges[i][1]);\n\n                int forcedMST = newEdges[i][2];\n\n                for(int j = 0 ; j<m ; j++){\n\n                    if(i != j){\n\n                        int u = newEdges[j][0];\n                        int v = newEdges[j][1];\n                        int wt = newEdges[j][2];\n\n                        // Check if not already connected\n\n                        if(y.findUPar(u) != y.findUPar(v)){\n\n                            y.unionBySize(u,v);\n                            forcedMST += wt;\n                        }\n\n                    }\n                }\n\n                if(forcedMST == mst) pseudocriticalEdges.push_back(newEdges[i][3]);\n\n            }\n\n        }\n\n        \n        return {criticalEdges , pseudocriticalEdges};\n\n    }\n};\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'C++']