Prim's algo (python)
Intuition\n Describe your first thoughts on how to solve this problem. \nPrim\'s algo\n# Approach\n Describe your approach to solving the problem. \n\n# Complex
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nPrim\'s algo\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\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        def prim(edges, forced_edge=None):\n            visited = [False] * n\n            edge_list = [[] for _ in range(n)]\n            for i, (u, v, w) in enumerate(edges):\n                edge_list[u].append((v, w, i))\n                edge_list[v].append((u, w, i))\n\n            weight = 0\n            pq = []\n\n            if forced_edge is not None:\n                u, v, w = edges[forced_edge]\n                visited[u] = True\n                visited[v] = True\n                weight += w\n                for nxt, w, idx in edge_list[u]:\n                    heapq.heappush(pq, (w, nxt, idx))\n                for nxt, w, idx in edge_list[v]:\n                    heapq.heappush(pq, (w, nxt, idx))\n            else:\n                heapq.heappush(pq, (0, 0, -1))\n\n            while pq:\n                w, v, idx = heapq.heappop(pq)\n                if not visited[v]:\n                    visited[v] = True\n                    weight += w\n                    for nxt, nxt_w, nxt_idx in edge_list[v]:\n                        if not visited[nxt]:\n                            heapq.heappush(pq, (nxt_w, nxt, nxt_idx))\n\n            if sum(visited) != n:  # Not all vertices were visited\n                return float(\'inf\')\n\n            return weight\n\n        # Find the weight of the original MST\n        mst_weight = prim(edges)\n\n        criticals, pseudo_criticals = [], []\n\n        # Check for critical edges\n        for i in range(len(edges)):\n            new_weight = prim(edges[:i] + edges[i+1:])\n            if new_weight > mst_weight:\n                criticals.append(i)\n\n        # Check for pseudo-critical edges\n        for i in range(len(edges)):\n            if i not in criticals:\n                new_weight = prim(edges, i)\n                if new_weight == mst_weight:\n                    pseudo_criticals.append(i)\n\n        return [criticals, pseudo_criticals]\n\n```
['Python3']