Python Union/Find (Easy to Understand)
\n# Approach\n1. Create disjoint set for non-infected nodes\n2. Find the groups where current malware node is infecting.\nTry to find the malware source count i
\n# Approach\n1. Create disjoint set for non-infected nodes\n2. Find the groups where current malware node is infecting.\nTry to find the malware source count in each group\n3. Now for each malware node, check if it will infect the connected\ngroup. To check, find whether the group has only one malware source.\nFind the safe nodes count.\n4. Return the one with max safe nodes count.\n\n# Code\n```\nclass DisjointSet:\n    def __init__(self, n):\n        self.parent = [i for i in range(n)]\n        self.rank = [1 for i in range(n)]\n    \n    def get_parent(self, node):\n        if node == self.parent[node]:\n            return node\n        self.parent[node] = self.get_parent(self.parent[node])\n        return self.parent[node]\n\n    def union(self, node1, node2):\n        parent_1, parent_2 = self.get_parent(node1), self.get_parent(node2)\n        if parent_1 == parent_2:\n            return\n        \n        if self.rank[parent_1] >= self.rank[parent_2]:\n            self.parent[parent_2] = parent_1\n            self.rank[parent_1] += self.rank[parent_2]\n        else:\n            self.parent[parent_1] = parent_2\n            self.rank[parent_2] += self.rank[parent_1]\n    \n    def get_component_size(self, node):\n        return self.rank[self.get_parent(node)]\n\nclass Solution:\n    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n        n = len(graph)\n        infected_nodes = set(initial)\n        disjoint_set = DisjointSet(n)\n        for i in range(n):\n            if i not in infected_nodes:\n                for j in range(n):\n                    if graph[i][j] == 1 and j not in infected_nodes and i != j:\n                        disjoint_set.union(i, j)\n        \n        malware_group_infecting_map = defaultdict(set)\n        group_malware_source_count = defaultdict(int)\n\n        for node in infected_nodes:\n            for i in range(n):\n                if i != node and graph[node][i] == 1 and i not in infected_nodes:\n                    parent_node = disjoint_set.get_parent(i)\n                    if parent_node not in malware_group_infecting_map[node]:\n                        malware_group_infecting_map[node].add(parent_node)\n                        group_malware_source_count[parent_node] += 1\n        \n        max_safe_node_count = -1\n        ans = -1\n        for node in infected_nodes:\n            safe_node_count = 0\n            for parent_node in malware_group_infecting_map[node]:\n                if group_malware_source_count[parent_node] == 1:\n                    safe_node_count += disjoint_set.get_component_size(parent_node)\n            if safe_node_count > max_safe_node_count:\n                max_safe_node_count = safe_node_count\n                ans = node\n            elif safe_node_count == max_safe_node_count:\n                ans = min(ans, node)\n\n        return ans\n\n\n        \n```
['Union Find', 'Graph', 'Python3']