Given two integers V and E representing the number of vertices and edges of an undirected graph G(V, E), a list of edges EdgeList, and an array A[] representing the cost to color each node, the task is to find the minimum cost to color the graph using the following operation:
When a node is colored, all the nodes that can be reached from it are colored without any additional cost.
Examples:
Input: V = 6, E = 5, A[] = {12, 25, 8, 11, 10, 7}, EdgeList = {{1, 2}, {1, 3}, {3, 2}, {2, 5}, {4, 6}}
Output: 15
Explanation:
On coloring the vertex 3 for a cost of 8, the vertices {1, 2, 5} gets colored at no additional cost.
On coloring the vertex 6 for a cost of 7, the only remaining vertex {4} also gets colored.
Therefore, the minimum cost = 8 + 7 = 15.Input: V =7, E = 6, A[] = {3, 5, 8, 6, 9, 11, 10}, EdgeList = {{1, 4}, {2, 1}, {2, 7}, {3, 4}, {3, 5}, {5, 6}}
Output: 5
Approach:
Follow the steps below to solve the problem:
- All the nodes are reachable from a given node form a Connected Component.
- So for each connected component, using Depth First Search, find the minimum cost node in a connected component of a graph.
Below is the implementation for the above approach:
C++
// C++ Program to find the minimum// cost to color all vertices of an// Undirected Graph#include <bits/stdc++.h>using namespace std;#define MAX 10vector<int> adj[MAX];// Function to add edge in the// given graphvoid addEdge(int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}// Function to perform DFS traversal and// find the node with minimum costvoid dfs(int v, int cost[], bool vis[], int& min_cost_node){ vis[v] = true; // Update the minimum cost min_cost_node = min(min_cost_node, cost[v - 1]); for (int i = 0; i < adj[v].size(); i++) { // Recur for all connected nodes if (vis[adj[v][i]] == false) { dfs(adj[v][i], cost, vis, min_cost_node); } }}// Function to calculate and return// the minimum cost of coloring all// vertices of the Undirected Graphint minimumCost(int V, int cost[]){ // Marks if a vertex is // visited or not bool vis[V + 1]; // Initialize all vertices as unvisited memset(vis, false, sizeof(vis)); int min_cost = 0; // Perform DFS traversal for (int i = 1; i <= V; i++) { // If vertex is not visited if (!vis[i]) { int min_cost_node = INT_MAX; dfs(i, cost, vis, min_cost_node); // Update minimum cost min_cost += min_cost_node; } } // Return the final cost return min_cost;}// Driver Codeint main(){ int V = 6, E = 5; int cost[] = { 12, 25, 8, 11, 10, 7 }; addEdge(1, 2); addEdge(1, 3); addEdge(3, 2); addEdge(2, 5); addEdge(4, 6); int min_cost = minimumCost(V, cost); cout << min_cost << endl; return 0;} |
Java
// Java program to find the minimum// cost to color all vertices of an// Undirected Graphimport java.util.*;class GFG{static final int MAX = 10;@SuppressWarnings("unchecked")static Vector<Integer> []adj = new Vector[MAX];static int min_cost_node;// Function to add edge in the// given graphstatic void addEdge(int u, int v){ adj[u].add(v); adj[v].add(u);}// Function to perform DFS traversal and// find the node with minimum coststatic void dfs(int v, int cost[], boolean vis[]){ vis[v] = true; // Update the minimum cost min_cost_node = Math.min(min_cost_node, cost[v - 1]); for(int i = 0; i < adj[v].size(); i++) { // Recur for all connected nodes if (vis[adj[v].get(i)] == false) { dfs(adj[v].get(i), cost, vis); } }}// Function to calculate and return// the minimum cost of coloring all// vertices of the Undirected Graphstatic int minimumCost(int V, int cost[]){ // Marks if a vertex is // visited or not boolean []vis = new boolean[V + 1]; // Initialize all vertices as unvisited Arrays.fill(vis, false); int min_cost = 0; // Perform DFS traversal for(int i = 1; i <= V; i++) { // If vertex is not visited if (!vis[i]) { min_cost_node = Integer.MAX_VALUE; dfs(i, cost, vis); // Update minimum cost min_cost += min_cost_node; } } // Return the final cost return min_cost;}// Driver Codepublic static void main(String[] args){ int V = 6, E = 5; int cost[] = { 12, 25, 8, 11, 10, 7 }; for(int i = 0; i < adj.length; i++) adj[i] = new Vector<Integer>(); addEdge(1, 2); addEdge(1, 3); addEdge(3, 2); addEdge(2, 5); addEdge(4, 6); int min_cost = minimumCost(V, cost); System.out.print(min_cost + "\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the minimum# cost to color all vertices of an# Undirected Graphimport sysMAX = 10adj = [[] for i in range(MAX)]# Function to add edge in the# given graphdef addEdge(u, v): adj[u].append(v) adj[v].append(u)# Function to perform DFS traversal and# find the node with minimum costdef dfs(v, cost, vis, min_cost_node): vis[v] = True # Update the minimum cost min_cost_node = min(min_cost_node, cost[v - 1]) for i in range(len(adj[v])): # Recur for all connected nodes if (vis[adj[v][i]] == False): min_cost_node = dfs(adj[v][i], cost, vis, min_cost_node) return min_cost_node # Function to calculate and return# the minimum cost of coloring all# vertices of the Undirected Graphdef minimumCost(V, cost): # Marks if a vertex is # visited or not vis = [False for i in range(V + 1)] min_cost = 0 # Perform DFS traversal for i in range(1, V + 1): # If vertex is not visited if (not vis[i]): min_cost_node = sys.maxsize min_cost_node = dfs(i, cost, vis, min_cost_node) # Update minimum cost min_cost += min_cost_node # Return the final cost return min_cost# Driver Codeif __name__=="__main__": V = 6 E = 5 cost = [ 12, 25, 8, 11, 10, 7 ] addEdge(1, 2) addEdge(1, 3) addEdge(3, 2) addEdge(2, 5) addEdge(4, 6) min_cost = minimumCost(V, cost) print(min_cost) # This code is contributed by rutvik_56 |
C#
// C# program to find the minimum// cost to color all vertices of an// Undirected Graphusing System;using System.Collections.Generic;class GFG{static readonly int MAX = 10;static List<int> []adj = new List<int>[MAX];static int min_cost_node;// Function to add edge in the// given graphstatic void addEdge(int u, int v){ adj[u].Add(v); adj[v].Add(u);}// Function to perform DFS traversal and// find the node with minimum coststatic void dfs(int v, int []cost, bool []vis){ vis[v] = true; // Update the minimum cost min_cost_node = Math.Min(min_cost_node, cost[v - 1]); for(int i = 0; i < adj[v].Count; i++) { // Recur for all connected nodes if (vis[adj[v][i]] == false) { dfs(adj[v][i], cost, vis); } }}// Function to calculate and return// the minimum cost of coloring all// vertices of the Undirected Graphstatic int minimumCost(int V, int []cost){ // Marks if a vertex is // visited or not bool []vis = new bool[V + 1]; int min_cost = 0; // Perform DFS traversal for(int i = 1; i <= V; i++) { // If vertex is not visited if (!vis[i]) { min_cost_node = int.MaxValue; dfs(i, cost, vis); // Update minimum cost min_cost += min_cost_node; } } // Return the readonly cost return min_cost;}// Driver Codepublic static void Main(String[] args){ int V = 6; int []cost = { 12, 25, 8, 11, 10, 7 }; for(int i = 0; i < adj.Length; i++) adj[i] = new List<int>(); addEdge(1, 2); addEdge(1, 3); addEdge(3, 2); addEdge(2, 5); addEdge(4, 6); int min_cost = minimumCost(V, cost); Console.Write(min_cost + "\n");}}// This code is contributed by Amit Katiyar |
Javascript
<script>// JavaScript Program to find the minimum// cost to color all vertices of an// Undirected Graphvar MAX = 10var adj = Array.from(Array(MAX), ()=> Array());// Function to add edge in the// given graphfunction addEdge(u, v){ adj[u].push(v); adj[v].push(u);}// Function to perform DFS traversal and// find the node with minimum costfunction dfs(v, cost, vis, min_cost_node){ vis[v] = true; // Update the minimum cost min_cost_node = Math.min(min_cost_node, cost[v - 1]); for (var i = 0; i < adj[v].length; i++) { // Recur for all connected nodes if (vis[adj[v][i]] == false) { min_cost_node = dfs(adj[v][i], cost, vis, min_cost_node); } } return min_cost_node;}// Function to calculate and return// the minimum cost of coloring all// vertices of the Undirected Graphfunction minimumCost(V, cost){ // Marks if a vertex is // visited or not var vis = Array(V + 1).fill(false); var min_cost = 0; // Perform DFS traversal for (var i = 1; i <= V; i++) { // If vertex is not visited if (!vis[i]) { var min_cost_node = 1000000000; min_cost_node = dfs(i, cost, vis, min_cost_node); // Update minimum cost min_cost += min_cost_node; } } // Return the final cost return min_cost;}// Driver Codevar V = 6, E = 5;var cost = [12, 25, 8, 11, 10, 7];addEdge(1, 2);addEdge(1, 3);addEdge(3, 2);addEdge(2, 5);addEdge(4, 6);var min_cost = minimumCost(V, cost);document.write( min_cost );</script> |
Output:
15
Time Complexity: O(V+E)
Auxiliary Space: O(V)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
