Cod sursă (job #675989)

#include <bits/stdc++.h>
#define nmax 100005

using namespace std;

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

struct Muchie
{
    int x,y,cost;
};

int t[nmax],n,m,sol,k;
Muchie a[101055];

bool Cmp(Muchie A,Muchie B)
{
    return A.cost<B.cost;
}

/// unifica radacinile x si y
void Union(int x,int y)
{
    t[y]=x;
}

/// Complexitate O(log*n)
int Find(int x)
{
    int y,rad=x;
    while(t[rad]!=0)
        rad=t[rad];
    /// compresie drum
    while(x!=rad)
    {
        y=t[x];
        t[x]=rad;
        x=y;
    }
    return rad;
}
int Rezolvare(Muchie a[],int m)
{
    int i,j,x,y;
    sol=0;
    sort(a+1,a+m+1,Cmp);
    for(i=1;i<=n;i++)
        t[i]=0;
    for (i=1;i<=m;i++)
    {
        x=Find(a[i].x);
        y=Find(a[i].y);
        if (x!=y)
        {
            Union(x,y);
            sol+=a[i].cost;
        }
    }
    return sol;
}
int main()
{
    int i,x,y,z;
    fin>>n>>m>>k;
    for (i=1;i<=m;i++)
        fin>>a[i].x>>a[i].y>>a[i].cost;
    fout<<Rezolvare(a,m)<<"\n";
    for(i=1;i<=k;i++)
    {
        fin>>x>>y>>z;
        m++;
        a[m].x=x;
        a[m].y=y;
        a[m].cost=z;
        fout<<Rezolvare(a,m)<<"\n";
    }
    fin.close();
    fout.close();
    return 0;

}