One MST | O(EV), 93% TC | Prim + DFS | Easy-to-Understand Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst we build an MST. For each edge (u, v) not in the MST, we check if it can replace 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst we build an MST. For each edge $$(u, v)$$ **not** in the MST, we check if it can replace any edges in the tree. If so, this edge and the relpaceable edge in the tree are both `pseudo-critical`.\n\nTo check if it\'s replaceable, we find a path from $$u$$ to $$v$$ **in the MST**. The weight of every edge along the path should be **smaller than** or **equal to** the weight of $$(u, v)$$ as per MST\'s definition. And, **equal-to** means this edge is replaceable by $$(u, v)$$, which is equivalent to `pseudo-critical`.\n\nIn the end, any edge in the MST that is not `pseudo-critical`, is `critical`. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Build a connection map `conn` for the graph.\n2. Use regular Prim\'s algorithm to find an MST. Build a connection map `mst` for the MST, and records the edge indices of the MST in `mstEdge`.\n3. For every edge $$(u, v)$$ not in the MST, find a path from $$u$$ to $$v$$ in the MST using DFS. Check whether any edge along the path has the same weight with $$(u, v)$$. If any, add them to the `pseudo` set.\n4. DFS in the MST to find the path from $$u$$ to $$v$$.\n5. Exclude the `pseudo` edges from the `mstEdge`, which remains `critical` edges.\n\nNote:\n    1. The code can be further improved in many ways, both in time and in space.\n    2. Either Prim or Kruskal can be used to build the MST, but since the MST is only built once, Prim is a better choice.\n    3. Performance: 93 ms, 93% time, 50% memory in Python3.\n\n# Complexity\n- Time complexity: $$O(E\\log E + EV - V^2 + E) \\sim O(EV)$$:\n    1.  $$O(E)$$ for building map.\n    2.  $$O(E\\log E)$$ for Prim\'s algorithm.\n    3.  Check $$O(E-V)$$ edges, each costs $$O(V)$$.\n    4.  $$O(V)$$ for DFS in the MST.\n    5.  $$O(E)$$ for set exclusion.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(E+V)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n\n        # 1. Build a connection map of the graph\n        conn = [[] for _ in range(n)]\n        for i, edge in enumerate(edges):\n            conn[edge[0]].append((edge[2], edge[1], edge[0], i))\n            conn[edge[1]].append((edge[2], edge[0], edge[1], i))\n\n        # 2. Regular Prim\'s MST algoithm\n        #    `mst`      : a connection map of the MST\n        #    `mstEdge`  : indices of edges in the MST\n        mst, mstEdge = [[] for _ in range(n)], []\n        heap, visited = conn[0], set([0])\n        heapify(heap)\n        while len(visited) < n:\n            weight, node, prev, ind = heappop(heap)\n            if node not in visited:\n                visited.add(node)\n                for item in conn[node]:\n                    if item[1] not in visited:\n                        heappush(heap, item)\n                \n                # build a connection map for the MST\n                mst[node].append((prev, ind))\n                mst[prev].append((node, ind))\n                mstEdge.append(ind)\n\n        # 4. Find the path from u to v in the MST using DFS.\n        def dfs(node: int) -> bool:\n            for next, ind in mst[node]:\n                if path and ind == path[-1]:\n                    # skip the parent\n                    continue\n                path.append(ind)\n                if next == dst or dfs(next):\n                    # path found\n                    return True\n                path.pop()\n            return False\n        \n        # 3. Check every edge (u, v) NOT in the MST, see if it can replace any of\n        #    the edges on the MST. Use DFS to find a path IN THE MST from u to v.\n        #    Any edge along the path that has the same weight of (u, v) can be\n        #    replaced by (u, v), which means both of them are pseudo-critical.\n        pseudo, mstEdge = set(), set(mstEdge)\n        for ind in range(len(edges)):\n            if ind in mstEdge:\n                # skip the mst edges\n                continue\n\n            # find a path from u to v in the MST\n            path, dst = [], edges[ind][1]\n            dfs(edges[ind][0])\n\n            # check edges along the path\n            for i in path:\n                if edges[i][2] == edges[ind][2]:\n                    pseudo.add(i)\n                    pseudo.add(ind)\n\n        # 5. Any edge in the MST that is not pseudo-critial, is critical.\n        return [list(mstEdge - pseudo), list(pseudo)]\n```
['Depth-First Search', 'Graph', 'Heap (Priority Queue)', 'Minimum Spanning Tree', 'Python', 'Python3']