Road Reparation

There are n cities and m roads between them. Unfortunately, the condition of the roads is so poor that they cannot be used. Your task is to repair some of the roads so that there will be a decent route between any two cities.

For each road, you know its reparation cost, and you should find a solution where the total cost is as small as possible.

Example:

Input: n = 5, m = 6, edges = {{1, 2, 3}, {2, 3, 5}, {2, 4, 2}, {3, 4, 8}, {5, 1, 7}, {5, 4, 4}}
Output: 14

Approach

C++

#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    long long a, b, w;
};
Edge arr[1000001];
long long parent[1000001];
long long size1[1000001];
long long find(long long a)
{
    if (a == parent[a])
        return a;
    return parent[a] = find(parent[a]);
}
void makeSet(long long n)
{
    for (long long i = 1; i <= n; i++)
    {
        parent[i] = i;
        size1[i] = 1;
    }
}
void union_set(long long a, long long b)
{
    a = find(a);
    b = find(b);
    if (a != b)
    {
        if (size1[a] < size1[b])
            swap(a, b);
        parent[b] = a;
        size1[a] += size1[b];
    }
}
bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}
int main()
{
    long long n = 5, m = 6;
    vector<vector<long long>> edges = {{1, 2, 3},
                                       {2, 3, 5},
                                       {2, 4, 2},
                                       {3, 4, 8},
                                       {5, 1, 7},
                                       {5, 4, 4}};
    makeSet(n);
    for (long long i = 1; i <= m; i++)
    {
        arr[i].a = edges[i - 1][0];
        arr[i].b = edges[i - 1][1];
        arr[i].w = edges[i - 1][2];
    }
    sort(arr + 1, arr + m + 1, cmp);
    long long ans = 0, cc_count = n;
    for (long long i = 1; i <= m; i++)
    {
        long long a = find(arr[i].a);
        long long b = find(arr[i].b);
        if (a != b)
        {
            ans += arr[i].w;
            union_set(a, b);
            cc_count--;
        }
    }
    if (cc_count != 1)
        cout << "IMPOSSIBLE\n";
    else
        cout << ans << "\n";

    return 0;
}