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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void DFS ( int U , int * vis , vector < int > adj [ ] ) { vis [ U ] = 1 ; for ( int V : adj [ U ] ) { if ( vis [ V ] == 0 ) DFS ( V , vis , adj ) ; } } void minCost ( int N , int M , int vCost , int eCost , int sorc [ ] , vector < int > colored , int destination [ ] ) { vector < int > adj [ N + 1 ] ; for ( int i = 0 ; i < M ; i ++ ) { adj [ sorc [ i ] ] . push_back ( destination [ i ] ) ; adj [ destination [ i ] ] . push_back ( sorc [ i ] ) ; } int vis [ N + 1 ] = { 0 } ; for ( int i = 0 ; i < colored . size ( ) ; i ++ ) { DFS ( 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 * min ( vCost , eCost ) ; cout << mincost << endl ; } int main ( ) { int N = 3 , M = 1 ; int sorc [ ] = { 1 } ; int destination [ ] = { 2 } ; int vCost = 3 , eCost = 2 ; vector < int > colored = { 1 } ; minCost ( N , M , vCost , eCost , sorc , colored , destination ) ; return 0 ; }