Union Find

#include <iostream>
#include <vector>

using namespace std;

vector <int> id;
vector <vector <int> > comp;

bool unionFind(int a, int b)
{
    int idA = id[a];
    int idB = id[b];

    if(idA == idB)
        return false;

    int tamA = comp[idA].size();
    int tamB = comp[idB].size();

    if(tamA > tamB)
        return unionFind(b, a);

    for(const auto nodo:comp[idA])
    {
        comp[idB].push_back(nodo);
        id[nodo] = idB;
    }

    comp[idA].clear();

    return true;
}

void prepararUnionFind(int cantNodos)
{
    ///Llamar a esta función antes de llamar
    ///a unionFind() !!!! IMPORTANTE!!!

    ///Cada nodo pertenece a su propio grupo
    comp.resize(cantNodos+1);
    id.resize(cantNodos+1);

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

int main()
{
    ///Se lee el input
    ///se procesa
    ///y se imprime, según corresponda

    ///Véase el problema
    ///http://juez.oia.unsam.edu.ar/#/task/conectar/statement
    ///Para practicar Union Find

    return 0;
}