<p>You are given a network of <code>n</code> nodes represented as an <code>n x n</code> adjacency matrix <code>graph</code>, where the <code>i<sup>th</sup></code> node is directly connected to the <code>j<sup>th</sup></code> node if <code>graph[i][j] == 1</code>.</p>

<p>Some nodes <code>initial</code> are initially infected by malware. Whenever two nodes are directly connected, and at least one of those two nodes is infected by malware, both nodes will be infected by malware. This spread of malware will continue until no more nodes can be infected in this manner.</p>

<p>Suppose <code>M(initial)</code> is the final number of nodes infected with malware in the entire network after the spread of malware stops.</p>

<p>We will remove <strong>exactly one node</strong> from <code>initial</code>, <strong>completely removing it and any connections from this node to any other node</strong>.</p>

<p>Return the node that, if removed, would minimize <code>M(initial)</code>. If multiple nodes could be removed to minimize <code>M(initial)</code>, return such a node with <strong>the smallest index</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
<strong>Output:</strong> 0
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
<strong>Output:</strong> 1
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
<strong>Output:</strong> 1
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == graph.length</code></li>
	<li><code>n == graph[i].length</code></li>
	<li><code>2 &lt;= n &lt;= 300</code></li>
	<li><code>graph[i][j]</code> is <code>0</code> or <code>1</code>.</li>
	<li><code>graph[i][j] == graph[j][i]</code></li>
	<li><code>graph[i][i] == 1</code></li>
	<li><code>1 &lt;= initial.length &lt;&nbsp;n</code></li>
	<li><code>0 &lt;= initial[i] &lt;= n - 1</code></li>
	<li>All the integers in <code>initial</code> are <strong>unique</strong>.</li>
</ul>

# class Solution:
#     def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:

#         def build_maps(original_graph,remove_index):
#             maps = defaultdict(list) 
#             for node_i, connections in enumerate(graph):
#                 if node_i == remove_index:
#                     pass
#                 else: 
#                     for other_node_j, connection in enumerate(connections):
#                         if connection == 1 and other_node_j != node_i and other_node_j != remove_index:
#                             maps[node_i].append(other_node_j)
#             return maps  

#         def bfs(starts,maps):
#             num_malware = 0 
#             queue = deque()
#             visited = set()  
#             queue.extend(starts)
#             num_malware += len(starts)
#             for start in starts:
#                 visited.add(start)
#             while queue:
#                 l = len(queue)
#                 for _ in range(l):
#                     node = queue.popleft()
#                     for neighbor in maps[node]:
#                         if neighbor not in visited:
#                             visited.add(neighbor)
#                             queue.extend([neighbor])
#                             num_malware += 1
#             return num_malware

#         after_remove_malware = []
#         initial.sort()
#         minimum = math.inf  
#         index = 100
#         for remove_node in initial:
#             remaining = initial.copy()
#             remaining.remove(remove_node)
#             current_map = build_maps(graph, remove_node)
#             current_mal = bfs(remaining,current_map)
#             if  current_mal < minimum:
#                 index = remove_node
#                 minimum = current_mal
#         return index

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        adj = defaultdict(set)
        n = len(graph)
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if graph[i][j]:
                    adj[i].add(j)
                    adj[j].add(i)
        mal = set(initial)
        best = -1
        def dfs(src):
            if src in visit:
                return 0 
            visit.add(src)
            path.add(src)
            res = 1
            if src in initial:
                res = -1
            for nei in adj[src]:
                res += dfs(nei)
            return res
        initial.sort()
        index = initial[0]
        for i in initial:
            visit = set([i])
            save = 0
            visit.add(i)
            for nei in adj[i]:
                path = set()
                sub = dfs(nei)
                save += sub if sub == len(path) else 0
            if save > best:
                best = save
                index = i
        return index
       

        
19900