python,  union find/bfs/dfs, complexity analysis
Union Find:\n Data sturctures: \n\t  a dictionary to store the tuples of \n\t\t  the infecting node x  : a set containing the community IDs of  good nodes infec
**Union Find:**\n* Data sturctures: \n\t*  a dictionary to store the tuples of \n\t\t*  the infecting node `x`  : a set containing the community IDs of  good nodes infected by `x`.\n\t*  a Counter to store \n\t\t*  each community ID : the times that it is infected by some initial nodes\n* Algorithm:\n\t* Step1: (We want compute connected components (communities) for all \'good\' nodes. If there is an edge between 2 \'good\' nodes, then union/connect them.)\n\t\n\t\t* for u, v in all combinations of good nodes pairs:\n\t\t\t* if there is an edge between u and v\n\t\t\t\t* if the size of set that where u is currently in is larger than that where v in in\n\t\t\t\t\t\t\t- add the size of v to size u\n\t\t\t\t\t\t\t- size v\'s parent become u\n\t\t\t\t* else:\n\t\t\t\t\t\t\t- add the size of u to size v\n\t\t\t\t\t\t\t- size u\'s parent become v\n\t* Step2: bridge/connect the bad nodes to good communities. If there is an edge between a \'bad\' initial node and a good node in a good community, then add the good community ID to that bad node\'s set.\n\t* Step3: \n\t\t* for each bad initial node `x`, \n\t\t\t* for each good community `y`  it infects\n\t\t\t\t* if `y` only can be infected by `x`\n\t\t\t\t\t* add the size of the community `y` to `the number of nodes that can surivive if removed \'x\' `\n\n\n**Compleixity analysis:**\n* Time: O(N^2). Assume in the worst case, there is N good nodes. For each good node, we need to check N^2 edges for union the graph, so the overall complexity is O(N^2). \n* Space: O(N) for `parents`, `size`, and the Counter() and defaultdict(set) data structures.\n\n\n```\nclass Solution:\n    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n        if not graph: return -1\n        N = len(graph)\n        clean = set(range(N)) - set(initial)\n        parents = list(range(N))\n        size = [1] * N\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            rx, ry = find(x), find(y)\n            if rx != ry:\n                if size[rx] < size[ry]:\n                    parents[rx] = ry\n                    size[ry] += size[rx]\n                else:\n                    parents[ry] = rx\n                    size[rx] += size[ry]\n        \n\n        for u, v in itertools.combinations(clean, 2):\n            if graph[u][v]: union(u, v)\n         \n        d = collections.defaultdict(set)\n        infectedTimes = collections.Counter()\n        for u in initial:\n            for v in clean:\n                if graph[u][v]: d[u].add(find(v))\n            \n            for comm in d[u]:\n                infectedTimes[comm] += 1\n        \n        count = [0] * N\n        for u, comms in d.items():\n            for comm in comms:\n                if infectedTimes[comm] == 1:\n                    count[u] += size[comm]\n        \n        maxi = max(count)\n        return count.index(maxi) if maxi != 0 else min(initial)   \n```\n\n\n**DFS:**\n\n```\nclass Solution:\n    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n        if not graph: return -1\n        N = len(graph)\n        clean = set(range(N)) - set(initial)\n        \n        def dfs(u, seen):\n            for v, adj in enumerate(graph[u]):\n                if adj and v in clean and v not in seen:\n                    seen.add(v)\n                    dfs(v, seen)\n                    \n        d = collections.defaultdict(list)\n        for u in initial:\n            seen = set()\n            dfs(u, seen)\n            \n            for v in seen:\n                d[v].append(u)\n                \n        count = [0] * N\n        for v, infects in d.items():\n            if len(infects) == 1:\n                count[infects[0]] += 1\n        \n        return count.index(max(count)) if max(count) != 0 else min(initial)\n```\n                    \n**BFS:**\n\n```\nclass Solution:\n    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n        if not graph: return -1\n        N = len(graph)\n        clean = set(range(N)) - set(initial)\n        d = collections.defaultdict(list)\n\n        for u in initial:\n            Q = collections.deque([u])\n            seen = set(initial)\n            while Q:\n                infect = Q.popleft()\n                for v, adj in enumerate(graph[infect]):\n                    if adj and v not in seen and v in clean:\n                        seen.add(v)\n                        Q.append(v)\n                        d[v].append(u)\n        \n        count = [0] * N\n        for v, infects in d.items():\n            if len(infects) == 1:\n                count[infects[0]] += 1\n        maxi = max(count)\n        return count.index(maxi) if maxi != 0 else min(initial)\n```\n                \n                \n
[]