Настройки поиска (Страница 3 из 3)

#include <iostream>
using namespace std;
int p[500000] , r[500000] , n,m,sum;
pair<int , pair<int,int> > a[400000];


int FindSet(int x)
{
    if (p[x]!=x) p[x]= FindSet(p[x]);
    return p[x];
}

void Union(int a,int b)
{
    a=FindSet(a);
    b=FindSet(b);

    if (r[a] > r[b]) p[b] = a; else
    {
        p[a]=b;
        if (r[a] == r[b]) r[b]++;
    }
}

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>n>>m;

    for (int i=1;i<=n;i++) p[i]=i;
    
    for (int i=0;i<m;i++) {
        int l,r,w;
        cin>>l>>r>>w;
        a[i] = make_pair( w, make_pair(l,r) );
    }

    sort(a,a+m);

    for (int i=m-1;i>=0;i--)
    if (FindSet(a[i].second.second)!=FindSet(a[i].second.first)) {
        Union(a[i].second.second , a[i].second.first);
        sum+=a[i].first;
    } 

    cout<<sum;
}