Easy C++ Solution using Kruskal's Algorithm with DSU with Path Compression and Union by Rank 🔥🔥
Code\n\nclass Solution {\nprivate:\n    // .................................................. //\n    // DSU implementation //\n    // creating struct for edge\
# Code\n```\nclass Solution {\nprivate:\n    // .................................................. //\n    // DSU implementation //\n    // creating struct for edge\n    struct Edge {\n        int src, dst, wt , serial;\n        Edge(int s, int d, int w, int n) {\n            src = s;\n            dst = d;\n            wt = w;\n            serial = n;\n        }\n    };\n    // Using Union by rank and path compression\n    vector<int> par;\n    vector<int> rank;\n    // path compression\n    void initialize(int n) {\n        par = vector<int>(n);\n        rank = vector<int>(n);\n        for(int i = 0; i < n; i++) {\n            par[i] = i;\n            rank[i] = 0;\n        }\n    }\n    void unionn(int x, int y) {\n        int x_rep = find(x), y_rep = find(y);\n        if(x_rep == y_rep) return;\n        if(rank[x_rep] < rank[y_rep])   par[x_rep] = y_rep;\n        else if(rank[x_rep] > rank[y_rep])  par[y_rep] = x_rep;\n        else {\n            par[y_rep] = x_rep;\n            rank[x_rep]++;\n        }\n    }\n    int find(int x) {\n        if(x == par[x])\n            return x;\n        par[x] = find(par[x]);\n        return par[x];\n    }\n    // DSU implementation //\n    // ................................................... //\n    vector<Edge> edge;\n    static bool myCmp(Edge& e1, Edge& e2) {\n        return e1.wt < e2.wt;\n    }\n    int findMSTWt(int n, int m, int include, int exclude) {\n        int ret = 0;\n        initialize(n);\n        // if any edge is to be included include it at first\n        int i, s = 0;\n        if(include != -1) {\n            Edge e = edge[include];\n            unionn(e.src, e.dst);\n            ret += e.wt;\n            s++;\n        }\n        // finding MST using Kruskal\'s Algorithm\n        for(int i = 0; s < n - 1 and i < m; i++) {\n            if(i == exclude)    continue;\n            Edge e = edge[i];\n            int x = find(e.src);\n            int y = find(e.dst);\n            // if no cycle then add\n            if(x != y) {\n                ret += e.wt;\n                unionn(x,y);\n                s++;\n            }\n        }\n        if(s < n - 1)\n            ret = 1e8;\n        return ret;\n    }\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        // using Kruskal\'s algorithm\n        int m = edges.size();\n        for(int i = 0; i < m; i++) {\n            Edge e(edges[i][0], edges[i][1], edges[i][2], i);\n            edge.push_back(e);\n        }\n        sort(edge.begin() , edge.end() , myCmp);\n        vector<vector<int>> ans(2);\n        int mn = findMSTWt(n, m, -1, -1);\n        // finding critical edges\n        // just exclude every edge if MST wt. increases then it is critical edge\n        // finding pseudo - critical edges\n        // just include every edge if MST wt. remains same then it is pseudo critical edge\n        for(int i = 0; i < m; i++) {\n            int curr1 = findMSTWt(n, m, -1, i);\n            if(curr1 > mn) {\n                ans[0].push_back(edge[i].serial);\n                continue;\n            }\n            int curr2 = findMSTWt(n, m, i, -1);\n            if(curr2 == mn)   ans[1].push_back(edge[i].serial);\n        }\n        return ans;\n    }\n};\n```
['Union Find', 'Graph', 'Sorting', 'Minimum Spanning Tree', 'C++']