C++ || MST || Disjoint Set / Union Find
\nclass Solution {\nprivate:\n    vector<int> prnt, rnk;\n\n    int find(int u) {\n        if(prnt[u] == -1) return u;\n        return prnt[u] = find(prnt[u]);\
```\nclass Solution {\nprivate:\n    vector<int> prnt, rnk;\n\n    int find(int u) {\n        if(prnt[u] == -1) return u;\n        return prnt[u] = find(prnt[u]);\n    }\n\n    void merge(int u, int v) {\n        u = find(u);\n        v = find(v);\n\n        if(rnk[u] < rnk[v]) swap(u, v);\n\n        rnk[u] += rnk[v];\n        prnt[v] = u;\n    }\n    \n    int mst(vector<vector<int>>& edges, vector<int> included, vector<int> excluded) {\n        for(int i = 0; i < prnt.size(); i++) {\n            prnt[i] = -1;\n            rnk[i] = 1;\n        }\n        \n        int cost = 0;\n        if(included.size() > 0) {\n            merge(included[0], included[1]);\n            cost += included[2];\n        }\n        \n        for(vector<int> edge: edges) {\n            if(excluded.size() == edge.size() && excluded[3] == edge[3])\n                continue;\n            else if(find(edge[0]) != find(edge[1])) {\n                merge(edge[0], edge[1]);\n                cost += edge[2];\n            }\n        }\n        \n        return rnk[find(0)] == prnt.size() ? cost : INT_MAX;\n    }\n\n    \n    static bool cmp(vector<int> &a, vector<int> &b) {\n        return a[2] < b[2];\n    }\n    \npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        rnk = vector<int>(n, 1);\n        prnt = vector<int>(n, -1);\n        \n        \n        // add index of i\'th edge\n        // {u, v, weight, i}\n        for(int i = 0; i < edges.size(); i++) {\n            edges[i].push_back(i);\n        }\n        \n        // sort non-decreasing order of weight\n        sort(edges.begin(), edges.end(), cmp);\n        \n        int min_cost = mst(edges, vector<int>(), vector<int>());\n        \n        vector<int> critical, psudo;\n        for(vector<int> edge: edges) {\n            // excluding edge\n            int ex_cost = mst(edges, vector<int>(), edge);\n            if(ex_cost > min_cost) {\n                critical.push_back(edge[3]);\n            } else if(ex_cost == min_cost) {\n                // included edge\n                int in_cost = mst(edges, edge, vector<int>());\n                if(in_cost == ex_cost) \n                    psudo.push_back(edge[3]);\n            }\n        }\n        \n        return {critical, psudo};\n    }\n};\n\n```
['Union Find', 'C']