(This problem is the same as Minimize Malware Spread, with the differences bolded.)
In a network of nodes, each node i is directly connected to another node j if and only if graph[i][j] = 1.
Some nodes initial 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.
Suppose M(initial) is the final number of nodes infected with malware in the entire network, after the spread of malware stops.
We will remove one node from the initial list, completely removing it and any connections from this node to any other node.  Return the node that if removed, would minimize M(initial).  If multiple nodes could be removed to minimize M(initial), return such a node with the smallest index.
 



Example 1:
Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0


Example 2:
Input: graph = [[1,1,0],[1,1,1],[0,1,1]], initial = [0,1]
Output: 1


Example 3:
Input: graph = [[1,1,0,0],[1,1,1,0],[0,1,1,1],[0,0,1,1]], initial = [0,1]
Output: 1

 
Note:

1 < graph.length = graph[0].length <= 300
0 <= graph[i][j] == graph[j][i] <= 1
graph[i][i] = 1
1 <= initial.length < graph.length
0 <= initial[i] < graph.length

Difficulty: interview

Starter code:

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

Solutions:
from collections import deque
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:

        
        def bfs(graph, seed, removed):
            queue = deque(seed)
            visited = seed
            
            while len(queue) > 0:
                node = queue.popleft()
                for next_node in range(len(graph[node])):
                    if graph[node][next_node] == 0 or next_node in visited or next_node == removed:
                        continue
                    visited.add(next_node)
                    queue.append(next_node)
            return len(visited)
                        
        best = len(graph)
        best_remove = initial[0]
        initial = set(initial)
        
        for remove_node in initial:
            initial_removed = initial - {remove_node}
            node_result = bfs(graph, initial_removed, remove_node)

            if (node_result < best) or (node_result == best) and (best_remove > remove_node):
                best = node_result
                best_remove = remove_node
        return best_remove


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(i,s):
            if i in visit or (i in ht and i!=s):
                return
            visit.add(i)
            source[i].append(s)
            for j in graph[i]:
                dfs(j,s)
     
        ht=set(initial)
        for i in range(len(graph)):
            tmp=[]  
            for j in range(len(graph[i])):
                if graph[i][j]:
                    tmp.append(j)
            graph[i]=tmp
                
        source=[[] for _ in range(len(graph))]
        for i in initial:
            visit=set()
            dfs(i,i)

        dic=collections.defaultdict(int)
        for i in range(len(source)):
            if len(source[i])==1:
                dic[source[i].pop()]+=1
        res,val=len(graph),0
        for i,cnt in list(dic.items()):
            if cnt>val:
                res,val=i,cnt
            elif cnt==val:
                res=min(res,i)

        return res
                
                
        


import collections
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        numNodes = len(graph)
        minSpread = float('inf')
        minNode = None
        initial.sort()
        
        for i in initial:
            visited = set([i])
            for j in initial:
                self.helper(graph, j, visited)
                        
            if len(visited) < minSpread:
                minSpread = len(visited)
                minNode = i
        
        return minNode
        
    
    def helper(self, graph, curr, visited):
        if curr in visited:
            return
        
        edges = graph[curr]
        visited.add(curr)
        
        for i in range(len(edges)):
            if graph[curr][i] == 1:
                self.helper(graph, i, visited)
                


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        
        
        
        table={}
        
        for i in range(len(graph)):
            table[i] = []
        for i in range(len(graph)):
            for j in range(i+1,len(graph[i])):
                if graph[i][j] ==1:
                    table[i].append(j)
                    table[j].append(i)
        
        
        print(table)
        
        def DFS(n,exclude_node):
            for connect_node in table[n]:
                if connect_node not in self.visited and connect_node != exclude_node:
                    self.visited.append(connect_node)
                    DFS(connect_node,exclude_node)
        
        res=[]
        current_max = 0
        
        
        for node in initial:
            exclude = node
            self.visited=[]
            for i in range(len(initial)):
                
                if initial[i] != exclude:
                    if initial[i] not in self.visited:
                        self.visited.append(initial[i])
                    DFS(initial[i],node)
            left = len(graph)-len(self.visited)
            if left >current_max:
                res = [node]
                current_max = left
            elif left == current_max:
                res.append(node)
            print((node,self.visited))
        
        res.sort()
        print(res)
        return res[0]


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        d = collections.defaultdict(list)
        for init in initial:
            vis = set(initial)
            Q = collections.deque([init])
            while Q:
                infect = Q.popleft()
                for node in range(len(graph[infect])):
                    if graph[infect][node] == 0:
                        continue
                    if node in vis:
                        continue
                    vis.add(node)
                    d[node].append(init)
                    Q.append(node)
        res = [0]*n
        for key in d:
            if len(d[key])==1:
                res[d[key][0]] += 1
        if max(res) == 0: return min(initial)
        return res.index(max(res))


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        index = 0
        count = len(graph)
        initial.sort()
        def search(removed):
            visited =set()
            dfs = []
            for i in initial:
                if i != removed:
                    dfs.append(i)
            while dfs:
                curr = dfs.pop()
                if curr in visited:
                    continue
                visited.add(curr)
                for n,i in enumerate(graph[curr]):
                    if n == removed:
                        continue
                    if i:
                        dfs.append(n)
            return len(visited)
        for i in initial:
            z = search(i)
            if z < count:
                index = i
                count = z
        return index

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        index = 0
        count = len(graph)
        initial.sort()
        def search(removed):
            visited =set()
            dfs = []
            for i in initial:
                if i != removed:
                    dfs.append(i)
            while dfs:
                curr = dfs.pop()
                if curr in visited:
                    continue
                visited.add(curr)
                for n,i in enumerate(graph[curr]):
                    if n == removed:
                        continue
                    if i:
                        dfs.append(n)
            return len(visited)
        for i in initial:
            z = search(i)
            print(i, z)
            if z < count:
                index = i
                count = z
        return index

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        parent = list(range(n))
        size = [1] * n

        def find(u):
            if parent[u] != u:
                parent[u] = find(parent[u])
            return parent[u]

        def union(u, v):
            x, y = find(u), find(v)
            if x != y:
                parent[y] = x
                size[x] += size[y]

        graph = [[v for v, x in enumerate(row) if x and u != v] for u, row in enumerate(graph)]
        infected = [False] * n

        for u in range(n):
            if u in initial:
                infected[u] = True

        for u in range(n):
            if not infected[u]:
                for v in graph[u]:
                    if not infected[v]:
                        union(u, v)

        threat = defaultdict(set)

        for u in range(n): # find infected which threaten uninfected components
            if not infected[u]:
                for v in graph[u]:
                    if infected[v]:
                        threat[find(u)].add(v)

        best = 0
        best_idx = -1

        for v in sorted(initial):   # for each infected
            preventable = set()     # find sum of size of distinct uninfected components threatened by one and only one
            for u in graph[v]:
                if len(threat[find(u)]) == 1:
                    preventable.add(find(u))
            total = 1 + sum(size[u] for u in preventable)
            if total > best:
                best = total
                best_idx = v
        return best_idx


from collections import defaultdict, Counter

class UF:
    def __init__(self, keys):
        self.uf = {}
        for key in keys:
            self.uf[key] = key

    def find(self, x):
        parent = self.uf[x]
        if parent == x:
            return x
        ret = self.find(parent)
        self.uf[x] = ret
        return ret

    def union(self, x, y):
        xx = self.find(x)
        yy = self.find(y)
        self.uf[xx] = yy

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        initial.sort()
        malware = set(initial)
        uf = UF(range(len(graph)))
        neighbors = defaultdict(set)
        for i in range(len(graph)):
            for j in range(len(graph[i])):
                if graph[i][j] == 0:
                    continue
                elif i in malware and j in malware:
                    continue
                elif i in malware:
                    neighbors[i].add(j)
                elif j in malware:
                    neighbors[j].add(i)
                else:
                    uf.union(i, j)
        components = Counter([uf.find(x) for x in range(len(graph)) if x not in malware])
        infected = defaultdict(set)
        incoming = defaultdict(set)
        for key, value in neighbors.items():
            infected[key] = set([uf.find(x) for x in value])
            for component in infected[key]:
                incoming[component].add(key)
        ret = initial[0]
        score = 0
        for mal in initial:
            mal_score = 0
            for component in infected[mal]:
                if len(incoming[component]) == 1:
                    mal_score += components[component]
            if mal_score > score:
                score = mal_score
                ret = mal
        print(components, neighbors, infected, incoming)
        return ret

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(i,s):
            if i in visit or (i in ht and i!=s):
                return
            visit.add(i)
            source[i].append(s)
            for j in graph[i]:
                dfs(j,s)
     
        ht=set(initial)
        for i in range(len(graph)):
            tmp=[]  
            for j in range(len(graph[i])):
                if graph[i][j]:
                    tmp.append(j)
            graph[i]=tmp
                
        source=[[] for _ in range(len(graph))]
        for i in initial:
            visit=set()
            dfs(i,i)

        dic=collections.Counter()
        for i in range(len(source)):
            if len(source[i])==1:
                dic[source[i].pop()]+=1
        res,val=len(graph),0
        for i,cnt in list(dic.items()):
            if cnt>val:
                res,val=i,cnt
            elif cnt==val:
                res=min(res,i)

        return res
                
                
        


class UF:
    def __init__(self, n):
        self.arr = list(range(n + 1))
        self.rank = [1] * (n + 1)
    
    def root(self, x):
        curr = x
        
        while curr != self.arr[curr]:
            curr = self.arr[curr]
        return curr
    
    def union(self, x, y):
        root_x = self.root(x)
        root_y = self.root(y)
        
        rank_x = self.rank[root_x]
        rank_y = self.rank[root_y]
        
        if rank_x >= rank_y:
            self.arr[root_y] = root_x
            self.rank[root_x] += rank_y
        else:
            self.arr[root_x] = root_y
            self.rank[root_y] += rank_x
            
class Solution:
    
    def dfs(self, root, seen, uf, intersection):
        
        for i, v in enumerate(self.graph[root]):
            if v == 0:
                continue
            
            if i in self.init_set:
                if root not in intersection:
                    intersection[root] = []
                intersection[root].append(i)
                continue
                
            uf.union(root, i)
            if i in seen:
                continue
            seen.add(i)
            self.dfs(i, seen, uf, intersection)
        
    
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        self.graph = graph
        self.init_set = set(initial)
        initial.sort()
        
        uf = UF(len(graph[0]))
        seen = set()
        intersection = {}
        for node in range(len(graph[0])):
            if node in self.init_set:
                continue
            
            self.dfs(node, seen, uf, intersection)
        
        islands = {}
        for node in range(len(graph[0])):
            root = uf.root(node)
            if root not in islands:
                islands[root] = set()
            
            if node in intersection:
                for elt in intersection[node]:
                    islands[root].add(elt)
        #print(islands)
        islandCounts = {}
        for node in range(len(graph[0])):
            root = uf.root(node)
            if len(islands[root]) == 1:
                for key in islands[root]:
                    if key not in islandCounts:
                        islandCounts[key] = 1
                    else:
                        islandCounts[key] += 1
        #print(islandCounts)
        if len(islandCounts) == 0:
            return initial[0]
        res = sorted(islandCounts, key = lambda x : (-islandCounts[x], x))
        return res[0]
            


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        conn = collections.defaultdict(set)
        n = len(graph)
        visited = [False] * n
        for i in initial:
            visited[i] = True
            
        def bfs(node):
            q = collections.deque([node])
            v = visited[:]
            while q:
                i = q.popleft()
                for j, k in enumerate(graph[i]):
                    if k and not v[j]:
                        v[j] = True
                        q.append(j)
                        conn[j].add(node)
        for i in initial:
            bfs(i)
        cnt = collections.Counter()
        for k, v in list(conn.items()):
            if len(v) == 1:
                cnt[v.pop()] += 1
        if not cnt:
            return min(initial)
        s = sorted(list(cnt.items()), key=lambda k: (k[1], -k[0]))
        return s[-1][0]


class Solution(object):
    def minMalwareSpread(self, graph, initial):
        N = len(graph)
        clean = set(range(N)) - set(initial)
        def dfs(u, seen):
            for v, adj in enumerate(graph[u]):
                if adj and v in clean and v not in seen:
                    seen.add(v)
                    dfs(v, seen)

        # For each node u in initial, dfs to find
        # 'seen': all nodes not in initial that it can reach.
        infected_by = {v: [] for v in clean}
        for u in initial:
            seen = set()
            dfs(u, seen)

            # For each node v that was seen, u infects v.
            for v in seen:
                infected_by[v].append(u)

        # For each node u in initial, for every v not in initial
        # that is uniquely infected by u, add 1 to the contribution for u.
        contribution = collections.Counter()
        for v, neighbors in infected_by.items():
            if len(neighbors) == 1:
                contribution[neighbors[0]] += 1

        # Take the best answer.
        best = (-1, min(initial))
        for u, score in contribution.items():
            if score > best[0] or score == best[0] and u < best[1]:
                best = score, u
        return best[1]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        visited = [False] * n
        for i in initial:
            visited[i] = True
        conn = [set() for i in range(n)]            
        def bfs(node):
            q = collections.deque([node])
            v = visited[:]
            while q:
                i = q.popleft()
                for j, k in enumerate(graph[i]):
                    if k and not v[j]:
                        v[j] = True
                        q.append(j)
                        conn[j].add(node)
        for i in initial:
            bfs(i)
        cnt = collections.Counter()
        for k, v in enumerate(conn):
            if len(v) == 1:
                cnt[v.pop()] += 1
        if not cnt:
            return min(initial)
        s = sorted(list(cnt.items()), key=lambda k: (k[1], -k[0]))
        return s[-1][0]


class Solution:
    def dfs(self, i, visited, graph):
        if i in visited:
            return
        visited.add(i)
        for x, edge in enumerate(graph[i]):
            if edge:
                self.dfs(x, visited, graph)
    
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        numInfected = float('inf')
        minVal = None
        initial.sort()
        for i in initial:
            visited = set([i])
            for j in initial:
                self.dfs(j, visited, graph)
            if len(visited) < numInfected:
                numInfected = len(visited)
                minVal = i
        
        return minVal


import collections
class Solution(object):
    def minMalwareSpread(self, graph, initial):
        N = len(graph)
        clean = set(range(N)) - set(initial)
        def dfs(u, seen):
            for v, adj in enumerate(graph[u]):
                if adj and v in clean and v not in seen:
                    seen.add(v)
                    dfs(v, seen)

        # For each node u in initial, dfs to find
        # 'seen': all nodes not in initial that it can reach.
        infected_by = {v: [] for v in clean}
        for u in initial:
            seen = set()
            dfs(u, seen)

            # For each node v that was seen, u infects v.
            for v in seen:
                infected_by[v].append(u)

        # For each node u in initial, for every v not in initial
        # that is uniquely infected by u, add 1 to the contribution for u.
        contribution = collections.Counter()
        for v, neighbors in infected_by.items():
            if len(neighbors) == 1:
                contribution[neighbors[0]] += 1

        # Take the best answer.
        best = (-1, min(initial))
        for u, score in contribution.items():
            if score > best[0] or score == best[0] and u < best[1]:
                best = score, u
        return best[1]

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #how many nodes
        N = len(graph)
        clean = set(range(N)) - set(initial)
        def dfs(u, seen):
            for v, adj in enumerate(graph[u]):
                if adj and v in clean and v not in seen:
                    seen.add(v)
                    dfs(v, seen)

        # For each node u in initial, dfs to find
        # 'seen': all nodes not in initial that it can reach.
        infected_by = {v: [] for v in clean}
        for u in initial:
            seen = set()
            dfs(u, seen)

            # For each node v that was seen, u infects v.
            for v in seen:
                infected_by[v].append(u)

        # For each node u in initial, for every v not in initial
        # that is uniquely infected by u, add 1 to the contribution for u.
        contribution = collections.Counter()
        for v, neighbors in infected_by.items():
            if len(neighbors) == 1:
                contribution[neighbors[0]] += 1
        # Take the best answer.
        best = (-1, min(initial))
        for u, score in contribution.items():
            if score > best[0] or score == best[0] and u < best[1]:
                best = score, u
        return best[1]

from collections import defaultdict
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        if not graph:return -1
        n = len(graph)
        
        initial = sorted(initial)
        
        clean = set([i for i in range(n)]) - set(initial)
        infected_by = {i:[] for i in range(n)}
        
        def dfs(node):
            for i,v in enumerate(graph[node]):
                if v and i in clean and i not in seen:
                    seen.add(i)
                    dfs(i)
        for node in initial:
            seen = set()
            dfs(node)
            for u in seen:
                infected_by[u].append(node)
        
        cnt = {v:0 for v in initial}
        
        for i in infected_by:
            if len(infected_by[i]) == 1: 
                cnt[infected_by[i][0]] += 1
        m = 0 
        res = initial[0]
        for i in cnt:
            if cnt[i] > m:
                res = i
                m = cnt[i]
        return res
        


from collections import Counter

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        # Depth First Search
        # For each node v not in initial, we want to know which nodes u from initial can reach v in the graph G [with u (and its edges) added to G]. Let's say these nodes u \"infect\" v.
        # Time  complexity: O(N^2)
        # Space complexity: O(N)
        N = len(graph)
        clean = set(range(N)) - set(initial)
        def dfs(u, seen):
            for v, adj in enumerate(graph[u]):
                if adj and v in clean and v not in seen:
                    seen.add(v)
                    dfs(v, seen)

        # For each node u in initial, dfs to find
        # 'seen': all nodes not in initial that it can reach.
        infected_by = {v: [] for v in clean}
        for u in initial:
            seen = set()
            dfs(u, seen)

            # For each node v that was seen, u infects v.
            for v in seen:
                infected_by[v].append(u)

        # For each node u in initial, for every v not in initial
        # that is uniquely infected by u, add 1 to the contribution for u.
        contribution = Counter()
        for v, neighbors in list(infected_by.items()):
            if len(neighbors) == 1:
                contribution[neighbors[0]] += 1

        # Take the best answer.
        best = (-1, min(initial))
        for u, score in list(contribution.items()):
            if score > best[0] or score == best[0] and u < best[1]:
                best = score, u

        return best[1]




class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        nodes = len(graph)
        min_count = float('inf')
        min_node = 0
        for node in sorted(initial):
            visited = set()
            queue = deque()
            count = 0
            for i in initial:
                if i != node and i not in visited:
                    queue.append(i)
                    visited.add(i)
                    count += 1
                    while queue:
                        curr = queue.popleft()
                        for i, edge in enumerate(graph[curr]):
                            if edge == 1 and i != node and i not in visited:
                                queue.append(i)
                                visited.add(i)
                                count += 1
            if count < min_count:
                min_count = count
                min_node = node
        return min_node
            
        


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        spreads = [[] for _ in range(len(graph))]
        initial = set(initial)
        for i in initial:
            q = {i}
            visited = set()
            while q:
                cur = q.pop()
                if cur in visited or (cur in initial and cur != i):
                    continue
                visited.add(cur)
                spreads[cur].append(i)
                for j in range(len(graph[cur])):
                    if graph[cur][j]:
                        q.add(j)
        counts = defaultdict(int)
        for s in spreads:
            if len(s) == 1:
                counts[s[0]] += 1

        most = next(iter(initial))
        for i, c in list(counts.items()):
            if c > counts[most] or (c == counts[most] and i < most):
                most = i
        return most


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        nodes = len(graph)
        min_count = float('inf')
        min_node = 0
        for node in initial:
            visited = set()
            queue = deque()
            count = 0
            for i in initial:
                if i != node and i not in visited:
                    queue.append(i)
                    visited.add(i)
                    count += 1
                    while queue:
                        curr = queue.popleft()
                        for i, edge in enumerate(graph[curr]):
                            if edge == 1 and i != node and i not in visited:
                                queue.append(i)
                                visited.add(i)
                                count += 1
            if count < min_count or (count == min_count and node < min_node):
                min_count = count
                min_node = node
        return min_node
            
        


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        bfs=[]
        oinitial=set(initial)
        for i in initial:
            bfs.append([i,i])
        #print(bfs)
        frm={}
        
        
        for init in initial:
            seen=set(initial)
            bfs=[init]
            for n in bfs:
                for i,c in enumerate(graph[n]):
                    if i==n or i in seen or c==0:continue
                    seen.add(i)
                    if i in frm:
                        frm[i].append(init)
                    else:
                        frm[i]=[init]
                    bfs.append(i)
        
        #print(frm)
        #print(src)
        res=[0]*len(graph)
        
        for k in frm:
            if len(frm[k])==1:
                res[frm[k][0]]+=1
        
        
        if max(res)==0:return min(initial)
        
        return res.index(max(res))
                
            
            
            
        
        
        
            
                
                
            



class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        numNodes, minSpread, minNode = len(graph), math.inf, None
        initial.sort()
        
        def helper(curr, visited):

            if curr in visited:return

            edges = graph[curr]
            visited.add(curr)

            for i in range(len(edges)):
                if graph[curr][i] == 1:
                    helper(i, visited)     
        
        for i in initial:
            visited = set([i])
            for j in initial:
                if i!= j:
                    helper(j, visited)
          
            if len(visited) < minSpread:
                minSpread = len(visited)
                minNode = i
        
        return minNode
        
    


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #build adjacent arrays to represent the graph
        #go through the initial nodes and then do dfs, this could be be timeout.
        d = collections.defaultdict(list)
        for init in initial:
            visit = set(initial)
            q = collections.deque([init])
            while q:
                node = q.popleft()
                for i in range(len(graph[node])):
                    if graph[node][i] == 0 or i in visit:
                        continue
                    visit.add(i)
                    d[i].append(init)
                    q.append(i)
                    
        res = [0] * len(graph)
        for m in d: #这里出错的，是里面的元素而不是索引
        #for m in range(len(d)): wrong because d is dictionary, not array
            if len(d[m]) == 1:
                res[d[m][0]] += 1
        if max(res) == 0: return min(initial) #为什么是min(initial)而不是initial[0],题意initial里的值就是index
        return res.index(max(res))

from functools import lru_cache
from typing import List, Tuple

import numpy
import collections

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

    const_n = len(graph)
    d = collections.defaultdict(list)

    for init in initial:
      vis = set(initial)
      q = collections.deque([init])
      while q:
        index = q.popleft()
        for node in range(len(graph[index])):
          if graph[index][node] == 0:
            continue
          if node in vis:
            continue

          vis.add(node)
          d[node].append(init)
          q.append(node)
        pass
      pass

    res = [0] * const_n
    for key, value in d.items():
      if len(value) == 1:
        res[value[0]] += 1

    if max(res) == 0:
      return min(initial)
    return res.index(max(res))

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(i,s):
            if i in visit or (i in ht and i!=s):
                return
            visit.add(i)
            source[i].append(s)
            for j in range(len(graph[i])):
                if graph[i][j]:
                    dfs(j,s)
     
        ht=set(initial)
        source=[[] for _ in range(len(graph))]
        for i in initial:
            visit=set()
            dfs(i,i)

        dic=collections.defaultdict(int)
        for i in range(len(source)):
            if len(source[i])==1:
                dic[source[i].pop()]+=1
        res,val=len(graph),0
        for i,cnt in list(dic.items()):
            if cnt>val:
                res,val=i,cnt
            elif cnt==val:
                res=min(res,i)

        return res
                
                
        


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        numNodes = len(graph)
        minSpread = float('inf')
        minNode = None
        initial.sort()
        
        for i in initial:
            visited = set([i])
            for j in initial:
                self.helper(graph, j, visited)
          
            if len(visited) < minSpread:
                minSpread = len(visited)
                minNode = i
        
        return minNode
        
    
    def helper(self, graph, curr, visited):

        if curr in visited:
            return
        
        edges = graph[curr]
        visited.add(curr)
        
        for i in range(len(edges)):
            if graph[curr][i] == 1:
                self.helper(graph, i, visited)        

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #build adjacent arrays to represent the graph
        #go through the initial nodes and then do dfs, this could be be timeout.
        d = collections.defaultdict(list)
        for init in initial:
            visit = set(initial)
            q = collections.deque([init])
            while q:
                node = q.popleft()
                for i in range(len(graph[node])):
                    if graph[node][i] == 0 or i in visit:
                        continue
                    visit.add(i)
                    d[i].append(init)
                    q.append(i)
                    
        res = [0] * len(graph)
        for m in d:
        #for m in range(len(d)):
            if len(d[m]) == 1:
                res[d[m][0]] += 1
        if max(res) == 0: return min(initial)
        return res.index(max(res))

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        d = collections.defaultdict(list)
        for init in initial:
            vis = set(initial)
            Q = collections.deque([init])
            while Q:
                infect = Q.popleft()
                for node in range(len(graph[infect])):
                    if graph[infect][node] == 0: continue
                    if node in vis: continue
                    vis.add(node)
                    d[node].append(init)
                    Q.append(node)
        # count the most frequent node
        res = [0] * n
        for key in d:
            if len(d[key]) == 1:
                res[d[key][0]] += 1
        if max(res) == 0: return min(initial)
        return res.index(max(res))


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        numNodes = len(graph)
        minSpread = float('inf')
        minNode = None
        initial.sort()
        
        def helper(curr, visited):

            if curr in visited:
                return

            edges = graph[curr]
            visited.add(curr)

            for i in range(len(edges)):
                if graph[curr][i] == 1:
                    helper(i, visited)     
        
        for i in initial:
            visited = set([i])
            for j in initial:
                helper(j, visited)
          
            if len(visited) < minSpread:
                minSpread = len(visited)
                minNode = i
        
        return minNode
        
    



class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        numNodes = len(graph)
        minSpread = float('inf')
        minNode = None
        initial.sort()
        
        def helper(curr, visited):

            if curr in visited:
                return

            edges = graph[curr]
            visited.add(curr)

            for i in range(len(edges)):
                if graph[curr][i] == 1:
                    helper(i, visited)     
        
        for i in initial:
            visited = set([i])
            for j in initial:
                if i!= j:
                    helper(j, visited)
          
            if len(visited) < minSpread:
                minSpread = len(visited)
                minNode = i
        
        return minNode
        
    


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        d = collections.defaultdict(list)
        for init in initial:
            vis = set(initial)
            Q = collections.deque([init])
            while Q:
                infect = Q.popleft()
                for node in range(len(graph[infect])):
                    if graph[infect][node] == 0: continue
                    if node in vis: continue
                    vis.add(node)
                    d[node].append(init)
                    Q.append(node)
        # count the most frequent node
        res = [0] * n
        for key in d:
            if len(d[key]) == 1:
                res[d[key][0]] += 1
        if max(res) == 0: return min(initial)
        return res.index(max(res))
#         def find(x):
#             if x != parents[x]:
#                 parents[x] = find(parents[x])
#             return parents[x]
        
#         def union(x,y):
#             parents[find(x)] = parents[find(y)]
            
#         n = len(graph)
#         parents = list(range(n))    
#         for i in range(n):
#             for j in range(i + 1, n):
#                 if graph[i][j] == 1:
#                     union(i , j)
                    
#         union = collections.Counter(find(i) for i in range(n))
#         malware = collections.Counter(find(i) for i in initial)
        
#         save , res = min(initial) , 0
#         for i in initial:
#             if malware[find(i)] == 1:
#                 if union[find(i)] > save:
#                     save , res = union[find(i)] , i
#                 elif union[find(i)] == save:
#                     res = min(res, i)
                    
#         return res
        


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #build adjacent arrays to represent the graph
        #go through the initial nodes and then do dfs, this could be be timeout.
        d = collections.defaultdict(list)
        for init in initial:
            visit = set(initial)
            q = collections.deque([init])
            while q:
                node = q.popleft()
                for i in range(len(graph[node])):
                    if graph[node][i] == 0 or i in visit:
                        continue
                    visit.add(i)
                    d[i].append(init)
                    q.append(i)
                    
        res = [0] * len(graph)
        for m in d: #这里出错的，是里面的元素而不是索引
        #for m in range(len(d)):
            if len(d[m]) == 1:
                res[d[m][0]] += 1
        if max(res) == 0: return min(initial) #为什么是min(initial)而不是initial[0],题意initial里的值就是index
        return res.index(max(res))

from collections import Counter, defaultdict
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        # Total nodes
        N = len(graph)
        seen = set()
        refcounter = Counter()
        
        #clean nodes which are not infected
        clean_nodes = set(range(N)) - set(initial)
        maxval = 0
        
        def dfs(node, seen):
            for v, adj in enumerate(graph[node]):
                if adj and v not in seen and v in clean_nodes:
                    seen.add(node)
                    dfs(v, seen)
        
        for key in initial:
            seen = set()
            dfs(key, seen)
            refcounter[key] = len(seen)
            if maxval < refcounter[key]:
                maxval = refcounter[key]
            seen.clear()

        print(refcounter)
        
        maxlist = [ key for key,val in list(refcounter.items()) if refcounter[key] == maxval]
        if not maxlist or len(maxlist) > 1:
            return sorted(initial)[0]
        return maxlist[0]
        
        
            


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n = len(graph)
        d = collections.defaultdict(list)
        for init in initial:
            vis = set(initial)
            Q = collections.deque([init])
            while Q:
                infect = Q.popleft()
                for node in range(len(graph[infect])):
                    if graph[infect][node] == 0: continue
                    if node in vis: continue
                    vis.add(node)
                    d[node].append(init)
                    Q.append(node)
        # count the most frequent node
        res = [0] * n
        for key in d:
            if len(d[key]) == 1:
                res[d[key][0]] += 1
        if max(res) == 0: return min(initial)
        return res.index(max(res))

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def infected(src, exclude=None):
            infected = set()
            def dfs(node, infected):
                if node in infected:
                    return
                infected |= {node}
                for neighbor in range(len(graph[node])):
                    if graph[node][neighbor]==0 or neighbor==exclude:
                        continue
                    dfs(neighbor, infected)
            for source in src:
                if source == exclude:
                    continue
                dfs(source, infected)
            return len(infected)
        initial.sort()
        res, best = initial[0], len(graph)
        for source in initial:
            temp = infected(initial, source)
            if temp < best:
                res, best = source, temp
        return res

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        
        least_infections = len(graph)
        node_to_remove = initial[0]
        
        for i in initial:
            
            total_infected = 0
            
            q = initial[:]
            q.remove(i)
            visited = set()
            
            while q != []:
                # print(q)
                v = q.pop()
                if v != i and not v in visited:
                    total_infected += 1
                    visited.add(v)
                    for j,edge in enumerate(graph[v]):
                        if j!=i and (edge == 1) and not (j in visited):
                            q.append(j)
            
            # print(total_infected,i)
            
            if total_infected < least_infections:
                least_infections = total_infected
                node_to_remove = i
            elif total_infected == least_infections:
                node_to_remove = min(i,node_to_remove)
        
        return node_to_remove