Cod sursa(job #3373209)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 6 noiembrie 2026 12:36:56
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
int tati[200005];
vector<pair<int, int>>v;
struct lat
{
    int x, y, cost;
};
lat d[400005];
bool cmp(lat &a, lat &b)
{
    return(a.cost < b.cost);
}
int gasire(int x)
{
    if(tati[x] == x)return x;
    tati[x] = gasire(tati[x]);
    return tati[x];
}
void unire(int a, int b)
{
    a = gasire(a);
    b = gasire(b);
    if(a!=b)
    {
        tati[b] = a;
    }
}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m, k, j, c;
    cin >> n >> m;
    for(int i = 1; i<= n; i++)
    {
        tati[i] = i;
    }
    for(int i = 1; i<= m; i++)
    {
        cin >> k >> j >> c;
        d[i].x = k;
        d[i].y = j;
        d[i].cost = c;
    }
    sort(d+1, d+m+1, cmp);
    int cos = 0;
    int muc = 0;
    for(int i = 1; i<= m; i++)
    {
        int nr1 = d[i].x;
        int nr2 = d[i].y;
        if(gasire(nr1) != gasire(nr2))
        {
            cos+=d[i].cost;
            muc++;
            v.push_back({nr1, nr2});
            unire(nr1, nr2);
        }
        if(muc == n-1)break;
    }
    cout << cos << '\n';
    cout << v.size()<<'\n';
    for( auto i: v)
    {
        cout << i.first <<" "<< i.second <<'\n';
    }
    return 0;
}