[ C++ ] [ DSU ]
Code\n\nclass Solution {\npublic:\n    // Define a DSU class for union-find operations\n    class DSU {\n        vector<int> parent, size;\n    public:\n       
# Code\n```\nclass Solution {\npublic:\n    // Define a DSU class for union-find operations\n    class DSU {\n        vector<int> parent, size;\n    public:\n        DSU(int n) {\n            parent.resize(n);\n            size.resize(n, 1);\n            for (int i = 0; i < n; ++i)\n                parent[i] = i;\n        }\n        \n        int find(int x) {\n            if (parent[x] != x)\n                parent[x] = find(parent[x]);\n            return parent[x];\n        }\n        \n        bool unite(int x, int y) {\n            int rootX = find(x);\n            int rootY = find(y);\n            if (rootX == rootY)\n                return false;\n            \n            if (size[rootX] < size[rootY]) {\n                parent[rootX] = rootY;\n                size[rootY] += size[rootX];\n            } else {\n                parent[rootY] = rootX;\n                size[rootX] += size[rootY];\n            }\n            \n            return true;\n        }\n\n        int getSize(int x) {  // Add a public method to get the size of a set\n            return size[find(x)];\n        }\n    };\n    \n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        int m = edges.size();\n        for (int i = 0; i < m; ++i)\n            edges[i].push_back(i); // Store the original index\n        \n        sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[2] < b[2];\n        });\n        \n        DSU dsu(n);\n        int mstWeight = 0;\n        for (int i = 0; i < m; ++i) {\n            if (dsu.unite(edges[i][0], edges[i][1]))\n                mstWeight += edges[i][2];\n        }\n        \n        vector<int> critical, pseudoCritical;\n        for (int i = 0; i < m; ++i) {\n            DSU tempDsu(n);\n            int weightWithout = 0;\n            for (int j = 0; j < m; ++j) {\n                if (i != j && tempDsu.unite(edges[j][0], edges[j][1]))\n                    weightWithout += edges[j][2];\n            }\n            \n            if (tempDsu.getSize(0) != n || weightWithout > mstWeight)\n                critical.push_back(edges[i][3]); // Store the original index\n            else {\n                DSU newDsu(n);\n                newDsu.unite(edges[i][0], edges[i][1]);\n                int weightWith = edges[i][2];\n                for (int j = 0; j < m; ++j) {\n                    if (i != j && newDsu.unite(edges[j][0], edges[j][1]))\n                        weightWith += edges[j][2];\n                }\n                \n                if (weightWith == mstWeight)\n                    pseudoCritical.push_back(edges[i][3]); // Store the original index\n            }\n        }\n        \n        return {critical, pseudoCritical};\n    }\n};\n\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'Strongly Connected Component', 'C++']