Python Union Find /w explaination(little)
Similar to 924, but with a slight twist, solution for 924: https://leetcode.com/problems/minimize-malware-spread/discuss/2120247/python-union-find-w-explainatio
Similar to 924, but with a slight twist, solution for 924: https://leetcode.com/problems/minimize-malware-spread/discuss/2120247/python-union-find-w-explainationlittle\n```\nclass Solution:\n    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n        n = len(graph)\n\n        parents = list(range(n))\n        sizes = [1 for _ in range(n)]\n        def find(x):\n            if parents[x] != x:\n                parents[x] = find(parents[x])\n            return parents[x]\n        \n        def union(x, y):\n            px, py = parents[x], parents[y]\n            if px < py:\n                parents[py] = px\n                sizes[px] += sizes[py] \n            elif px > py:\n                parents[px] = py\n                sizes[py] += sizes[px]\n        \n        # join clean nodes\n        for i in range(n):\n            if i not in initial:\n                for j in range(i+1, n):\n                    if j not in initial and graph[i][j] == 1:\n                        union(i, j)\n        \n        \n        # for each initial node, find out component they connected\n        dict_intial_to_component = defaultdict(set)\n        # keep record of the number of initial node each component connect to\n        dict_component_to_initial = defaultdict(int)\n        for i in initial:\n            for j in range(n):\n                if j not in initial and graph[i][j] == 1:\n                    root = find(j)\n                    dict_intial_to_component[i].add(root)\n                        \n        for i in dict_intial_to_component:\n            for componenet in dict_intial_to_component[i]:\n                dict_component_to_initial[componenet] += 1\n        \n        # select candidate, \n        # for each initial node, figure our how many commonent only connect to it.\n\t\t# for each intial node, calculate the score of each corresponding connected component, if one component connect to multiple initial node, we can not improve it by removing one node.\n\t\t#  the score of each component is the number of clean node in the component\n        ans = 0, min(initial)\n        for i in initial:\n            score = 0\n            for component in dict_intial_to_component[i]:\n                if dict_component_to_initial[component] == 1:\n                    score += sizes[component]\n            if score > ans[0]:\n                ans = score, i\n            elif score == ans[0] and i < ans[1]:\n                ans = score, i\n        return ans[1]\n```
[]