Minimize Malware Spread II

Problem Id: 928 Difficulty: Hard


Intuition

Solution


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        visited = [False] * len(graph)
        ans = 0
        count = len(graph)
        initial.sort()
        for node in initial:
            tmp = 0
            visited = [False] * len(graph)
            visited[node] = True
            for start in initial:
                tmp += self.dfs(start, visited, graph)
            if tmp < count:
                ans = node
                count = tmp
        return ans

    def dfs(self, node, visited, graph):
        if visited[node]:
            return 0
        visited[node] = True
        count = 1
        for n in range(len(graph)):
            if not graph[node][n]:
                continue
            count += self.dfs(n, visited, graph)
        return count