Cod sursa(job #2870552)

Utilizator VipioanaMirea Oana Teodora Vipioana Data 12 martie 2022 13:53:36
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <bitset>
#define inf 1000000001
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
const int N=2e5+1,M=4e5+1;
int n,m,cost,t[N],nr[N];
vector <pair<int,int>> sol;

struct ura{
    int x,y,c;
}a[M];

bool cmp(ura a, ura b){
    return a.c<b.c;
}

int radacina(int x){
    if(t[x]==0)
        return x;
    t[x]=radacina(t[x]);
    return t[x];
}

void join(int x, int y){
    int tx=radacina(x);
    int ty=radacina(y);
    if(nr[tx]>nr[ty]){
        t[ty]=tx;
        nr[tx]+=nr[ty];
    }else{
        t[tx]=ty;
        nr[ty]+=nr[tx];
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
        cin>>a[i].x>>a[i].y>>a[i].c;
    int i=1,nrm=0;
    sort(a+1,a+m+1,cmp);
    while(i<=m && nrm<n-1){
        if(radacina(a[i].x)!=radacina(a[i].y)){
            join(a[i].x,a[i].y);
            cost+=a[i].c;
            nrm++;
            sol.push_back({a[i].x,a[i].y});
        }
        i++;
    }
    cout<<cost<<'\n'<<sol.size()<<'\n';
    for(auto j:sol)
        cout<<j.first<<" "<<j.second<<'\n';
    return 0;
}