Well structured C++ O(ElogE) code with clear comments, Kruskal+Tarjan
The code was inspired by this post. To solve the problem with O(ElogE) time complexity, you need to understand several algorithms as prerequisites:\n1. Kruskal\
The code was inspired by this [post](https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/discuss/698025/O(ElogE)-Kruskal%2BTarjan). To solve the problem with O(ElogE) time complexity, you need to understand several algorithms as prerequisites:\n1. Kruskal\u2019s Minimum Spanning Tree Algorithm (LeetCode medium [problem](https://leetcode.com/problems/connecting-cities-with-minimum-cost/))\n\t* \tUnion-find (or disjoint set) data structure\n2. Tarjan\'s bridge-finding algorithm (Leetcode hard [problem](https://leetcode.com/problems/critical-connections-in-a-network/))\n```\nclass UnionFind {\n    vector<int> setof, rank;\npublic:\n    UnionFind(int n) {\n        setof.resize(n);\n        rank.resize(n);\n        for (int i = 0; i < n; ++i) {\n            setof[i] = i;\n            rank[i] = 0;\n        }\n    }\n    \n    void merge(int x, int y) {\n        int rx = find(x), ry = find(y);\n        if (rx != ry) {\n            if (rank[rx] > rank[ry]) {\n                swap(rx, ry);\n            }\n            setof[rx] = ry;\n            if (rank[rx] == rank[ry]) {\n                rank[ry]++;\n            }\n        }\n    }\n    \n    int find(int x) {\n        if (setof[x] == x) {\n            return x;\n        }\n        return setof[x] = find(setof[x]);\n    }\n};\n\nclass TarjanSolver {\n    int n;\n    unordered_map<int, int> nodes;\n    unordered_set<int> bridges;\n    vector<vector<vector<int>>> edges;\n    vector<int> ancestors;\n    vector<bool> vis;\npublic:\n    TarjanSolver(vector<vector<int>>& inputEdges) {\n        n = 0;\n        nodes.clear();\n        for (vector<int>& e : inputEdges) {\n            for (int j = 0; j < 2; ++j) {\n                if (nodes.count(e[j]) == 0) {\n                    // map node indices to component indices in the new graph\n                    nodes[e[j]] = n++;\n                }\n                e[j] = nodes[e[j]];\n            }\n        }\n        edges.assign(n, {});\n        for (vector<int>& e : inputEdges) {\n            int u = e[0], v = e[1], i = e[2];\n            edges[u].push_back({v, i});\n            edges[v].push_back({u, i});\n        }\n    }\n    \n    /*\n        returns 2 lists:\n        1. indices of critical edges\n        2. indices of pseudo-critical edges\n    */\n    vector<vector<int>> solve() {\n        bridges.clear();\n        ancestors.assign(n, 0);\n        vis.assign(n, false);\n        for (int u = 0; u < n; ++u) {\n            if (!vis[u]) {\n                dfs(u, -1, 0);\n            }\n        }\n        vector<vector<int>> result(2, vector<int>());\n        for (int u = 0; u < n; ++u) {\n            for (int j = 0; j < edges[u].size(); ++j) {\n                int v = edges[u][j][0], i = edges[u][j][1];\n                // avoid duplicates\n                if (u < v) {\n                    // critical edge\n                    if (bridges.count(i) > 0) {\n                        result[0].push_back(i);\n                    }\n                    // pseudo-critical edge\n                    else {\n                        result[1].push_back(i);\n                    }\n                }\n            }\n        }\n        return result;\n    }\nprivate:\n    void dfs(int u, int from, int depth) {\n        vis[u] = true;\n        ancestors[u] = depth;\n        for (int j = 0; j < edges[u].size(); ++j) {\n            int v = edges[u][j][0], i = edges[u][j][1];\n            // the edge from parent to current node\n            if (i == from) {\n                continue;\n            }\n            if (!vis[v]) {\n                dfs(v, i, depth + 1);\n                if (depth < ancestors[v]) {\n                    bridges.insert(i);\n                }\n            }\n            ancestors[u] = min(ancestors[u], ancestors[v]);\n        }\n    }\n};\n\nclass Solution {\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> result(2, vector<int>());\n        UnionFind components(n);\n        \n        for (int i = 0; i < edges.size(); ++i) {\n            edges[i].push_back(i);\n        }\n        sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[2] < b[2];\n        });\n        \n        for (int l = 0, r = 0; l < edges.size(); l = r) {\n            // edges with indices in [l, r) have the same weight\n            while (r < edges.size() && edges[l][2] == edges[r][2]) {\n                ++r;\n            }\n            \n            // shrink components into nodes, and run Tarjan\'s bridge-finding algorithm on the new graph\n            // critical edges will be bridges and pseudo-critical edges will be the rest\n            // non-critical edges will not appear in the new graph\n            vector<vector<int>> connections;\n            for (int j = l; j < r; ++j) {\n                int u = components.find(edges[j][0]), v = components.find(edges[j][1]), i = edges[j][3];\n                if (u != v) {\n                    connections.push_back({u, v, i});\n                }\n            }\n            vector<vector<int>> subResult = TarjanSolver(connections).solve();\n            result[0].insert(result[0].end(), subResult[0].begin(), subResult[0].end());\n            result[1].insert(result[1].end(), subResult[1].begin(), subResult[1].end());\n            \n            // kruskal: merge components\n            for (int j = l; j < r; ++j) {\n                int u = components.find(edges[j][0]), v = components.find(edges[j][1]);\n                if (u != v) {\n                    components.merge(u, v);\n                }\n            }\n        }\n        \n        return result;\n    }\n};\n```
[]