Minimize cost to color all the vertices of an Undirected Graph | C # program to implement the above approach ; 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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static void DFS ( int U , int [ ] vis , ArrayList adj ) { vis [ U ] = 1 ; foreach ( int V in ( ArrayList ) adj [ U ] ) { if ( vis [ V ] == 0 ) DFS ( V , vis , adj ) ; } } static void minCost ( int N , int M , int vCost , int eCost , int [ ] sorc , ArrayList colored , int [ ] destination ) { ArrayList adj = new ArrayList ( ) ; for ( int i = 0 ; i < N + 1 ; i ++ ) adj . Add ( new ArrayList ( ) ) ; for ( int i = 0 ; i < M ; i ++ ) { ( ( ArrayList ) adj [ sorc [ i ] ] ) . Add ( destination [ i ] ) ; ( ( ArrayList ) adj [ destination [ i ] ] ) . Add ( sorc [ i ] ) ; } int [ ] vis = new int [ N + 1 ] ; for ( int i = 0 ; i < colored . Count ; i ++ ) { DFS ( ( int ) colored [ i ] , vis , adj ) ; } int X = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( vis [ i ] == 0 ) { X ++ ; DFS ( i , vis , adj ) ; } } int mincost = X * Math . Min ( vCost , eCost ) ; Console . Write ( mincost ) ; } public static void Main ( string [ ] args ) { int N = 3 , M = 1 ; int [ ] sorc = { 1 } ; int [ ] destination = { 2 } ; int vCost = 3 , eCost = 2 ; ArrayList colored = new ArrayList ( ) ; colored . Add ( 1 ) ; minCost ( N , M , vCost , eCost , sorc , colored , destination ) ; } }