Minimum cost to connect a disconnected graph

Given a disconnected graph G with N vertices and M edges and cost[] for all the vertices, the task is to add edges to G to make it connected and to add an edge between vertices u to v the cost[u] and cost[v] must be greater than or equals to 0, and the cost to add this edge is cost[u] + cost[v], minimize the cost by making G connected or print -1 if it is not possible.

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
Expalantion:
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

Approach :

The idea is to use the disjoint set union data structure. The idea is to store all the minimum value which is 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 else 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:

1. Initialize a vector minVal[] to find the minimum element of every set.
2. Initialize the vectors parent(N+1), rank(N+1, 0), minVal(N+1).
3. Initialize a set, say s, to store the parent of every set.
4. Initialize a variable, say minCost, to store the minimum cost.
5. 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].
6. Iterate over the vector G using the variable i and call for function operation Union(parent, rank, minVal, i.first, i.second).
7. Iterate over the range [1, N+1) using the variable i and insert the parent element of I to s.
8. 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.
9. 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) and print the value of minCost else print -1.

Implementation :

// 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 set
int 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 union
void 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 condition
void findMinCost(vector<pair<int, int> >& G,
                 vector<int>& cost, int N, int M)
{

    // Stores the parent elements
    // of the 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 vlaue 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 the 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 Code
int 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;
}

3

Time Complexity : O(N*log M)
Auxiliary Space : O(N)