Kruskal

#include <iostream>
#include <vector>
#include <algorithm> ///sort

using namespace std;

vector <int> idComponente;
vector <vector <int> > componente;

bool unionFind(int nodoA, int nodoB)
{
    int compA = idComponente[nodoA];
    int compB = idComponente[nodoB];

    if(compA == compB) ///Están en la misma componente
        return false;

    int tamA = componente[compA].size();
    int tamB = componente[compB].size();

    ///La idea es siempre mover la componenteA hacia la componenteB
    ///Pero para eso, la componenteA siempre debe ser igual o menor a la componenteB
    if(tamA > tamB) ///Este pequeño checkeo hace que sea eficiente
    {
        swap(compA, compB);
        swap(tamA, tamB);
    }

    for(int i=0; i<tamA; i++)
    {
        int nodo = componente[compA][i];
        componente[compB].push_back(nodo); ///Muevo a la otra componente
        idComponente[nodo] = compB; ///Reasigno id de componente
    }

    ///Opcional: Se puede limpiar a la componenteA ya que no existe mas, sus elementos se movieron a componenteB
    componente[compA].clear();

    return true;
}

struct arista
{
    int desde, hacia, costo;
};

bool operator<(const arista &a, const arista &b)
{
    ///Esta función devuelde si arista "a" es menor a arista "b"
    return a.costo < b.costo;
}

vector <arista> Kruskal(vector <arista> a, int cantNodos)
{
    idComponente.resize(cantNodos+1);
    componente.resize(cantNodos+1);

    ///Inicialmente cada nodo pertenece a su propia componente

    for(int i=1; i<=cantNodos; i++)
    {
        idComponente[i] = i;
        componente[i] = vector <int> (1, i);
    }

    vector <arista> arbolCubridorMinimo;

    sort(a.begin(), a.end());

    ///Un arbol cubridor mínimo (minimum spanning tree) tiene aritas = cantNodos-1 ya que es un árbol
    int i = 0;
    while(i < a.size() && arbolCubridorMinimo.size() < cantNodos-1)
    {
        if(unionFind(a[i].desde, a[i].hacia))
            arbolCubridorMinimo.push_back(a[i]);
        i++;
    }

    return arbolCubridorMinimo;
}

int main()
{
    int cantNodos, cantAristas;
    cin >> cantNodos >> cantAristas;

    vector <arista> a(cantAristas);

    for(int i=0; i<cantAristas; i++)
        cin >> a[i].desde >> a[i].hacia >> a[i].costo;

    vector <arista> resultado = Kruskal(a, cantNodos);

    int costoTotal = 0;

    cout << "El arbol cubridor minimo es: " << endl;

    for(int i=0; i<resultado.size(); i++)
    {
        cout << "(" << resultado[i].desde << ",";
        cout << resultado[i].hacia << ") -> " << resultado[i].costo << endl;
        costoTotal += resultado[i].costo;
    }

    cout << "El costo total es: " << costoTotal << endl;

    return 0;
}