Cod sursa(job #3371153)

Utilizator nisa21111Denisa Beleuzu nisa21111 Data 28 octombrie 2026 19:45:15
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
//ex 1
#include <bits/stdc++.h>
using namespace std;

int par[200005], sz[200005];

int find(int x) {
    while (par[x] != x) {
        par[x] = par[par[x]];
        x = par[x];
    }
    return x;
}

bool unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
    return true;
}

struct Edge {
    int x, y, c;
};

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    int n, m;
    fin >> n >> m;

    vector<Edge> e(m);
    for (auto &ed : e) fin >> ed.x >> ed.y >> ed.c;

    sort(e.begin(), e.end(), [](const Edge &a, const Edge &b) {
        return a.c < b.c;
    });

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

    long long total = 0;
    vector<pair<int, int>> chosen;
    chosen.reserve(n);

    for (const auto &ed : e) {
        if (unite(ed.x, ed.y)) {
            total += ed.c;
            chosen.push_back({ed.x, ed.y});
            if ((int)chosen.size() == n - 1) break;
        }
    }

    fout << total << "\n" << chosen.size() << "\n";
    for (auto &p : chosen) fout << p.first << " " << p.second << "\n";

    return 0;
}