Python 80ms 100% faster, building MST only once, with descriptions
From the CRLS textbook, the edge list L of MST should be the same, even if you have more than 1 MST.  In combination with Kruskal\'s, this means the edges that 
From the CRLS textbook, the edge list L of MST should be the same, even if you have more than 1 MST.  In combination with Kruskal\'s, this means the edges that were given up because of cycles are noncritical edges if the cycle also contains another edge with the same weight. \nIn other words, these noncritical-equal-weight edges only get selected/discarded w.r.t MST because of their order in the sorting of edges; if their ordering in the sort are interchangeable due to being equaal in weight so is their status to the MST. \n\n\'\'\'\nclass Solution(object):\n    nonCritical = list()\n    def findCriticalAndPseudoCriticalEdges(self, n, edges):\n        """\n        :type n: int\n        :type edges: List[List[int]]\n        :rtype: List[List[int]]\n        """  \n        \n        rank = [1] * n \n        parent = [i for i in range(n)]\n        critical = list()\n        noncritical = list()\n        mst = list()\n        adj = [[] for i in range(n)]\n        \n        def find(i):\n            if parent[i] == i:\n                return i\n            parent[i] = find(parent[i])  # this will eventually set root to be parent[i]\n            return parent[i]\n    \n        def union(pu, pv):\n            if rank[pu] > rank[pv]:\n                parent[pv] = pu\n            elif rank[pu] < rank[pv]:\n                parent[pu] = pv\n            else:\n                parent[pv] = pu\n                rank[pv] += 1\n    \n        def dfsPath(adj, nodeweight, v, stack, vis):\n            u = nodeweight[0]\n            vis[u] = 1\n            stack.append(nodeweight)\n            if u == v:\n                return True\n            for child in adj[u]:\n                if not vis[child[0]]:\n                    if dfsPath(adj, child, v, stack, vis):\n                        return True\n            stack.pop(-1)\n        \n        edges = [(u, v, w, i) for i, (u,v,w) in enumerate(edges)]\n        edges.sort(key = lambda x: x[2])\n        e = len(edges)\n        count = 0\n        i = 0\n        #Kruskal\'s\n        while i < e:\n            if count == n-1 and edges[i][2] > curr: \n                # if mst is complete and the rest edges have lengths greater than all tree edges\n                break\n            (u, v, w, ind) = edges[i]\n            urep = find(u)\n            vrep = find(v)\n            if urep != vrep: # we can safely add this edge\n                adj[u].append((v, w, ind))\n                adj[v].append((u, w, ind))\n                mst.append(ind)\n                curr = w\n                count += 1\n                union(urep, vrep)\n            else:# adding this edge would form a cycle; \n                 # this edge would either be equal to or greater than the last added MST edge\n                if curr == w :\n                    # check to see whether the cycle contains another edge with the same weight\n                    stack = list()\n                    vis = [0] * n\n                    dfsPath(adj, (u,0,n) , v, stack, vis) # find path in mst from u to v\n                    # stack should contain ending node and edge weights and inds \n                    # the (v, w, ind) from (u, v, w, ind) starting situation (u, u, 0, n) \n                    for halfEdge in stack:\n                        if halfEdge[1] == w:# if path has edges with same weight as the one not being added\n                            if halfEdge[2] not in noncritical: # then those edges are noncritical\n                                noncritical.append(halfEdge[2]) \n                            if ind not in noncritical: # the edge (u, v, w, ind) can replace be replaced by those edges, \n                                noncritical.append(ind)        \n            i+= 1\n        for i in mst:\n            if i not in noncritical:\n                critical.append(i)\n        return [critical, noncritical]\n\'\'\'
['Python']