// Did this code successfully run on Leetcode : Yes
// Any problem you faced while coding this : None


// Your code here along with comments explaining your approach:
In this problem given the intial nodes which are malware affected.we can cure one of the inital nodes and we have to find the max number of nodes that can be saved from getting affected.
Graph is given as adjacency matrix.
This problem follows the following steps:
in a graph if more than two nodes are affected then malware cannot be stopped.
If multiple sub graphs in the same graph has malware affcted nodes as 1,then we cure the one which has more number of nodes to maximize the number of nodes to protect.
Inorder to apply the above logic in this problem,we go with graph coloring.it is coloring the connected graphs with same color.
1)we first construct an array which tells us the coloring of the input graph as in which components are connected to each other.
2)we then see how many number of nodes are present for a given color.
3)we see in which color does these nodes in the inital are present (i.e malware infected nodes).
4)If for a particular color if the number of malware affected nodes are >=2 then we know that the nodes in that graph cannot be cured then we return the lowest malware affected node.
5)If the number of malware affected nodes are 1 then  we return the node count where it is greater.


# Time complexity --> o(n*n) where n-->length of the graph
# space complexity --> o(n)
class Solution:
    def dfs(self,graph,colors,u,color_to_color):
        colors[u]=color_to_color
        for neig in range(len(graph)):
            if graph[u][neig]==1 and colors[neig]==-1:
                self.dfs(graph,colors,neig,color_to_color)
        
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        n=len(graph)
        colors=[-1 for i in range(n)]
        color_to_color=0
        #coloring the given nodes if connected with the same color else with different color.
        for u in range(n):
            if colors[u]==-1:
                colors[u]=color_to_color
                self.dfs(graph,colors,u,color_to_color)
                # print(colors)        
                color_to_color=color_to_color+1
        colored_node_count=[0 for i in range(color_to_color)]
        #counting the number of nodes for a particular color.
        for color in range(n):
            colored_node_count[colors[color]]=colored_node_count[colors[color]]+1
        
        #keeping a track of the malware affected nodes  comes under which color.
        infected_nodes_color_count=[0 for i in range(color_to_color)]
        for node in initial:
            infected_nodes_color_count[colors[node]]=infected_nodes_color_count[colors[node]]+1
        
        #we traversed through the malware affected nodes and check the count of affected nodes in the sub graph.If  multiple sub graphs has infected node count as 1.
        cureindex=float('inf')
        for i in initial:
            if infected_nodes_color_count[colors[i]]==1:
                if cureindex==float('inf'):
                    cureindex=i
                #If multiple nodes are having malware affected node count as 1 then we return the subgraph count which has more number of node count of the subgraphs which are having count as 1.
                elif colored_node_count[colors[i]]>colored_node_count[colors[cureindex]]:
                    cureindex=i
                #if malware affected node count==1 and the number of colored node count are equal then we return the node having less index out of the initial nodes.
                elif colored_node_count[colors[i]]==colored_node_count[colors[cureindex]]:
                    cureindex=min(i,cureindex)
        #If the malware affected node count is not equal to 1 that means that all nodes will be affected then as per question we return the lower index from the initial.
        if cureindex==float('inf'):
            return min(initial)
        return cureindex
        