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.  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.
Note that if a node was removed from the initial list of infected nodes, it may still be infected later as a result of the malware spread.
 


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

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

Example 3:
Input: graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
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:
class Solution(object):
    def minMalwareSpread(self, graph, initial):
        # 1. Color each component.
        # colors[node] = the color of this node.

        N = len(graph)
        colors = {}
        c = 0

        def dfs(node, color):
            colors[node] = color
            for nei, adj in enumerate(graph[node]):
                if adj and nei not in colors:
                    dfs(nei, color)

        for node in range(N):
            if node not in colors:
                dfs(node, c)
                c += 1

        # 2. Size of each color.
        # size[color] = number of occurrences of this color.
        size = collections.Counter(colors.values())

        # 3. Find unique colors.
        color_count = collections.Counter()
        for node in initial:
            color_count[colors[node]] += 1

        # 4. Answer
        ans = float('inf')
        for x in initial:
            c = colors[x]
            if color_count[c] == 1:
                if ans == float('inf'):
                    ans = x
                elif size[c] > size[colors[ans]]:
                    ans = x
                elif size[c] == size[colors[ans]] and x < ans:
                    ans = x

        return ans if ans < float('inf') else min(initial)    

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(node, vis):
            for connect in range(len(graph[node])):
                if graph[node][connect] == 1 and connect not in vis:
                    vis.add(connect)
                    dfs(connect, vis)
                    
        init = set(initial)
        total_vis = set()
        del_node, subgraph_len = min(initial), 0
        for node in range(len(graph)):
            if node not in total_vis:
                vis = set([node])
                dfs(node, vis)
                infect = vis & init
                if len(infect) == 1:
                    if len(vis) > subgraph_len or (len(vis) == subgraph_len and list(infect)[0] < del_node):
                        del_node, subgraph_len = list(infect)[0], len(vis)
                total_vis |= vis
        return del_node

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(node,vis):
            for v in  range(len(graph[node])):
                if graph[node][v] == 1 and v not in vis:
                    vis.add(v)
                    dfs(v,vis)

        s = set(initial)
        t_vis = set()
        del_node, subgraph_len = min(initial), 0
        for node in range(len(graph)):
            if node not in t_vis:
                vis = set([node])
                dfs(node,vis)
                # caculate the number of infected node in the subgraph
                infect = vis & s
                if len(infect) == 1:
                    # more number of nodes or smaller index
                    if len(vis) > subgraph_len or (len(vis) == subgraph_len and list(infect)[0] < del_node):
                        del_node,subgraph_len = list(infect)[0],len(vis)
                t_vis |= vis
        return del_node


from itertools import count
from collections import Counter

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        # color the components
        colors = dict()
        c = count()
        
        def dfs(node, color):
            colors[node] = color
            
            for nei, adj in enumerate(graph[node]):
                if adj and nei not in colors:
                    dfs(nei, color)
                    
        for node in range(len(graph)):
            if node not in colors:
                dfs(node, next(c))
        
        
        # count sizes of each component
        size = Counter(list(colors.values()))
        
        
        # find components with only one malware inside
        malware_count = Counter()
        for node in initial:
            malware_count[colors[node]] += 1
            
        #print(malware_count)
        #print(size)
        
        # find the component with the most nodes and only 1 malware
        ans = None
        ans_nodes = 0
        for x in initial:
            c = colors[x]
            if malware_count[c] != 1:
                continue
            if size[c] > ans_nodes:
                ans = x
                ans_nodes = size[c]
            elif size[c] == ans_nodes:
                ans = min(ans, x)
                
        return ans if ans else min(initial)


class Solution(object):
    def minMalwareSpread(self, graph, initial):
        # 1. Color each component.
        # colors[node] = the color of this node.

        N = len(graph)
        colors = {}
        c = 0

        def dfs(node, color):
            colors[node] = color
            for nei, adj in enumerate(graph[node]):
                if adj and nei not in colors:
                    dfs(nei, color)

        for node in range(N):
            if node not in colors:
                dfs(node, c)
                c += 1

        # 2. Size of each color.
        # size[color] = number of occurrences of this color.
        size = collections.Counter(list(colors.values()))

        # 3. Find unique colors.
        color_count = collections.Counter()
        for node in initial:
            color_count[colors[node]] += 1

        # 4. Answer
        ans = float('inf')
        for x in initial:
            c = colors[x]
            if color_count[c] == 1:
                if ans == float('inf'):
                    ans = x
                elif size[c] > size[colors[ans]]:
                    ans = x
                elif size[c] == size[colors[ans]] and x < ans:
                    ans = x

        return ans if ans < float('inf') else min(initial)
    
    
# Algorithm

# This algorithm has a few parts:

# Coloring each component: For each node, if it isn't yet colored, use a depth-first search to traverse its component, coloring that component with a new color.

# Size of each color: Count the number of occurrences of each color.

# Find unique colors: Look at the colors of nodes in initial to see which nodes have unique colors.

# Choose answer: For each node with a unique color, find the size of that color. The largest size is selected, with ties broken by lowest node number.

# If there is no node with a unique color, the answer is min(initial).


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        if len(graph) == 0:
            return 0
        
        g = dict()
        
        for i in range(len(graph)):
            for j in range(len(graph[i])):
                if graph[i][j]:
                    if i in g:
                        g[i].append(j)
                    else:
                        g[i] = [j]
        
        groups = []
        initialSet = set(initial)
        numOfNodes = [0] * len(graph)
        
        for v, e in list(g.items()):
            if v not in initialSet:
                continue
            num = 1
            initialSet.remove(v)
            group = [v]
            stack = e
            visited = {v}
            while len(stack) != 0:
                vertex = stack.pop()
                if vertex not in visited:
                    if vertex in initialSet:
                        initialSet.remove(vertex)
                        group.append(vertex)
                    stack.extend(g[vertex])
                    visited.add(vertex)
                    num += 1
            groups.append(group)
            numOfNodes[v] = num
                
        
        canRemove = set([group[0] for group in groups if len(group) == 1])
        # print(groups)
        # print(numOfNodes)
        # print(canRemove)
        
        if len(canRemove) == 0:
            return min(initial)
        
        result = -1
        for vertex in initial:
            if vertex in canRemove and (result == -1 or numOfNodes[vertex] > numOfNodes[result]):
                result = vertex
            elif vertex in canRemove and numOfNodes[vertex] == numOfNodes[result] and vertex < result:
                result = vertex
        
        return result
        
        
        
        
       
            


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #coloring each component (belong to different connected components)
        #count the size of each color
        #find unique nodes in initial
        #for each node with a unique color, choose the largest size, if there is a tie, choose the one with the smaller index
        N = len(graph)
        colors = {}# colors[node] = the color of this node.
        c = 0
        def dfs(node, color):
            colors[node] = color
            for nei, adj in enumerate(graph[node]):
                if adj and nei not in colors:#nei in colors的情况都考虑过了
                    dfs(nei, color)
        for node in range(N):
            if node not in colors:
                dfs(node, c)
                c += 1
        size = collections.Counter(list(colors.values()))# size[color] = number of occurrences of this color.
        color_count = collections.Counter()
        for node in initial:
            color_count[colors[node]] += 1
        ans = -1# the index of node to be removed
        for x in initial:
            if color_count[colors[x]] == 1:
                if ans == -1:
                    ans = x
                elif size[colors[x]] > size[colors[ans]]:
                    ans = x
                elif size[colors[x]] == size[colors[ans]] and x < ans:
                    ans = x
        return ans if ans != -1 else min(initial)#why we need to remove the minimum of initial, it won't reduce the malware count


class Solution:
    def minMalwareSpread(self, graph, initial):
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank = {}
        initial = set(initial)
        # rank, initial = collections.defaultdict(list), set(initial)
        for node in sorted(initial):
            nodes = set()
            dfs(node)
            rank[node] = nodes
        print(rank)
        
        passed = []
        for k,v in list(rank.items()):
            count = 0
            for i in initial:
                if i in v:
                    count += 1
            if count <= 1:
                passed.append((k, len(v)))
        passed.sort(key = lambda x:x[1], reverse=True)
        if len(passed) == 0:
            return min(initial)
        else:
            return passed[0][0]
            
        
    
        # return min(initial)
            
        #     if nodes & initial == {node}:
        #         rank[len(nodes)].append(node)
        # return rank[max(rank)][0] if rank else min(initial)


class Solution(object):
    def minMalwareSpread(self, graph, initial):
        def dfs(node,vis):
            for v in  range(len(graph[node])):
                if graph[node][v] == 1 and v not in vis:
                    vis.add(v)
                    dfs(v,vis)

        s = set(initial)
        t_vis = set()
        del_node, subgraph_len = min(initial), 0
        for node in range(len(graph)):
            if node not in t_vis:
                vis = set([node])
                dfs(node,vis)
                # caculate the number of infected node in the subgraph
                infect = vis & s
                if len(infect) == 1:
                    # more number of nodes or smaller index
                    if len(vis) > subgraph_len or (len(vis) == subgraph_len and list(infect)[0] < del_node):
                        del_node,subgraph_len = list(infect)[0],len(vis)
                t_vis |= vis
        return del_node

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank, initial = collections.defaultdict(list), set(initial)
        for node in sorted(initial):
            nodes = set()
            dfs(node)
            if nodes & initial == {node}:
                rank[len(nodes)].append(node)
        return rank[max(rank)][0] if rank else min(initial)

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #Graph represented as an adjaency matrix        
        #Loop through infected
        #Simulate condition of what would happen if only this infected node is removed
        #If num infected is the new min -> then we have a potential answer
        
        infected_nodes = set(initial)
        max_infected = len(graph)
        node_to_remove = initial[0]
        
        for infected_node in initial:
            infected_nodes.remove(infected_node)
            infected = set()
            for node in infected_nodes:
                self.dfs(node, graph, infected)
                
            infected_nodes.add(infected_node)
            if len(infected) < max_infected or (len(infected) == max_infected and infected_node < node_to_remove):
                node_to_remove = infected_node
                max_infected = len(infected)
        return node_to_remove
        #Loop through the infected nodes
        #Do a traversal to simulate an \"infection\"
        #Count number of nodes infected and track max infected
        
    def dfs(self, node, graph, infected):
        infected.add(node)
        for col, val in enumerate(graph[node]):
            if val == 1 and col not in infected:                
                self.dfs(col, graph, infected)


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #Graph represented as an adjaency matrix        
        #Loop through infected
        #Simulate condition of what would happen if only this infected node is removed
        #If num infected is the new min -> then we have a potential answer
        
        infected_nodes = set(initial)
        max_infected = len(graph)
        node_to_remove = initial[0]
        
        for infected_node in initial:
            infected_nodes.remove(infected_node)
            infected = set()
            for node in infected_nodes:
                self.dfs(node, graph, infected)
                
            infected_nodes.add(infected_node)
            if len(infected) < max_infected or (len(infected) == max_infected and infected_node < node_to_remove):
                node_to_remove = infected_node
                max_infected = len(infected)
        return node_to_remove
        #Loop through the infected nodes
        #Do a traversal to simulate an \"infection\"
        #Count number of nodes infected and track max infected
        
    def dfs(self, node, graph, infected):
        infected.add(node)
        for col, val in enumerate(graph[node]):
            if val == 1 and col not in infected:                
                self.dfs(col, graph, infected)


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #dfs to find all node in a subgraph, only subgraph with 1 infected node can be saved as we can remove only one node
        init = set(initial)
        total_visited = set()
        res, max_subgraph_len = min(initial), 0
        for node in range(len(graph)):
            if node not in total_visited:
                visited = set([node])
                self.dfsConnected(graph, node, visited)
                #find infected node in subgraph
                infected = visited & init
                if len(infected) == 1:
                    if len(visited) > max_subgraph_len or (len(visited) == max_subgraph_len and min(infected) < res):
                        res, max_subgraph_len = min(infected), len(visited)
                total_visited |= visited
        return res
    
    def dfsConnected(self, graph, node, visited):
        for neighbor in range(len(graph[node])):
            if graph[node][neighbor] == 1 and neighbor not in visited:
                visited.add(neighbor)
                self.dfsConnected(graph, neighbor, visited)

class Solution:
    def minMalwareSpread(self, graph, initial):
        def dfs(i):
            nodes.add(i)
            for j in range(len(graph[i])):
                if graph[i][j] and j not in nodes:
                    dfs(j)
        rank, initial = collections.defaultdict(list), set(initial)
        for node in sorted(initial):
            nodes = set()
            dfs(node)
            if nodes & initial == {node}:
                rank[len(nodes)].append(node)
        return rank[max(rank)][0] if rank else min(initial)

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        #This is special case where all the nodes are initially infected, see which one connected least
        if len(initial) == len(graph):
            m = 0
            r = initial[0]
            for i in initial:
                if m < sum(x == 0 for x in graph[i]):
                    m = sum(x==0 for x in graph[i])
                    r = i
            return r
            
        
        d = collections.defaultdict(list)
        for init in initial:
            q = collections.deque()
            q.append(init)
            visit = set() #only cache the current initial infect node
            visit.add(init)
            while q:
                virus = q.popleft()
                for i in range(len(graph[virus])):
                    if graph[virus][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:
            if len(d[m]) == 1:
                res[d[m][0]] += 1
        print(d)
        if max(res) == 0:
            return min(initial)
        return res.index(max(res))
        '''
        51 of 52 passed, only [1,1,0][1,1,0][0,0,1] with [0,1 2] not passing
        d = collections.defaultdict(list)
        for init in initial:
            q = collections.deque()
            q.append(init)
            visit = set()
            visit.add(init)
            while q:
                virus = q.popleft()
                for i in range(len(graph[virus])):
                    if graph[virus][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:
            if len(d[m]) == 1:
                res[d[m][0]] += 1
        print(d)
        if max(res) == 0:
            return min(initial)
        return res.index(max(res))
        '''

class Solution:
    # def findRoot(self, parents, index):
    #     root = index
    #     while parents[root] != root:
    #         root = parents[root]
    #     while root != index:
    #         temp = parents[index]
    #         parents[index] = root
    #         index = temp
    #     return root
    #
    # def creatParents(self, graph):
    #     node_num = len(graph)
    #     parents = [i for i in range(node_num)]
    #     for i in range(node_num):
    #         for j in range(i + 1, node_num):
    #             if graph[i][j] == 1:
    #                 root_i = self.findRoot(parents, i)
    #                 root_j = self.findRoot(parents, j)
    #                 if root_i != root_j:
    #                     parents[root_i] = root_j
    #     return parents
    #
    # def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
    #     initial_num = len(initial)
    #     node_num = len(graph)
    #     if initial_num <= 0 or node_num <= 0:
    #         return 0
    #     if initial_num==1:
    #         return initial[0]
    #
    #     parents = self.creatParents(graph)
    #     node_info = [0] * node_num  # 各节点圈中的节点数
    #     for i in range(node_num):
    #         root = self.findRoot(parents, i)
    #         node_info[root] += 1
    #
    #     # 找出initial种节点圈最大的节点
    #     index = initial[0]
    #     max = -1
    #     for i in range(initial_num):
    #         root = self.findRoot(parents, initial[i])
    #         if node_info[root] > max or (node_info[root] == max and initial[i] < index):
    #             max = node_info[root]
    #             index = initial[i]
    #     return index

    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        initial.sort()
        visited = []
        result = [-1, 0]  # index,count

        for i in range(len(graph)):
            if i in visited:
                continue
            else:
                temp = [-1, 0]
                stack = [i]
                visited.append(i)
                stack_num = 1;
                while stack:
                    index = stack.pop(0)
                    if index in initial:
                        if temp[0] == -1:
                            temp[0] = index
                        temp[1] += 1
                    for j in range(len(graph[index])):
                        if graph[index][j] == 1 and (j not in visited):
                            stack.append(j)
                            stack_num += 1
                            visited.append(j)
                if temp[1] == 1:
                    if result[1] < stack_num:
                        result[0] = temp[0]
                        result[1] = stack_num
        return result[0] if result[0] != -1 else initial[0]



import math
import queue

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        if len(initial) == 0:
            return 0
        best = None
        best_val = math.inf
    
        initial_set = set(initial)
        for index in initial:
            initial_set.remove(index)
            
            seen = set()
            Q = queue.Queue()
            for elt in initial_set:
                seen.add(elt)
                Q.put(elt)
            
            while not Q.empty():
                u = Q.get()
                
                for i, v in enumerate(graph[u]):
                    if v == 0 or i in seen:
                        continue 
                    
                    seen.add(i)
                    Q.put(i)
            if len(seen) < best_val:
                best_val = len(seen)
                best = index
            elif len(seen) == best_val and index < best:
                best = index
            initial_set.add(index)
        return best
                    
                    
            
            


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        
        heap = []
        sizes = {}
        component = 0
        
        for i in initial:
          #print(\"graph\", graph, heap)
          if graph[i][i] < 0:
            heappush(heap, (-sizes[component], i, graph[i][i]))
            continue
          
          queue = deque([i])
          #print(\"outer queue\", queue)
          size = 0
          component = component - 1
          
          while len(queue) > 0:

            current = queue.popleft()
            #print(current)

            if graph[current][current] == 1:
              size = size + 1
              graph[current][current] = component
              queue.extend(i for (i, x) in enumerate(graph[current]) if x == 1)
              #print(\"queue\", current, queue)
              
          heappush(heap, (-size, i, component))
          sizes[component] = size
            
        #print(\"final heap\", heap)
        
        return self.select(heap)
      
    def select(self, heap):
      
      if len(heap) == 1:
        return heap[0][1]
      
      res = heappop(heap)
      others = []
      while len(heap) > 0 and res[0] == heap[0][0] and res[2] == heap[0][2]:
        others.append(heappop(heap))
      
      if len(others) == 1 and len(heap) == 0 or len(others) == 0:
        return res[1]
      
      if len(heap) == 0:
        return res[1]
      
      return self.select(heap)

import math
import queue

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        if len(initial) == 0:
            return 0
        best = None
        best_val = math.inf
    
        initial.sort()
        initial_set = set(initial)
        for index in initial:
            initial_set.remove(index)
            
            seen = set()
            Q = queue.Queue()
            for elt in initial_set:
                seen.add(elt)
                Q.put(elt)
            
            while not Q.empty():
                u = Q.get()
                
                for i, v in enumerate(graph[u]):
                    if v == 0 or i in seen:
                        continue 
                    
                    seen.add(i)
                    Q.put(i)
            if len(seen) < best_val:
                best_val = len(seen)
                best = index
            initial_set.add(index)
        return best
                    
                    
            
            


import heapq
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        nodes = set(initial)
        useless = set()
        best = 0
        initial.sort()
        index = initial[0]
        def dfs(start):
            count = 0
            stack = [start]
            visited = set()
            while stack:
                curr = stack.pop()
                if curr in visited:
                    continue
                if curr != start and curr in nodes:
                    useless.add(curr)
                    useless.add(start)
                visited.add(curr)
                count += 1
                for i in range(len(graph[curr])):
                    if graph[curr][i]:
                        stack.append(i)
            return count
        for i in initial:
            g = dfs(i)
            if i not in useless:
                if g > best:
                    best = g
                    index = i
        return index

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()
            for j in initial:
                if j != i:
                    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:
        visited = [False] * len(graph)
        sizes = [0] * len(graph)
        for node in range(len(graph)):
            if visited[node]:
                continue
            vertices = []
            numOfInitials = self.dfs(graph, node, visited, vertices, initial)
            size = len(vertices)
            for i in vertices:
                sizes[i] = size if numOfInitials < 2 else 0
        maxSpread = -1
        maxNode = -1
        for i in initial:
            print(i)
            if sizes[i] > maxSpread:
                maxSpread = sizes[i]
                maxNode = i
            elif sizes[i] == maxSpread:
                maxNode = min(maxNode, i)
        return maxNode
    
    def dfs(self, graph, node, visited, vertices, initial):
        initials = 0
        if visited[node]:
            return initials
        vertices.append(node)
        visited[node] = True
        if node in initial:
            initials += 1
        for i in range(len(graph[node])):
            if graph[node][i] == 1:
                initials += self.dfs(graph, i, visited, vertices, initial)
        return initials
        


class Solution:
    
    def calcConnectedNodes(self, graph, node):
        visited = set()
        toVisit = []
        toVisit.append(node)
        while len(toVisit) != 0:
            
            curNode = toVisit.pop()
            if curNode in visited:
                continue
            visited.add(curNode)
            for i in range(len(graph[curNode])):
                if graph[curNode][i] == 1:
                    toVisit.append(i)
        return visited
            
            
        
    
    
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        initialSet = set(initial)
        maxNodesConnected = -1
        nodeToRemove = -1
        for node in initial:
            connectedNodes = self.calcConnectedNodes(graph, node)   
            intersected = connectedNodes.intersection(initialSet)
            # even if i removed this node, there are other nodes that will infect it, so no need
            if len(intersected) >= 2:
                continue
            if maxNodesConnected == -1 or len(connectedNodes) > maxNodesConnected or (len(connectedNodes) == maxNodesConnected and node < nodeToRemove):
                nodeToRemove = node
                maxNodesConnected = len(connectedNodes)
        if nodeToRemove == -1:
            return min(initial)
        return nodeToRemove


class Solution:
    
    def calcConnectedNodes(self, graph, node):
        visited = set()
        toVisit = []
        toVisit.append(node)
        while len(toVisit) != 0:
            
            curNode = toVisit.pop()
            if curNode in visited:
                continue
            visited.add(curNode)
            for i in range(len(graph[curNode])):
                if graph[curNode][i] == 1:
                    toVisit.append(i)
        return visited
    
    
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        initialSet = set(initial)
        maxNodesConnected = -1
        nodeToRemove = -1
        for node in initial:
            connectedNodes = self.calcConnectedNodes(graph, node)   
            intersected = connectedNodes.intersection(initialSet)
            # even if i removed this node, there are other nodes that will infect it, so no need
            if len(intersected) >= 2:
                continue
            if maxNodesConnected == -1 or len(connectedNodes) > maxNodesConnected or (len(connectedNodes) == maxNodesConnected and node < nodeToRemove):
                nodeToRemove = node
                maxNodesConnected = len(connectedNodes)
        if nodeToRemove == -1:
            return min(initial)
        return nodeToRemove


from collections import defaultdict
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        edges = defaultdict(list)
        for i in range(len(graph)):
            for j in range(len(graph[i])):
                if(graph[i][j] == 1):
                    edges[i].append(j)
        #maps nodes to their color  
        colors = defaultdict(int)
        #counts the number of nodes in that colored connected component
        nodes_in_colors = defaultdict(int)
        color = 1
        for node in initial:
            if(colors[node] == 0):
                colors[node] = color
            else:
                continue
            stack = [node]
            visited = set()
            curr_infected = 0
            while(stack):
                curr = stack.pop()
                curr_infected += 1
                for neigh in edges[curr]:
                    if(neigh not in visited):
                        stack.append(neigh)
                        visited.add(neigh)
                        colors[neigh] = color
            nodes_in_colors[color] = curr_infected
            color += 1
        #maps color to initial nodes of that color
        initial_color = defaultdict(list)
        for node in initial:
            initial_color[colors[node]].append(node)
        print(initial_color)
        unique_color = defaultdict(int)
        #only look for unique colors/ components with unique colors
        for node in initial:
            unique_color[colors[node]] += 1
        
        unique = []
        for color in unique_color:
            if(unique_color[color] == 1):
                unique.append(initial_color[color][0])
        if(len(unique) == 0):
            return min(initial)
        
        max_infected = 0
        min_node = float('inf')
        print(unique)
        for node in unique:
            if(nodes_in_colors[colors[node]] >= max_infected):
                max_infected = nodes_in_colors[colors[node]]
                min_node = min(node, min_node)
        return min_node
                
                


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        d = collections.defaultdict(list)
        initial.sort()
        
        for i in range(len(graph)):
            for j in range(len(graph[i])):
                if i != j and graph[i][j]==1:
                    d[i].append(j)
                else:
                    d[i].append(100)
                    d[i].pop()
        print(d)
            
        infected = set(initial)
        
        maxinfected=float('inf')
        res=0
        for i in range(len(initial)):
            self.curr_infected = 0
            infected.remove(initial[i])
            
            visited = set()
            for item in infected:
                self.dfs(item,d,visited,infected,True)
            
            print((self.curr_infected))
            if self.curr_infected < maxinfected:
                maxinfected=self.curr_infected
                res = initial[i]
                
            infected.add(initial[i])
            
        return res
    
    def dfs(self,curr,d,visited,infected,original_node):
        if curr in visited:
            return
        if curr in infected and not original_node:
            return
        original_node = False
        
        # mark visitied
        visited.add(curr)
        self.curr_infected += 1
        
        # grab neighbors
        neighbors = d[curr]
        
        for next in neighbors:
            self.dfs(next,d,visited,infected,original_node)
        


class Solution:
    def minMalwareSpread(self, graph, initial):
        # dfs
        def dfs(node, visited):
            if node in initial:
                return 0
            visited.add(node)
            res = 1
            for nxt_node, v in enumerate(graph[node]):
                if v == 0 or nxt_node == node: continue
                if nxt_node not in visited:
                    sub = dfs(nxt_node, visited)
                    if sub == 0:
                        return 0
                    res += sub
            return res
        
        initial = set(initial)
        res = [-1, 0]
        for n in list(initial):
            initial.discard(n)
            res = max([dfs(n, set()), -n], res)
            initial.add(n)
        return -res[1]
        
    def minMalwareSpread_I(self, graph, initial):
        def find(x):
            if x != parents[x]:
                parents[x] = find(parents[x])
            return parents[x]
        def union(x, y):
            parents[find(x)] = find(y)
        # init
        n = len(graph)
        parents = list(range(n))
        # union
        for i in range(n):
            for j in range(i + 1, n):
                if graph[i][j] == 1:
                    union(i, j)
        area = collections.Counter(find(i) for i in range(n))
        malware = collections.Counter(find(i) for i in initial)
        return min(initial, key=lambda i: [(malware[find(i)] == 1) * -area[find(i)], i])

    def minMalwareSpread_II(self, graph: List[List[int]], initial: List[int]) -> int:
        union_mem = {i:i for i in range(len(graph))}
        count = collections.Counter(range(len(graph)))
        
        def find(vertex):
            if union_mem[vertex] != vertex:
                union_mem[vertex] = find(union_mem[vertex])
            return union_mem[vertex]
        
        def union(v1, v2):
            v1f, v2f = find(v1), find(v2)
            if v1f != v2f:
                count[v1f] += count[v2f]
                union_mem[v2f] = v1f
        
        N = len(graph)
        for r in range(N):
            for c in range(N):
                if r != c and graph[r][c] == 1:
                    union(r, c)
        groups = collections.defaultdict(list)
        for v1 in initial:
            v1f = find(v1)
            groups[v1f].append(v1)
        return -max(([count[find(v1)], -v1] for v1 in initial if len(groups[find(v1)]) == 1), default = [0, -min(initial)])[1]

from collections import defaultdict
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        size = Counter()
        color = defaultdict(int)
        
        def dfs(node, c):
            color[node] = c
            size[c] += 1
            for nextNode, val in enumerate(graph[node]):
                if val and nextNode not in color:
                    dfs(nextNode, c)
        
        c = 0
        for node in range(len(graph)):
            if node not in color:
                dfs(node, c)
                c += 1
        
        # find node with unique color
        color_count = Counter()
        for node in initial:
            color_count[color[node]] += 1
            
        # if unique color, ans is node color with greatest size else smallest index
        ans = -1
        for node in initial:
            c = color[node]
            if color_count[c] == 1:
                if ans == -1:
                    ans = node
                elif size[c] > size[color[ans]]:
                    ans = node
                elif size[c] == size[color[ans]] and node < ans:
                    ans = node
        if ans == -1:
            return min(initial)
        return ans

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        minNode = -1
        maxSpread = 0
        for node in initial:
            testInit = initial.copy()
            testInit.remove(node)
            touch,testSpread = touchAnyNodes([node],graph,testInit)
            #print (str(node) + \" \" + str(touch) + \" \" + str(testSpread) )
            if not touch:
                if testSpread > maxSpread or (testSpread == maxSpread and node < minNode):
                    maxSpread = testSpread
                    minNode = node
        if maxSpread == 0:
            initial.sort()
            return initial[0]
        return minNode

def touchAnyNodes(visited,graph,infected) -> (bool,int):
    newVisited = visited.copy()
    for node in visited:
        for idx in range(len(graph[node])):
            if graph[node][idx] == 1 and (not idx in visited) and (not idx in newVisited):
                if idx in infected:
                    return True,0
                newVisited.append(idx)
    if len(newVisited) == len(visited):
        return False,len(visited)
    return touchAnyNodes(newVisited,graph,infected)


class Solution(object):
    def minMalwareSpread(self, graph, initial):
        # 1. Color each component.
        # colors[node] = the color of this node.

        N = len(graph)
        colors = {}
        c = 0

        def dfs(node, color):
            colors[node] = color
            for nei, adj in enumerate(graph[node]):
                if adj and nei not in colors:
                    dfs(nei, color)

        for node in range(N):
            if node not in colors:
                dfs(node, c)
                c += 1

        # 2. Size of each color.
        # size[color] = number of occurrences of this color.
        size = collections.Counter(colors.values())

        # 3. Find unique colors.
        color_count = collections.Counter()
        for node in initial:
            color_count[colors[node]] += 1

        # 4. Answer
        ans = float('inf')
        for x in initial:
            c = colors[x]
            if color_count[c] == 1:
                if ans == float('inf'):
                    ans = x
                elif size[c] > size[colors[ans]]:
                    ans = x
                elif size[c] == size[colors[ans]] and x < ans:
                    ans = x

        return ans if ans < float('inf') else min(initial)  

class Solution(object):
    def minMalwareSpread(self, graph, initial):
        def dfs(node, visited):
            for neighbor in range(len(graph[node])):
                if graph[node][neighbor] == 1 and neighbor not in visited:
                    visited.add(neighbor)
                    dfs(neighbor, visited)
        
        res, max_size = min(initial), 0
        i_set = set(initial)
        total_visited = set()
        for node in range(len(graph)):
            if node not in total_visited:
                visited = {node}
                dfs(node, visited)
                infected = visited & i_set
                if len(infected) == 1:
                    if len(visited) > max_size or (len(visited) == max_size and list(infected)[0] < res):
                        res = list(infected)[0]
                        max_size = len(visited)
                total_visited |= visited
        return res
                                                 


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        N = len(graph)
        colors = {}
        c = 0

        def dfs(node, color):
            colors[node] = color
            for nei, adj in enumerate(graph[node]):
                if adj and nei not in colors:
                    dfs(nei, color)

        for node in range(N):
            if node not in colors:
                dfs(node, c)
                c += 1

        size = collections.Counter(colors.values())

        color_count = collections.Counter()
        for node in initial:
            color_count[colors[node]] += 1

        ans = float('inf')
        for x in initial:
            c = colors[x]
            if color_count[c] == 1:
                if ans == float('inf'):
                    ans = x
                elif size[c] > size[colors[ans]]:
                    ans = x
                elif size[c] == size[colors[ans]] and x < ans:
                    ans = x

        return ans if ans < float('inf') else min(initial)    

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(node,vis):
            for v in  range(len(graph[node])):
                if graph[node][v] == 1 and v not in vis:
                    vis.add(v)
                    dfs(v,vis)

        s = set(initial)
        t_vis = set()
        del_node, subgraph_len = min(initial), 0
        for node in range(len(graph)):
            if node not in t_vis:
                vis = set([node])
                dfs(node,vis)
                # caculate the number of infected node in the subgraph
                infect = vis & s
                if len(infect) == 1:
                    # more number of nodes or smaller index
                    if len(vis) > subgraph_len or (len(vis) == subgraph_len and list(infect)[0] < del_node):
                        del_node,subgraph_len = list(infect)[0],len(vis)
                t_vis |= vis
        return del_node
#         def find(x):
#             if x != parents[x]:
#                 parents[x] = find(parents[x])
#             return parents[x]
        
#         def union(x, y):
#             parents[find(x)] = 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))
#         print(union)
#         malware = collections.Counter(find(i) for i in initial)
#         print(malware)
        
#         save, res = 0, min(initial)
#         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
        
#         # return min(initial, key=lambda x: [(malware[find(x)] == 1) * -union[find(x)], x])
                    
        


# from collections import deque
# import heapq

# class Solution:
#     def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
#         groups = {}
#         group_counter = 0
        
#         contains_malware = []
#         malware_set = set(initial)
        
#         visited = set()
#         for i in range(len(graph)):
#             group_counter += 1
#             if i not in visited:
#                 queue = deque()
#                 queue.append(i)
#                 while queue:
#                     node = queue.popleft()
#                     visited.add(node)
#                     if node in malware_set:
#                         contains_malware.append((node, group_counter))
#                     if group_counter not in groups:
#                             groups[group_counter] = 1
#                     else:
#                         groups[group_counter] += 1
#                     for candidate_node, flag in enumerate(graph[node]):
#                         if flag == 1 and candidate_node not in visited:
#                             queue.append(candidate_node)
                            
                            
#         if len(initial) == len(graph):
#             individuals = []
#             for node, i in contains_malware:
#                 if groups[i] == 1:
#                     individuals.append(node)
#             individuals.sort()
#             return individuals[0]
#         else:
#             contains_malware = [(-groups[i], node) for node, i in contains_malware]
#             heapq.heapify(contains_malware)
#             return contains_malware[0][1]
                        
import collections
class Solution(object):
    def minMalwareSpread(self, graph, initial):
        # 1. Color each component.
        # colors[node] = the color of this node.

        N = len(graph)
        colors = {}
        c = 0

        def dfs(node, color):
            colors[node] = color
            for nei, adj in enumerate(graph[node]):
                if adj and nei not in colors:
                    dfs(nei, color)

        for node in range(N):
            if node not in colors:
                dfs(node, c)
                c += 1

        # 2. Size of each color.
        # size[color] = number of occurrences of this color.
        size = collections.Counter(list(colors.values()))

        # 3. Find unique colors.
        color_count = collections.Counter()
        for node in initial:
            color_count[colors[node]] += 1

        # 4. Answer
        ans = float('inf')
        for x in initial:
            c = colors[x]
            if color_count[c] == 1:
                if ans == float('inf'):
                    ans = x
                elif size[c] > size[colors[ans]]:
                    ans = x
                elif size[c] == size[colors[ans]] and x < ans:
                    ans = x

        return ans if ans < float('inf') else min(initial)  


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        parents = {}
        
        def find(parents, i):
            c = i
            while parents[c] != c:
                c = parents[c]
            parents[i] = c
            return c
        
        def union(parents, i, j):
            parents[find(parents, i)] = find(parents, j)
            
        for u in range(len(graph)):
            if u not in parents:
                parents[u] = u
            for v in range(len(graph[u])):
                if v not in parents:
                    parents[v] = v
                if graph[u][v] == 1:
                    union(parents, u, v)
        
        malware_count = collections.defaultdict(int)
        for i in initial:
            malware_count[find(parents, i)] += 1
        comp_size = collections.defaultdict(int)
        for k in parents.keys():
            comp_size[find(parents, k)] += 1

        largest_comp = None
        largest_size = 0
        for i in initial:
            k = find(parents, i)
            v = malware_count[k]
            if v == 1:
                if comp_size[k] > largest_size:
                    largest_size = comp_size[k]
                    largest_comp = [i]
                elif comp_size[k] == largest_size:
                    largest_comp.append(i)
        if largest_comp:
            return min(largest_comp)
        return min(initial)

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        colors = {}
        c = 0
        def dfs(node, graph, c):
            colors[node]=c
            for nei,adj in enumerate(graph[node]):
                if adj and nei not in colors:
                    dfs(nei, graph, c)
        # group into colors
        for i in range(len(graph)):
            if i not in colors:
                dfs(i, graph, c)
                c+=1
        size = collections.Counter(list(colors.values()))
        # group nodes from initial to have unique color
        init_count = collections.defaultdict(int)
        for node in initial:
            init_count[colors[node]]+=1
        # find ans
        ans = float('inf')
        for x in initial:
            if init_count[colors[x]]==1:
                if ans==float('inf'):
                    ans = x
                elif size[colors[x]]>size[colors[ans]]:
                    ans = x
                elif size[colors[x]]==size[colors[ans]] and x<ans:
                    ans = x
        return ans if ans!=float('inf') else min(initial)
        



class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        s = set(initial)
        go_visit = set()
        del_node, length = min(initial), 0
        def helper(node, visit):
            for i in range(len(graph[node])):
                if graph[node][i] == 1 and i not in visit:
                    visit.add(i)
                    helper(i, visit)
        for node in range(len(graph)):
            if node not in go_visit:
                visit = set()
                visit.add(node)
                helper(node, visit)
                temp = visit & s
                if len(temp) == 1:
                    if length < len(visit) or (length == len(visit) and list(temp)[0] < del_node):
                        del_node = list(temp)[0]
                        length = len(visit)
                go_visit |= visit
        return del_node
                    


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def method1():
            N=len(graph)
            colors={}
            c=0
            
            def dfs(node,color):
                colors[node]=color
                for nei,adj in enumerate(graph[node]):
                    if adj==1 and nei not in colors:
                        dfs(nei,color)
            
            for node in range(N):
                if node not in colors:
                    dfs(node,c)
                    c+=1
                    
            size=collections.Counter(colors.values())
            
            color_count=collections.Counter()
            for node in initial:
                color_count[colors[node]]+=1
                
            
            ans=float('inf')
            for initial_node in initial:
                c=colors[initial_node]
                if color_count[c]==1:
                    if ans==float('inf'):
                        ans=initial_node
                    elif size[c]>size[colors[ans]]:
                        ans=initial_node
                    elif size[c]==size[colors[ans]] and initial_node<ans:
                        ans=initial_node
            
            return ans if ans<float('inf') else min(initial)
        #return method1()
    
        
        def method2():
            def dfs(node,vis):
                for v in  range(len(graph[node])):
                    if graph[node][v] == 1 and v not in vis:
                        vis.add(v)
                        dfs(v,vis)

            s = set(initial)
            seen = set()
            del_node, subgraph_len = min(initial), 0
            for node in range(len(graph)):
                if node not in seen:
                    vis = set([node])
                    dfs(node,vis)
                    # caculate the number of infected node in the subgraph
                    infect = vis & s
                    if len(infect) == 1:
                        # more number of nodes or smaller index
                        if len(vis) > subgraph_len or (len(vis) == subgraph_len and list(infect)[0] < del_node):
                            del_node,subgraph_len = list(infect)[0],len(vis)
                    seen |= vis
            return del_node
        
        return method2()

class DSU():
    
    def __init__(self):
        self.parent={}
        self.size={}
    
    def find(self,x):
        if x!=self.parent[x]:
            self.parent[x]=self.find(self.parent[x])
        return self.parent[x]
    
    def union(self,x,y):
        xp,yp=self.find(x),self.find(y)
        if xp==yp:
            return False
        if self.size[xp]<self.size[yp]:
            xp,yp=yp,xp
        
        self.size[xp]+=self.size[yp]
        self.parent[yp]=xp
        return True

    def add_node(self,x):
        self.parent[x]=x
        self.size[x]=1


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        initial.sort()
        edges=[]
        for i in range(len(graph)):
            for j in range(i+1,len(graph[0])):
                if graph[i][j]:edges.append([i,j])
        
        dsu=DSU()
        for i in range(len(graph)):
            dsu.add_node(i)
            
        for e1,e2 in edges:
            if e1!=e2: dsu.union(e1,e2)
        ans=initial[0]
        m=len(graph)+1
        for i in initial:
            
            mt=self.get_max_size(initial,dsu,i)
            if mt<m:
                m=mt
                ans=i
        return ans
        
    
    def get_max_size(self,initial,dsu,di):
        x=0
        parents=set([])
        for i in initial:
            if i!=di:
                parents.add(dsu.find(i))
        
        for n in dsu.parent:
            if dsu.find(n) in parents:
                x+=1
        return x
        
        
            
        


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        # DFS: O(N^2) Time, O(N) Space
        # Tricky: [[1,1,0],[1,1,0],[0,0,1]], [0,1,2] -> If we remove 0, 1 can still infect 0 and we end up with 3 infected nodes. If we remove 2, we end up with 2 infected nodes -> SO we cant remove the node with the highest number of neighbors
        # New algorithm: We need to know which nodes are in the same component -> then no point in removing them since the other nodes would still infect it eventually
        
        # 1. Color each component
        # colors[node] = the color of this node.
        sizeComponents = defaultdict(int)
        nodesToComponents = defaultdict(int)
        c = 0
        def dfs(node, c):
            sizeComponents[c] += 1
            nodesToComponents[node] = c
            for neighbor in range(len(graph[node])):
                if graph[node][neighbor] == 1 and node != neighbor:
                    if neighbor not in nodesToComponents:
                        dfs(neighbor, c)
                        
                    
        for node in range(len(graph)):
            if node not in nodesToComponents:
                dfs(node, c)
                c += 1
        
        # 2. Map initial node to the size of their components
        # initialComponents = defaultdict(int)
        # for node in initial:
        #     component = nodesToComponents[node]
        #     initialComponents[node] = sizeComponents[component]
        
        # 2. Apparently, the question wants you to find which nodes in initial are in unique components
        initialComponents = defaultdict(int)
        for node in initial:
            component = nodesToComponents[node]
            initialComponents[component] += 1
            
        # 3. Find node with unique component, i.e. size of component == 1
        res = float('inf')
        for node in initial:
            component = nodesToComponents[node]
            size = sizeComponents[component]
            if initialComponents[component] == 1: # if this is the only
                if res == float('inf'):
                    res = node
                elif size > sizeComponents[nodesToComponents[res]]:
                    res = node
                elif size == sizeComponents[nodesToComponents[res]] and node < res:
                    res = node

        return res if res < float('inf') else min(initial)    

class Solution(object):
    def minMalwareSpread(self, graph, initial):
        def dfs(node,vis):
            for v in  range(len(graph[node])):
                if graph[node][v] == 1 and v not in vis:
                    vis.add(v)
                    dfs(v,vis)

        s = set(initial)
        t_vis = set()
        del_node, subgraph_len = min(initial), 0
        for node in range(len(graph)):
            if node not in t_vis:
                vis = set([node])
                dfs(node,vis)
                # print(vis)
                # caculate the number of infected node in the subgraph
                infect = vis & s
                # print(\"infect: \", infect)
                if len(infect) == 1:
                    # more number of nodes or smaller index
                    if len(vis) > subgraph_len or (len(vis) == subgraph_len and list(infect)[0] < del_node):
                        del_node,subgraph_len = list(infect)[0],len(vis)
                t_vis |= vis
                # print(t_vis)
        return del_node

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        def dfs(node):
            nodes.add(node)
            for i in range(len(graph[node])):
                if i not in nodes and graph[node][i] == 1:
                    dfs(i)
        
        rank, initial = collections.defaultdict(list), set(initial)
        for node in initial:
            nodes = set()
            dfs(node)
            #print(\"For initial node:\", node, \"the set is:\", nodes, 
            #     \"intersection is:\", sorted(nodes & initial))
            if len(nodes & initial) == 1:
                rank[len(nodes)].append(node)
        #print(\"Rank is:\", rank)
        return rank[max(rank)][0] if rank else min(initial)


class DisjointSetUnion:
    def __init__(self):
        self._parent = {}
        self._size = {}
    
    def union(self, a: int, b: int) -> None:
        a, b = self.find(a), self.find(b)
        if a == b:
            return
        if self._size[a] < self._size[b]:
            a, b = b, a
        self._parent[b] = a
        self._size[a] += self._size[b]
    
    def find(self, x: int) -> int:
        if x not in self._parent:
            self._parent[x] = x
            self._size[x] = 1
            return x
        
        while self._parent[x] != x:
            self._parent[x] = self._parent[self._parent[x]]
            x = self._parent[x]
        
        return self._parent[x]
    
    def size(self, x: int) -> int:
        return self._size[self.find(x)]
    
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        dsu = DisjointSetUnion()
        
        for u, neighborhood in enumerate(graph):
            for v, is_connected in enumerate(neighborhood):
                if is_connected:
                    dsu.union(u, v)
        
        parent_count = collections.Counter(dsu.find(u) for u in initial)
        best_index = best_count = -1
        
        for index in initial:
            count = dsu.size(index) if parent_count[dsu.find(index)] == 1 else 0
            
            if count > best_count or (count == best_count and index < best_index):
                best_index, best_count = index, count
        
        return best_index

from collections import deque 
class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        if graph is None or len(graph) ==0 or len(graph[0]) ==0 or len(initial) ==0:
            return None 
    
        n = len(graph)
        m = len(graph[0])
        k = len(initial)
        initial.sort()
        
                        
        result = sys.maxsize 
        idx = None 
        for i in range(k):
            temp_q = initial[:]
            temp_q.pop(i)
            temp_q = deque(temp_q)
            temp_visited = set(temp_q)
            
            self.helper(graph, temp_q, temp_visited)
            if result > len(temp_visited):
                result = len(temp_visited)
                idx = initial[i]
        
        return idx 
    
    def helper(self, graph, temp_q, temp_visited):
        
        n, m = len(graph), len(graph[0])
        
        while temp_q:
            curr = temp_q.popleft()
            for col in range(m):
                if col in temp_visited or graph[curr][col] ==0:
                    continue 
                temp_visited.add(col)
                temp_q.append(col)
        
                    
        
            
            
            
        
        
            
           
          
        
        
        
        


class Solution:

    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        class UF():
            def __init__(self, keys):
                self.uf = {}
                for key in keys:
                    self.uf[key] = key

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

            def union(self, x, y):
                xx = self.find(x)
                yy = self.find(y)
                self.uf[xx] = yy
        uf = UF(range(len(graph)))
        for i in range(len(graph)):
            for j in range(len(graph[i])):
                if graph[i][j] == 1:
                    uf.union(i, j)
        ct = collections.Counter([uf.find(x) for x in range(len(graph))])
        ct2 = collections.Counter([uf.find(x) for x in initial])
        initial.sort()
        ret = initial[0]
        score = 0
        for idx in initial:
            parent = uf.find(idx)
            if ct2[parent] > 1:
                continue
            if ct[parent] > score:
                score = ct[parent]
                ret = idx
        return ret