Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
1.5 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"
 
const double PI = 3.14159265358979;
const ll INF =  1e9 + 7;
const ll MOD = 1e9 + 7;
const ll nax = 2505;
const int LOG = 25;

vector<int> par, sz;

int getParent(int x) {
    return x == par[x] ? x : par[x] = getParent(par[x]);
}

void mergeGroups(int x, int y) {
    x = getParent(x);
    y = getParent(y);

    if (x == y) {
        return;
    }

    if (sz[x] < sz[y]) {
        par[x] = y;
        sz[y] += sz[x];
    } else {
        par[y] = x;
        sz[x] += sz[y];
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    par.assign(n + 1, 0);
    sz.assign(n + 1, 1);

    for (int i = 1; i <= n; i++) {
        par[i] = i;
    }

    vector<pair<int, pair<int, int> > > edges;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        edges.push_back({w, {u, v}});
    }

    sort(edges.begin(), edges.end());
    ll ans = 0, totalEdges = 0;

    for (auto &edge: edges) {
        int w = edge.first;
        int u = edge.second.first;
        int v = edge.second.second;

        if (getParent(u) != getParent(v)) {
            mergeGroups(u, v);
            totalEdges++;
            ans += w;
        }
    }

    if (totalEdges == n - 1) {
        cout << ans;
    } else {
        cout<< "IMPOSSIBLE";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // int t; cin >> t; while(t--)
    solve();
    return 0;
}
Leave a Comment