O(ElogE), Kruskal+Tarjan
First we have some observations:\n\t1. Any edge with the minimum weight must belong to at least one MST\n\t2. In Kruskal algorithm, after processing those edges
First we have some observations:\n\t1. Any edge with the minimum weight must belong to at least one MST\n\t2. In Kruskal algorithm, after processing those edges with the same minimum weight, the Union of vertices is independent of the choice of the edges, thus the rest part of the algorithm is unaffected\n\t3. The edges with minimum weight form a subgraph, and the bridges of it are critical edges, while the other are pseudo-critical edges\n\t4. Those ignored edges in Kruskal (with two ends already connected) are not critital or pseudo-critical\nUsing these observations we have an algorithm:\n\t1. Sort and group edges by weight. In each step we process one group of edges\n\t2. Discard the edges whose ends are already connected\n\t3. Run Tarjan\'s bridge finding algorithm on each connnected part of the subgraph. Add bridges to critical and the rest to pseudo-critical\n\t4. Use union-find to connect the edges\' two ends.\nSorting takes O(ElogE) time and Tarjan takes O(V\'+E\') time. Since we will only process any edge once and that after one step, the number of independent vertices shrinks by at least V\'/2 (connected parts will be reduced to one vertice), the total time cost of Tarjan is O(V+E). Thus the overall time complexity is O(ElogE).\nIn the contest, however, I used some brute-force method instead of union-find and tarjan to save coding time, but also get accepted thanks to the weak data cases. It\'s possible to solve V,E~10^5 with the optimal algorithm.\n```\nclass Solution:\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        edges=[x+[i] for i,x in enumerate(edges)]\n        ce,pce=set(),set()\n        while any([e[0]!=e[1] for e in edges]):\n            temp=min([e[2] for e in edges])\n            s=[e for e in edges if e[2]==temp]\n            for i in range(len(s)):\n                temp2=[x[:] for x in s]\n                for j in range(len(s)):\n                    if i!=j:\n                        f,t,w,id=temp2[j]\n                        for e in temp2:\n                            if e[0]==t:\n                                e[0]=f\n                            if e[1]==t:\n                                e[1]=f\n                if temp2[i][0]==temp2[i][1]:\n                    pce.add(temp2[i][3])\n                else:\n                    ce.add(temp2[i][3])\n            for f,t,w,i in s:\n                for e in edges:\n                    if e[0]==t:\n                        e[0]=f\n                    if e[1]==t:\n                        e[1]=f\n            edges=[e for e in edges if e[2]!=temp and e[0]!=e[1]]\n        return [list(ce),list(pce)]\n```\nThe code above is O(E^3) or higher, and I may update it to optimal when I have time.
[]