Kruskal

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Arista
{
    int desde;
    int hacia;
    int costo;
};

bool comparador(const Arista &ar1, const Arista &ar2)
{
    return (ar1.costo < ar2.costo);
}

Arista armarArista(int a, int b, int costo)
{
    Arista ar;
    ar.desde = a;
    ar.hacia = b;
    ar.costo = costo;
    return ar;
}

struct Grafo
{
    vector <vector <Arista> > adj; ///Lista de adyacencia
    vector <Arista> listaAristas; ///Acá se guardan todas las aristas
    vector <int> idComp; ///Acá va el ID de la componente a la cual pertenece un nodo
    vector <vector <int> > comp; ///Lista de nodos por cada componente

    void leer()
    {
        int nodos, aristas;
        cin >> nodos >> aristas;

        adj.resize(nodos+1);
        idComp.resize(nodos+1);
        comp.resize(nodos+1);

        for(int i=1; i<=nodos; i++)
        {
            idComp[i] = i;
            comp[i].push_back(i);
        }

        int desde, hacia, costo;

        for(int i=0; i<aristas; i++)
        {
            cin >> desde >> hacia >> costo;
            adj[desde].push_back(armarArista(desde, hacia, costo));
            adj[hacia].push_back(armarArista(hacia, desde, costo));
            listaAristas.push_back(armarArista(desde, hacia, costo));
        }
    }

    bool sigueSiendoArbol(Arista ar)
    {
        ///Preguntar si las componentes son distintas
        int n1 = ar.desde;
        int n2 = ar.hacia;

        int c1 = idComp[n1];
        int c2 = idComp[n2];

        return (c1 != c2);
    }

    void agregarArista(Arista ar)
    {
        ///1) Unificar los ID

        int n1 = ar.desde;
        int n2 = ar.hacia;

        int c1 = idComp[n1];
        int c2 = idComp[n2];

        int t1 = comp[c1].size();
        int t2 = comp[c2].size();

        ///Siempre la componente 1 sea menor que la componente 2

        ///O(N*N) -> O(N*log(N))
        if(t1 > t2) ///ES VITAL PARA QUE ESTO FUNCIONE COMO LA GENTE
        {
            swap(n1, n2);
            swap(c1, c2);
            swap(t1, t2);
        }

        for(int i=0; i<t1; i++)
        {
            int n = comp[c1][i];
            ///Cambiar el ID
            ///Agregarlo a la lista de nodos de la otra componente
            idComp[n] = c2;
            comp[c2].push_back(n);
        }
    }

    void mostrarArista(Arista ar)
    {
        cout << "(" << ar.desde << ", " << ar.hacia << "): " << ar.costo << endl;
    }

    void Kruskal()
    {
        ///ordenar la lista de arista
        sort(listaAristas.begin(), listaAristas.end(), comparador);

        ///Agarrar una por una, ir agregándola a un MST(minimum spanning tree)
        for(int i=0; i<listaAristas.size(); i++)
        {
            ///Agregar una arista, solamente si al agregarla no se forman ciclos
            if(sigueSiendoArbol(listaAristas[i]))
            {
                agregarArista(listaAristas[i]);
                mostrarArista(listaAristas[i]);
            }
        }
    }
};

int main()
{
    Grafo g;
    g.leer();
    g.Kruskal();

    return 0;
}