Cod sursa(job #2979964)

Utilizator TanasaStefanTanasa Stefan TanasaStefan Data 16 februarie 2023 09:25:44
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int rang[100005] , t[100005], viz[100005] , n , m ;
long long s;

struct muchie
{
    int x , y , c;
}v[100005];

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

int radacina ( int nod)
{
    if(t[nod] == 0)
        return nod;
    else
    {
        int k = radacina(nod);
        t[nod] = k;
        return k;
    }
}

void unire(int a , int b)
{
    int ra = radacina(a);
    int rb = radacina(b);
    if(rang[ra] > rang[rb])
        t[ra] = rb;
    else
        t[rb] = ra;
    if(rang[ra] < rang[rb])
        rang[rb]++;

}

int main()
{
    f >> n >> m;

    for ( int i = 1; i <= m ; i++)
    {
        f >> v[i].x >> v[i].y >> v[i].c;
    }

    sort ( v + 1 , v + m + 1 , cmp);

    for ( int i = 1 ; i <= m ; i++)
    {
        int a = v[i].x , b = v[i].y , cost = v[i].c;
        if(radacina(a) != radacina(b))
        {
            s = s + cost;
            unire(a,b);
        }
    }
    g << s;
}