[Python] UnionFind+Kruskal check double
Imagine getting all MSTs. That is very huge.\nSo change the problem. If we have to use or don\'t use a edge, can we make a MST?\n\nIf we do not use a edge and M
Imagine getting all MSTs. That is very huge.\nSo change the problem. If we have to use or don\'t use a edge, can we make a MST?\n\nIf we do not use a edge and MST value is incresed, that edge is critical edge.\nBecause we cannot create good MST without this edge. \nIt means all good MST use this edge.\nSo this edge is critical edge.\n\nIf we always use a edge and MST value is not changed, that edge is presudo-criticla edge. \nBecause we can create good MST including this edge. \nIt means at least one MST use this edge. So this edge is presudo-critical edge.\n\nThe time complextiy is `O(ElogE + E^2 + E^2)`.\nUnion-Find time complexity is almost `O(N)`.\n\n```python\nfrom typing import Dict, List\nfrom collections import deque, defaultdict, OrderedDict, Counter\nfrom heapq import heapify, heappush, heappop\nfrom bisect import bisect_left, bisect_right\nfrom functools import lru_cache\nfrom itertools import combinations, permutations, groupby\nfrom math import gcd\nimport re\nimport sys\ninf = float(\'inf\')\nsys.setrecursionlimit(10**9)\nMOD = 10**9+7\n\n\nclass UnionFind:\n    def __init__(self, n):\n        self.par = [i for i in range(n)]\n\n    def find(self, a):\n        if self.par[a] == a:\n            return a\n        self.par[a] = self.find(self.par[a])\n        return self.par[a]\n\n    def union(self, a, b):\n        a, b = self.find(a), self.find(b)\n        if a > b:\n            a, b = b, a\n        if a == b:\n            return False\n        self.par[b] = a\n        return True\n\n\nclass Solution:\n    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n        # save the edge id\n        edges = [(u, v, w, i) for i, (u, v, w) in enumerate(edges)]\n        edges.sort(key=lambda x: x[2])\n\n        # Do not use this edge\n        def find_mst_not_use_this_edge(not_use):\n            unionFind = UnionFind(n)\n            res = 0\n            for i, (u, v, w, _) in enumerate(edges):\n                # do not use this edge\n                if i == not_use:\n                    continue\n                if unionFind.union(u, v) == True:\n                    res += w\n\n            return res if all(unionFind.find(i) == 0 for i in range(n)) else inf\n\n        # Need to use this edge\n        def find_mst_need_use_this_edge(need_use):\n            # use this edge first\n            unionFind = UnionFind(n)\n            res = edges[need_use][2]\n            unionFind.union(edges[need_use][0], edges[need_use][1])\n            # And then create mst\n            for i, (u, v, w, _) in enumerate(edges):\n\t\t\t\t# alread use this edge\n                if i == need_use:\n                    continue\n                if unionFind.union(u, v) == True:\n                    res += w\n\n            return res if all(unionFind.find(i) == 0 for i in range(n)) else inf\n        # Normal MST value\n        base = find_mst_not_use_this_edge(-1)\n        cri = []\n        p_cri = []\n        for i in range(len(edges)):\n            v = find_mst_not_use_this_edge(i)\n            # If MST value is increased, it means all MST use this edge.\n            if v != base:\n                cri.append(edges[i][3])\n            else:\n                v = find_mst_need_use_this_edge(i)\n                # If MST value is not changed, it means at least one MST which use this edge exists\n                if v == base:\n                    p_cri.append(edges[i][3])\n\n        return [cri, p_cri]\n\n\n\n```
[]