Python: O(E log E) Without Using Kruskal's Algorithm
Intuition\n Describe your first thoughts on how to solve this problem. \n1. The minimum edge is in the MST\n2. If we remove the minimum edge by collapsing it in
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n1. The minimum edge is in the MST\n2. If we remove the minimum edge by collapsing it into a point, the MST of the subgraph that remains is a subgraph of the original MST\n3. The distinction between pseudo-critical edges and critical edges of the same weight is that pseudo-critical edges form a cycle\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirst, we sort the edges to get them in ascending order, then we take them in groups of the same weight. All of these edges are going to be either critical or pseudo-critical because they are minimum edges (observation 1). Any edge that is self-referential due to future edge collpasing is passed over. \n\nSecond, we leverage observation 3 and find which of these edges form a cycle. I just used a simple backtracking DFS to search for cycles. Any edge that is in a cycle is marked as pseudo-critical and all others are marked as critical. \n\nThird, any edge that we just searched is now collapsed into a point (observation 2). We use the node_map to keep track of which elements point where, and we have to be careful about updating it. Due to how all vertices will be pushed into a single point, we need to loop through all (k, v) pairs in the node_map to update everything correctly. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(E\\ log\\ E)$$: Edges are sorted once, then each edge is iterated over once\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(E+V)$$: Edges are stored in intermediate arrays, vertices get one entry into the node_map\n\n# Code\n```\nimport itertools\nimport collections\n\nclass Solution:\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        # Observations:\n        # The minimum edge is in the MST\n        # In any non-empty set of pseudo-critical edges, there exists a non-empty set of edges that forms a cycle\n\n        edges = [(edge[0], edge[1], i, edge[2]) for i, edge in enumerate(edges)]\n        edges.sort(key=lambda x: x[3])\n        grouped_edges = itertools.groupby(edges, key=lambda x:x[3])\n        node_map = {x: x for x in range(n)}\n\n        critical = []\n        psuedo_critical = []\n\n        edges = 0\n\n        for _, edge_group in grouped_edges:\n            # Take the minimum edges that have not become self-loops\n            possible_edges = collections.defaultdict(set)\n            for edge in list(edge_group):\n                mapped_edges = (node_map[edge[0]], node_map[edge[1]])\n                if mapped_edges[0] != mapped_edges[1]:\n                    possible_edges[mapped_edges].add(edge[2])\n\n            # From these, the edges are critical if they are not in a loop, and psuedo-critical if they are\n            adj_matrix = collections.defaultdict(collections.Counter)\n            for v1, v2 in possible_edges:\n                count = len(possible_edges[(v1, v2)])\n                adj_matrix[v1][v2] += count\n                adj_matrix[v2][v1] += count \n\n            in_cycle = self.find_edges_in_cycle(adj_matrix)\n            for edge in possible_edges:\n                if edge in in_cycle or edge[::-1] in in_cycle:\n                    psuedo_critical.extend(possible_edges[edge])\n                else:\n                    critical.extend(possible_edges[edge])\n\n            # Finally, collapse each edge\n            for v1, v2 in possible_edges:\n                target = node_map[v1]\n                change = node_map[v2]\n                for key in node_map:\n                    if node_map[key] == change:\n                        node_map[key] = target\n\n        return critical, psuedo_critical\n\n    def find_edges_in_cycle(self, adj_matrix) -> set:\n        if len(adj_matrix) == 0:\n            return set()\n\n        in_cycle = set()\n        seen = set()\n        visited = list()\n\n        def backtrack(vertex):\n            visited.append(vertex)\n            seen.add(vertex)\n\n            for next_vertex in adj_matrix[vertex]:\n                if adj_matrix[vertex][next_vertex] < 1:\n                    continue\n\n                found = False\n\n                for i, elem in enumerate(visited):\n                    if elem == next_vertex:\n                        found = True\n\n                        # Find the edges forming this cycle\n                        prev = elem\n                        for elem2 in visited[i+1:]:\n                            edge = (prev, elem2)\n                            in_cycle.add(edge)\n                            prev = elem2\n                        in_cycle.add((prev, elem))\n\n                        break\n\n                adj_matrix[next_vertex][vertex] -= 1\n\n                if not found and next_vertex not in seen:\n                    backtrack(next_vertex)\n\n                adj_matrix[next_vertex][vertex] += 1\n\n            visited.pop()\n\n        for vertex in adj_matrix:\n            if vertex not in seen:\n                backtrack(vertex)\n\n        return in_cycle\n```
['Python3']