Minimize cost to color all the vertices of an Undirected Graph | Function to implement DFS Traversal to marks all the vertices visited from vertex U ; Mark U as visited ; Traverse the adjacency list of U ; Function to find the minimum cost to color all the vertices of graph ; To store adjacency list ; Loop through the edges to create adjacency list ; To check if a vertex of the graph is visited ; Mark visited to all the vertices that can be reached by colored vertices ; Perform DFS ; To store count of uncolored sub - graphs ; Loop through vertex to count uncolored sub - graphs ; If vertex not visited ; Increase count of uncolored sub - graphs ; Perform DFS to mark visited to all vertices of current sub - graphs ; Calculate minimum cost to color all vertices ; Print the result ; Driver Code ; Given number of vertices and edges ; Given edges ; Given cost of coloring and adding an edge ; Given array of colored vertices
def DFS ( U , vis , adj ) : NEW_LINE INDENT vis [ U ] = 1 NEW_LINE for V in adj [ U ] : NEW_LINE INDENT if ( vis [ V ] == 0 ) : NEW_LINE INDENT DFS ( V , vis , adj ) NEW_LINE DEDENT DEDENT DEDENT def minCost ( N , M , vCost , eCost , sorc , colored , destination ) : NEW_LINE INDENT adj = [ [ ] for i in range ( N + 1 ) ] NEW_LINE for i in range ( M ) : NEW_LINE INDENT adj [ sorc [ i ] ] . append ( destination [ i ] ) NEW_LINE adj [ destination [ i ] ] . append ( sorc [ i ] ) NEW_LINE DEDENT vis = [ 0 ] * ( N + 1 ) NEW_LINE for i in range ( len ( colored ) ) : NEW_LINE INDENT DFS ( colored [ i ] , vis , adj ) NEW_LINE DEDENT X = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( vis [ i ] == 0 ) : NEW_LINE INDENT X += 1 NEW_LINE DFS ( i , vis , adj ) NEW_LINE DEDENT DEDENT mincost = X * min ( vCost , eCost ) NEW_LINE print ( mincost ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE M = 1 NEW_LINE sorc = [ 1 ] NEW_LINE destination = [ 2 ] NEW_LINE vCost = 3 NEW_LINE eCost = 2 NEW_LINE colored = [ 1 ] NEW_LINE minCost ( N , M , vCost , eCost , sorc , colored , destination ) NEW_LINE DEDENT