[Python] MST with Kruskal's Algorithm - Standard code - Clean & Concise
Idea\n- Firstly, run the MST algorithm to find the total weight of Minimum Spanning Tree of the graph.\n- To find if one edge is critical, delete that edge and 
**Idea**\n- Firstly, run the MST algorithm to find the **total weight of Minimum Spanning Tree** of the graph.\n- To find **if one edge is critical**, **delete that edge** and **re-run the MST** algorithm and see **if the weight of the new MST increases**.\n- To find **if a non-critical edge is speudo-critical**, **include that edge** and **re-run the MST** algorithm and see **if the weight of the new MST the same**.\n- Since we only **interactive with edges** of the MST, so **Kruskal\'s Algorithm is a best fit** to solve this problem.\n```python\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = [i for i in range(n)]\n        self.rank = [1] * n\n\n    def find(self, u):\n        if u != self.parent[u]:\n            self.parent[u] = self.find(self.parent[u])\n        return self.parent[u]\n\n    def union(self, u, v):\n        pu, pv = self.find(u), self.find(v)\n        if pu == pv: return False\n        if self.rank[pu] < self.rank[pv]:\n            self.parent[pu] = self.parent[pv]\n        elif self.rank[pu] > self.rank[pv]:\n            self.parent[pv] = self.parent[pu]\n        else:\n            self.rank[pu] += 1\n            self.parent[pv] = pu\n        return True\n\n\nclass Solution:\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        edges = [[u, v, w, i] for i, [u, v, w] in enumerate(edges)]  # Add original indices of edge to edges array\n        edges.sort(key=lambda x: x[2])  # Sort in increasing order of weight\n\n        # O(E)\n        def kruskal(n, edges, bannedIdx, includeIdx):\n            uf = UnionFind(n)\n            totalWeight = 0\n            if includeIdx != -1:\n                u, v, w, _ = edges[includeIdx]\n                uf.union(u, v)\n                totalWeight += w\n                n -= 1\n\n            for i, (u, v, weight, _) in enumerate(edges):\n                if i == bannedIdx: continue\n                if uf.union(u, v):\n                    totalWeight += weight\n                    n -= 1\n                if n == 1: break  # A bit optimize since we found enough n-1 edges\n            return math.inf if n > 1 else totalWeight\n\n        criticalEdges = []\n        mstWeight = kruskal(n, edges, -1, -1)\n        for i in range(len(edges)):  # O(E * E)\n            totalWeight = kruskal(n, edges, i, -1)\n            if totalWeight > mstWeight:  # the mst increasing -> ith edge is critical\n                criticalEdges.append(edges[i][3])  # add original index\n\n        pseudoCriticalEdges = []\n        for i in range(len(edges)):  # O(E * E)\n            if edges[i][3] in criticalEdges: continue  # We only care non-critical edges\n            totalWeight = kruskal(n, edges, -1, i)\n            if totalWeight == mstWeight:  # the mst the same -> ith edge is pseudo-critical\n                pseudoCriticalEdges.append(edges[i][3])  # add original index\n\n        return [criticalEdges, pseudoCriticalEdges]\n```\n**Complexity**\n- Time: `O(E * E)`, where `V <= 100` is number of vertices, `E <= min(200, V*(V-1)/2)` is number of edges.\n- Space: `O(E + V)`
[]