[Python] DFS Solution- O(n ^ 2) => The cost of adjacency matrix
Intuition\n Describe your first thoughts on how to solve this problem. \nWe need to count the nodes which are infected by only one initial node.\nSo traversal f
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe need to count the nodes which are infected by **only one** initial node.\nSo traversal from the initial nodes and stop until it encounter another initial nodes or already visited nodes.\n<br>\nDFS would pass each node once, so the complexcity is every node pass its adjacency array from the adjacency matrix = O(n  ^ 2).\n# Code\nRuntime 793 ms || 94.87%\nMemory 23.5 MB || 5.13%\n```\nclass Solution:\n    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n         # O(n ^ 2) => the cost of adjacency matrix\n        # Three types of node:\n        # -1   -> not visit\n        # i    -> first pass by node i\n        # [0 ~ n-1] -> another infected node\n        n = len(graph)\n        vis = [-1] * n\n        for i in initial:\n            vis[i] = i\n        \n        def dfs(node, cur):\n            vis[node] = cur \n            cnt = 1\n            for i, v in enumerate(graph[node]):\n                if not v:  continue\n                if vis[i] == -1:\n                    cnt += dfs(i, cur)\n                elif vis[i] != cur:\n                    # The set is infected by another node\n                    vis[cur] = n\n            return cnt\n        \n        ans = [-1, -1]\n        for i in initial:\n            count = 0\n            for j, v in enumerate(graph[i]):\n                if not v or vis[j] != -1: \n                    continue\n                # reset\n                vis[i] = i\n                k = dfs(j, i)\n                if vis[i] == i:\n                    count += k\n            if count > ans[1]:\n                ans = [i, count]\n            if count == ans[1]:\n                ans[0] = min(ans[0], i)\n\n        return ans[0]\n```\nMemory optimization:\n\nRuntime: 787 ms || 96.15% \nMemory 18.8 MB || 96.15%\n```\nclass Solution:\n    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:\n        # O(n ^ 2) => the cost of adjacency matrix\n        # Three types of node:\n        # -1   -> not visit\n        # i    -> first pass by node i\n        # [0 ~ n-1] -> another infected node\n        n = len(graph)\n        vis = [-1] * n\n        for i in initial:\n            vis[i] = i\n        \n        ans = [-1, -1]\n        for i in initial:\n            count = 0\n            for j, v in enumerate(graph[i]):\n                if not v or vis[j] != -1: \n                    continue\n                q = [j]\n                vis[i] = vis[j] = i\n                cnt = infected = 0\n                while q:\n                    node = q.pop()\n                    cnt += 1\n                    for nxt, v in enumerate(graph[node]):\n                        if not v:  continue\n                        if vis[nxt] == -1:\n                            q.append(nxt)\n                            vis[nxt] = i\n                        elif vis[nxt] != i:\n                        # The set is infected by another node\n                            infected = 1\n                if not infected:\n                    count += cnt\n            if count > ans[1]:\n                ans = [i, count]\n            if count == ans[1]:\n                ans[0] = min(ans[0], i)\n\n        return ans[0]\n```
['Depth-First Search', 'Python3']