Python: Simple and Elegant, Prim's (20lines)
Intuition\n1. Calculate the cost of the Minimum Spanning Tree (MST) as $C$.\n2. For each edge, compute the cost if excluded, denoted as $C_e$, and the cost if i
# Intuition\n1. Calculate the cost of the Minimum Spanning Tree (MST) as $C$.\n2. For each edge, compute the cost if excluded, denoted as $C_e$, and the cost if included, denoted as $C_i$.\n3. An edge is considered critical if $C_e > C$, and pseudo-critical if $C_e = C = C_i$.\n\n# Complexity\n- Time complexity:\n$$O(E^2 logV)$$\n\n- Space complexity:\n$$O(E)$$\n\n# Code\n```\nclass Solution:\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        edges = [(a, b, c, i) for i, (a, b, c) in enumerate(edges)]\n        edges.sort(key = lambda x: x[2])\n        maxCost = 1000 * 100\n\n        def getMSTCost(E, V, C):\n            \'\'\' \n                E: edge exclusive set\n                V: nodes in MST\n                C: current Cost\n            \'\'\'\n            nonlocal edges, n, maxCost\n            if len(V) == n:\n                return C\n            else:\n                for a, b, c, i in edges:\n                    if i not in E and (a in V and b not in V or a not in V and b in V):\n                        return getMSTCost(E | set([i]), V | set([a, b]), C + c)\n            return maxCost\n        \n        C = getMSTCost(set(), set([0]), 0)\n\n        critical, pseudo_critical = [], []\n        for a, b, c, i in edges:\n            if getMSTCost(set([i]), set([0]), 0) > C:\n                critical += [i]\n            elif getMSTCost(set([i]), set([a, b]), c) == C:\n                pseudo_critical += [i]\n\n        return [critical, pseudo_critical]\n```\n\nNote that this impl is not optimized.
['Python3']