Kruskal's Algorithm with union find (C++)
Use Kruskal\'s algorithm to find the base MST\n2. For each edge, if MST excluding this edge results in higher weights, add this edge to critical edge list. Othe
1. Use Kruskal\'s algorithm to find the base MST\n2. For each edge, if MST excluding this edge results in higher weights, add this edge to critical edge list. Otherwise, if MST including this edge results in the same weight as in the base MST, add this edge to pseudo-crtitcal edge list.\n3. Use union-find to detect cycle in each case.\n```\nclass Solution {\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& eds) {\n        vector<vector<int>> edges;\n        edges.reserve(eds.size());\n        copy(eds.begin(), eds.end(), back_inserter(edges));\n        for (int i = 0; i<edges.size(); i++){\n            edges[i].push_back(i);\n        }\n        sort(edges.begin(), edges.end(), [](vector<int>& a, vector<int>& b){\n            return a[2]<b[2];\n        });\n        int nn = edges.size();\n        int base = MST(edges, -1, nn, n);\n        vector<vector<int>> res;\n        vector<int> cr, pcr;\n        for (int i = 0; i<nn; i++){\n          int newVal = MST(edges, i, nn, n);\n          if (newVal > base) cr.push_back(edges[i][3]);\n          else{\n              newVal = MST_p(edges, i, nn, n);\n              if (newVal == base) pcr.push_back(edges[i][3]);\n          }\n        }\n        res.push_back(cr);\n        res.push_back(pcr);\n        return res;\n    }\n    int MST(vector<vector<int>>& es, int i, int n, int nn){\n        vector<int> vec(nn, -1);\n        int res = 0;\n        int e_n = 0;\n        for (int j = 0; j<n; j++){\n            if (j == i) continue;\n            vector<int> vv = es[j];\n            if (find(vec, vv[0]) == find(vec, vv[1])){\n                continue;\n            }\n            res += vv[2];\n            Union(vec, vv[0], vv[1]);\n            e_n++;\n        }\n        if (e_n < nn-1) return INT_MAX;\n        return res;\n    }\n    int MST_p(vector<vector<int>>& es, int i, int n, int nn){\n        vector<int> vec(nn, -1);\n        int res = es[i][2];\n        Union(vec, es[i][0], es[i][1]);\n        for (int j = 0; j<n; j++){\n            if (j == i) continue;\n            vector<int> vv = es[j];\n            if (find(vec, vv[0]) == find(vec, vv[1])){\n                continue;\n            }\n            res += vv[2];\n            Union(vec, vv[0], vv[1]);\n        }\n        return res;\n    }\n    int find(vector<int>& vec, int i)  \n    {  \n        if (vec[i] == -1)  \n            return i;  \n        return find(vec, vec[i]);  \n    }   \n    void Union(vector<int>& vec, int x, int y)  \n    {  \n        int xs = find(vec, x);  \n        int ys = find(vec, y);  \n        if(xs != ys) \n        {  \n            vec[xs] = ys;  \n        }  \n    }  \n};\n```
[]