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 ; Given number of vertices and edges ; Given edges ; Given cost of coloring and adding an edge ; Given array of colored vertices
function DFS ( U , vis , adj ) { vis [ U ] = 1 ; for ( var V of adj [ U ] ) { if ( vis [ V ] == 0 ) DFS ( V , vis , adj ) ; } } function minCost ( N , M , vCost , eCost , sorc , colored , destination ) { var adj = [ ] ; for ( var i = 0 ; i < N + 1 ; i ++ ) adj . push ( new Array ( ) ) ; for ( var i = 0 ; i < M ; i ++ ) { ( adj [ sorc [ i ] ] ) . push ( destination [ i ] ) ; ( adj [ destination [ i ] ] ) . push ( sorc [ i ] ) ; } var vis = Array ( N + 1 ) . fill ( 0 ) ; for ( var i = 0 ; i < colored . length ; i ++ ) { DFS ( colored [ i ] , vis , adj ) ; } var X = 0 ; for ( var i = 1 ; i <= N ; i ++ ) { if ( vis [ i ] == 0 ) { X ++ ; DFS ( i , vis , adj ) ; } } var mincost = X * Math . min ( vCost , eCost ) ; document . write ( mincost ) ; } var N = 3 , M = 1 ; var sorc = [ 1 ] ; var destination = [ 2 ] ; var vCost = 3 , eCost = 2 ; var colored = [ ] ; colored . push ( 1 ) ; minCost ( N , M , vCost , eCost , sorc , colored , destination ) ;