Cod sursa(job #3373075)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 6 noiembrie 2026 08:23:35
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m;

struct DSU
{
    int parent[200010];
    int size[200010];
    void construct(){
        for(int i = 1; i <= n; i++){
            parent[i] = i;
            size[i] = 1;
        }
    }
    int find(int x){
        while(parent[x] != x)
            x = parent[x];
        return x;
    }
    void unite(int a, int b){
        a = find(a);
        b = find(b);
        if(size[a] > size[b]) swap(a, b);
        size[b] += size[a];
        parent[a] = b;
    }
} dsu;

struct edge
{
    int a, b, w;
};
vector<edge> edges;

bool fsort(const struct edge x, const struct edge y)
{
    return x.w < y.w;
}

void kruskal()
{
    dsu.construct();
    vector<pair<int, int>> mste;
    int weight = 0;
    for(edge &e : edges) if(dsu.find(e.a) != dsu.find(e.b)){
        dsu.unite(e.a, e.b);
        mste.push_back({e.a, e.b});
        weight += e.w;
    }
    fout << weight << '\n' << mste.size() << '\n';
    for(pair<int, int> &e : mste)
        fout << e.first << ' ' << e.second << '\n';
}

int main()
{

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, w; fin >> a >> b >> w;
        edges.push_back({a, b, w});
    }
    sort(edges.begin(), edges.end(), fsort);
    kruskal();

    return 0;
}