Given a disconnected graph G with N vertices and M edges and an array cost[] corresponding to each vertex, the task is to find the minimum cost to make the graph by connecting any pairs of vertices having the cost of vertices at least 0 and the cost of connecting those pair of vertices is the sum of the cost of individual vertices. If it is impossible, then print “-1”.
Examples:
Input: N = 6, G[] = {{3, 1}, {2, 3}, {2, 1}, {4, 5}, {5, 6}, {6, 4}}, cost[] = {2, 1, 5, 3, 2, 9}
Output: 3
Explanation: The initial graph has two connected components – {1, 2, 3} and {4, 5, 6}. We can add an edge between 2 to 5 at a cost of cost[2] + cost[5] = 1 + 2 = 3. After adding this edge, the whole graph is connected.Input: N = 6, G[] = {{3, 1}, {2, 3}, {2, 1}, {4, 5}, {5, 6}, {6, 4}}, cost[] = {2, 1, 5, -3, -2, -9}
Output: -1
Explanation: It is not possible to make the graph connected
Approach: The given problem can be solved using the Disjoint Set Union data structure. The idea is to store all the minimum values which are greater than or equals to 0, say minVal[] for all the different connected components, and check if any value in minVal[] is less than zero if it is true then print -1, Otherwise, find the minimum value in minVal[], say min, and find the sum of all the minimum values with the min value and print the answer.
Follow the below steps to solve the problem:
- Initialize a vector minVal[] to find the minimum element of every set.
- Initialize the vectors parent(N+1), rank(N+1, 0), minVal(N+1).
- Initialize a set, say s, to store the parent of every set.
- Initialize a variable, say minCost, that stores the minimum cost.
- Iterate over the range [1, N+1) using the variable i and set the value of parent[i] as I and minVal[i] as cost[i – 1].
- Iterate over the vector G using the variable i and call for function operation Union(parent, rank, minVal, i.first, i.second).
- Iterate over the range [1, N+1) using the variable i and insert the parent element of I to s.
- Iterate over the set s and find the minimum value of s and store it in min and mark flag as true if any value is negative.
- If the given graph is already connected or the flag value is false then:
- Iterate over the s using the variable I and if min value is not equal to I then update the value of minCost to minCost += (minVal[i] + min.second).
- After completing the above step, print the value of minCost as the resultant minimum cost.
- Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to perform the find operation// to find the parent of a disjoint setint Find(vector<int>& parent, int a){ return parent[a] = (parent[a] == a ? a : Find(parent, parent[a]));}// FUnction to perform union operation// of disjoint set unionvoid Union(vector<int>& parent, vector<int>& rank, vector<int>& minVal, int a, int b){ a = Find(parent, a); b = Find(parent, b); if (rank[a] == rank[b]) rank[a]++; if (rank[a] > rank[b]) { parent[b] = a; // Update the minimum value // such than it should be // greater than 0 if (minVal[a] >= 0 && minVal[b] >= 0) { minVal[a] = min(minVal[a], minVal[b]); } else if (minVal[a] >= 0 && minVal[b] < 0) { minVal[a] = minVal[a]; } else if (minVal[a] < 0 && minVal[b] >= 0) { minVal[a] = minVal[b]; } else { minVal[a] = max(minVal[a], minVal[b]); } } else { parent[a] = b; // Update the minimum value // such than it should be // greater than 0 if (minVal[a] >= 0 && minVal[b] >= 0) { minVal[b] = min(minVal[a], minVal[b]); } else if (minVal[a] >= 0 && minVal[b] < 0) { minVal[b] = minVal[a]; } else if (minVal[a] < 0 && minVal[b] >= 0) { minVal[b] = minVal[b]; } else { minVal[b] = max(minVal[a], minVal[b]); } }}// Function to minimize the cost to// make the graph connected as per// the given conditionvoid findMinCost(vector<pair<int, int> >& G, vector<int>& cost, int N, int M){ // Stores the parent elements of sets vector<int> parent(N + 1); // Stores the rank of the sets vector<int> rank(N + 1, 0); // Stores the minValue of the sets vector<int> minVal(N + 1); for (int i = 1; i < N + 1; i++) { // Update parent[i] to i parent[i] = i; // Update minValue[i] to cost[i-1] minVal[i] = cost[i - 1]; } for (auto i : G) { // Add i.first and i.second // elements to the same set Union(parent, rank, minVal, i.first, i.second); } // Stores the parent elements of // the different components set<int> s; for (int i = 1; i < N + 1; i++) { // Insert parent of i to s s.insert(Find(parent, i)); } // Stores the minimum value from s pair<int, int> min = { 0, INT_MAX }; // Flag to mark if any minimum // value is negative bool flag = false; for (auto i : s) { // If minVal[i] is negative if (minVal[i] < 0) { // Mark flag as true flag = true; } if (min.second > minVal[i]) { // Update the minimum value min = { i, minVal[i] }; } } // Stores minimum cost to add the edges int minCost = 0; // If the given graph is connected // or components minimum values not // having any negative edge if (!flag || (flag && s.size() == 1)) { for (auto i : s) { if (i != min.first) { // Update the minCost minCost += (minVal[i] + min.second); } } // Print the value of minCost cout << minCost << endl; } else { // Print -1 cout << -1 << endl; }}// Driver Codeint main(){ int N = 6; vector<pair<int,int>> G = { { 3, 1 }, { 2, 3 }, { 2, 1 }, { 4, 5 }, { 5, 6 }, { 6, 4 } }; vector<int> cost{ 2, 1, 5, 3, 2, 9 }; int M = G.size(); findMinCost(G, cost, N, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static class pair { int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to perform the find operation// to find the parent of a disjoint setstatic int Find(int[] parent, int a){ return parent[a] = (parent[a] == a ? a : Find(parent, parent[a]));}// FUnction to perform union operation// of disjoint set unionstatic void Union(int [] parent, int [] rank, int [] minVal, int a, int b){ a = Find(parent, a); b = Find(parent, b); if (rank[a] == rank[b]) rank[a]++; if (rank[a] > rank[b]) { parent[b] = a; // Update the minimum value // such than it should be // greater than 0 if (minVal[a] >= 0 && minVal[b] >= 0) { minVal[a] = Math.min(minVal[a], minVal[b]); } else if (minVal[a] >= 0 && minVal[b] < 0) { minVal[a] = minVal[a]; } else if (minVal[a] < 0 && minVal[b] >= 0) { minVal[a] = minVal[b]; } else { minVal[a] = Math.max(minVal[a], minVal[b]); } } else { parent[a] = b; // Update the minimum value // such than it should be // greater than 0 if (minVal[a] >= 0 && minVal[b] >= 0) { minVal[b] = Math.min(minVal[a], minVal[b]); } else if (minVal[a] >= 0 && minVal[b] < 0) { minVal[b] = minVal[a]; } else if (minVal[a] < 0 && minVal[b] >= 0) { minVal[b] = minVal[b]; } else { minVal[b] = Math.max(minVal[a], minVal[b]); } }}// Function to minimize the cost to// make the graph connected as per// the given conditionstatic void findMinCost(pair[] G, int [] cost, int N, int M){ // Stores the parent elements of sets int [] parent = new int[N + 1]; // Stores the rank of the sets int [] rank = new int[N + 1]; // Stores the minValue of the sets int [] minVal = new int[N + 1]; for (int i = 1; i < N + 1; i++) { // Update parent[i] to i parent[i] = i; // Update minValue[i] to cost[i-1] minVal[i] = cost[i - 1]; } for (pair i : G) { // Add i.first and i.second // elements to the same set Union(parent, rank, minVal, i.first, i.second); } // Stores the parent elements of // the different components HashSet<Integer> s = new HashSet<Integer>(); for (int i = 1; i < N + 1; i++) { // Insert parent of i to s s.add(Find(parent, i)); } // Stores the minimum value from s pair min = new pair( 0, Integer.MAX_VALUE ); // Flag to mark if any minimum // value is negative boolean flag = false; for (int i : s) { // If minVal[i] is negative if (minVal[i] < 0) { // Mark flag as true flag = true; } if (min.second > minVal[i]) { // Update the minimum value min = new pair( i, minVal[i] ); } } // Stores minimum cost to add the edges int minCost = 0; // If the given graph is connected // or components minimum values not // having any negative edge if (!flag || (flag && s.size() == 1)) { for (int i : s) { if (i != min.first) { // Update the minCost minCost += (minVal[i] + min.second); } } // Print the value of minCost System.out.print(minCost +"\n"); } else { // Print -1 System.out.print(-1 +"\n"); }}// Driver Codepublic static void main(String[] args){ int N = 6; pair []G = { new pair( 3, 1 ), new pair( 2, 3 ), new pair( 2, 1 ), new pair( 4, 5 ), new pair( 5, 6 ), new pair( 6, 4 ) }; int[] cost = { 2, 1, 5, 3, 2, 9 }; int M = G.length; findMinCost(G, cost, N, M);}}// This code is contributed by 29AjayKumar |
Python3
# Python 3 program for the above approachimport sys# Function to perform the find operation# to find the parent of a disjoint setdef Find(parent, a): if parent[parent[a]] != parent[a]: parent[a] = Find(parent, parent[a]) return parent[a]# FUnction to perform union operation# of disjoint set uniondef Union(parent, rank, minVal, a, b): a = Find(parent, a) b = Find(parent, b) if (rank[a] == rank[b]): rank[a] += 1 if (rank[a] > rank[b]): parent[b] = a # Update the minimum value # such than it should be # greater than 0 if (minVal[a] >= 0 and minVal[b] >= 0): minVal[a] = min(minVal[a],minVal[b]) elif(minVal[a] >= 0 and minVal[b] < 0): minVal[a] = minVal[a] elif(minVal[a] < 0 and minVal[b] >= 0): minVal[a] = minVal[b] else: minVal[a] = max(minVal[a],minVal[b]) else: parent[a] = b # Update the minimum value # such than it should be # greater than 0 if (minVal[a] >= 0 and minVal[b] >= 0): minVal[b] = min(minVal[a],minVal[b]) elif(minVal[a] >= 0 and minVal[b] < 0): minVal[b] = minVal[a] elif(minVal[a] < 0 and minVal[b] >= 0): minVal[b] = minVal[b] else: minVal[b] = max(minVal[a],minVal[b])# Function to minimize the cost to# make the graph connected as per# the given conditiondef findMinCost(G,cost,N, M): # Stores the parent elements of sets parent = [0 for i in range(N + 1)] # Stores the rank of the sets rank = [0 for i in range(N + 1)] # Stores the minValue of the sets minVal = [0 for i in range(N + 1)] for i in range(1,N + 1,1): # Update parent[i] to i parent[i] = i # Update minValue[i] to cost[i-1] minVal[i] = cost[i - 1] for i in G: # Add i.first and i.second # elements to the same set Union(parent, rank, minVal, i[0], i[1]) # Stores the parent elements of # the different components s = set() for i in range(1,N + 1,1): # Insert parent of i to s s.add(Find(parent, i)) # Stores the minimum value from s min1 = [0, sys.maxsize] # Flag to mark if any minimum # value is negative flag = False for i in s: # If minVal[i] is negative if (minVal[i] < 0): # Mark flag as true flag = True if (min1[1] > minVal[i]): # Update the minimum value min1 = [i, minVal[i]] # Stores minimum cost to add the edges minCost = 0 # If the given graph is connected # or components minimum values not # having any negative edge if (flag == False or (flag and len(s) == 1)): for i in s: if (i != min1[0]): # Update the minCost minCost += (minVal[i] + min1[1]) # Print the value of minCost print(minCost) else: # Print -1 print(-1)# Driver Codeif __name__ == '__main__': N = 6 G = [[3, 1],[2, 3],[2, 1],[4, 5],[5, 6],[6, 4]] cost = [2, 1, 5, 3, 2, 9] M = len(G) findMinCost(G, cost, N, M) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ class pair { public int first, second; public pair(int first, int second) { this.first = first; this.second = second; } } // Function to perform the find operation// to find the parent of a disjoint setstatic int Find(int[] parent, int a){ return parent[a] = (parent[a] == a ? a : Find(parent, parent[a]));}// FUnction to perform union operation// of disjoint set unionstatic void Union(int [] parent, int [] rank, int [] minVal, int a, int b){ a = Find(parent, a); b = Find(parent, b); if (rank[a] == rank[b]) rank[a]++; if (rank[a] > rank[b]) { parent[b] = a; // Update the minimum value // such than it should be // greater than 0 if (minVal[a] >= 0 && minVal[b] >= 0) { minVal[a] = Math.Min(minVal[a], minVal[b]); } else if (minVal[a] >= 0 && minVal[b] < 0) { minVal[a] = minVal[a]; } else if (minVal[a] < 0 && minVal[b] >= 0) { minVal[a] = minVal[b]; } else { minVal[a] = Math.Max(minVal[a], minVal[b]); } } else { parent[a] = b; // Update the minimum value // such than it should be // greater than 0 if (minVal[a] >= 0 && minVal[b] >= 0) { minVal[b] = Math.Min(minVal[a], minVal[b]); } else if (minVal[a] >= 0 && minVal[b] < 0) { minVal[b] = minVal[a]; } else if (minVal[a] < 0 && minVal[b] >= 0) { minVal[b] = minVal[b]; } else { minVal[b] = Math.Max(minVal[a], minVal[b]); } }}// Function to minimize the cost to// make the graph connected as per// the given conditionstatic void findMinCost(pair[] G, int [] cost, int N, int M){ // Stores the parent elements of sets int [] parent = new int[N + 1]; // Stores the rank of the sets int [] rank = new int[N + 1]; // Stores the minValue of the sets int [] minVal = new int[N + 1]; for (int i = 1; i < N + 1; i++) { // Update parent[i] to i parent[i] = i; // Update minValue[i] to cost[i-1] minVal[i] = cost[i - 1]; } foreach (pair i in G) { // Add i.first and i.second // elements to the same set Union(parent, rank, minVal, i.first, i.second); } // Stores the parent elements of // the different components HashSet<int> s = new HashSet<int>(); for (int i = 1; i < N + 1; i++) { // Insert parent of i to s s.Add(Find(parent, i)); } // Stores the minimum value from s pair min = new pair( 0, int.MaxValue ); // Flag to mark if any minimum // value is negative bool flag = false; foreach (int i in s) { // If minVal[i] is negative if (minVal[i] < 0) { // Mark flag as true flag = true; } if (min.second > minVal[i]) { // Update the minimum value min = new pair( i, minVal[i] ); } } // Stores minimum cost to add the edges int minCost = 0; // If the given graph is connected // or components minimum values not // having any negative edge if (!flag || (flag && s.Count == 1)) { foreach (int i in s) { if (i != min.first) { // Update the minCost minCost += (minVal[i] + min.second); } } // Print the value of minCost Console.Write(minCost +"\n"); } else { // Print -1 Console.Write(-1 +"\n"); }}// Driver Codepublic static void Main(String[] args){ int N = 6; pair []G = { new pair( 3, 1 ), new pair( 2, 3 ), new pair( 2, 1 ), new pair( 4, 5 ), new pair( 5, 6 ), new pair( 6, 4 ) }; int[] cost = { 2, 1, 5, 3, 2, 9 }; int M = G.Length; findMinCost(G, cost, N, M);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approach// Function to perform the find operation// to find the parent of a disjoint setfunction Find(parent, a){ if(parent[parent[a]] != parent[a]) parent[a] = Find(parent, parent[a]) return parent[a]}// Function to perform union operation// of disjoint set unionfunction Union(parent, rank, minVal, a, b){ a = Find(parent, a) b = Find(parent, b) if (rank[a] == rank[b]) rank[a] += 1 if (rank[a] > rank[b]){ parent[b] = a // Update the minimum value // such than it should be // greater than 0 if (minVal[a] >= 0 && minVal[b] >= 0) minVal[a] = Math.min(minVal[a],minVal[b]) else if(minVal[a] >= 0 && minVal[b] < 0) minVal[a] = minVal[a] else if(minVal[a] < 0 && minVal[b] >= 0) minVal[a] = minVal[b] else minVal[a] = Math.max(minVal[a],minVal[b]) } else{ parent[a] = b // Update the minimum value // such than it should be // greater than 0 if (minVal[a] >= 0 && minVal[b] >= 0) minVal[b] = Math.min(minVal[a],minVal[b]) else if(minVal[a] >= 0 && minVal[b] < 0) minVal[b] = minVal[a] else if(minVal[a] < 0 && minVal[b] >= 0) minVal[b] = minVal[b] else minVal[b] = Math.max(minVal[a],minVal[b]) }}// Function to minimize the cost to// make the graph connected as per// the given conditionfunction findMinCost(G,cost,N, M){ // Stores the parent elements of sets let parent = new Array(N+1).fill(0) // Stores the rank of the sets let rank = new Array(N+1).fill(0) // Stores the minValue of the sets let minVal = new Array(N+1).fill(0) for(let i=1;i<N + 1;i++){ // Update parent[i] to i parent[i] = i // Update minValue[i] to cost[i-1] minVal[i] = cost[i - 1] } for(let i of G) // Add i.first && i.second // elements to the same set Union(parent, rank, minVal, i[0], i[1]) // Stores the parent elements of // the different components let s = new Set() for(let i=1;i<N + 1;i++) // Insert parent of i to s s.add(Find(parent, i)) // Stores the minimum value from s let min1 = [0, Number.MAX_VALUE] // Flag to mark if any minimum // value is negative let flag = false for(let i of s){ // If minVal[i] is negative if (minVal[i] <0) // Mark flag as true flag = true if (min1[1] > minVal[i]) // Update the minimum value min1 = [i, minVal[i]] } // Stores minimum cost to add the edges let minCost = 0 // If the given graph is connected // or components minimum values not // having any negative edge if (flag == false || (flag && s.length == 1)){ for(let i of s){ if (i != min1[0]) // Update the minCost minCost += (minVal[i] + min1[1]) } // Print the value of minCost document.write(minCost,"</0>") } else // Print -1 document.write(-1,"</br>")}// Driver Codelet N = 6let G = [[3, 1],[2, 3],[2, 1],[4, 5],[5, 6],[6, 4]]let cost = [2, 1, 5, 3, 2, 9]let M = G.lengthfindMinCost(G, cost, N, M)// This code is contributed by shinjanpatra</script> |
Output:
3
Time Complexity: O(N*log M)
Auxiliary Space: O(N)
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!
