A estrutura de dados Union-Find, também conhecida como Disjoint Set Union (DSU), é fundamental para gerenciar coleções de elementos particionados em conjuntos disjuntos. Ela permite verificar rapidamente se dois elemenots pertencem ao mesmo conjunto e fundir dois conjuntos distintos.

1. Estrutura Básica com Compressão de Caminho

O conceito central do DSU é representar cada conjunto como uma árvore, onde cada nó aponta para seu pai. A raiz da árvore é o representante do conjunto. Para otimizar a operação de busca, utilizamos a Compressão de Caminho, que faz com que cada nó visitado aponte diretamente para a raiz, reduzindo drasticamente a altura da árvore para chamadas futuras.

#include <iostream>
#include <vector>

class UnionFind {
private:
    std::vector<int> pai;

public:
    UnionFind(int n) {
        pai.resize(n + 1);
        for (int i = 0; i <= n; ++i) pai[i] = i;
    }

    // Busca com compressão de caminho
    int localizar(int x) {
        if (pai[x] != x) {
            pai[x] = localizar(pai[x]);
        }
        return pai[x];
    }

    void mesclar(int a, int b) {
        int raiz_a = localizar(a);
        int raiz_b = localizar(b);
        if (raiz_a != raiz_b) {
            pai[raiz_a] = raiz_b;
        }
    }

    bool mesmo_conjunto(int a, int b) {
        return localizar(a) == localizar(b);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    UnionFind dsu(n);

    while (m--) {
        char op;
        int x, y;
        std::cin >> op >> x >> y;
        if (op == 'M') {
            dsu.mesclar(x, y);
        } else if (op == 'Q') {
            if (dsu.mesmo_conjunto(x, y)) std::cout << "Yes\n";
            else std::cout << "No\n";
        }
    }
    return 0;
}

2. Monitoramento de Tamanho dos Componentes

Em muitos problemas, como o cálculo de componentes conexos em grafos, é necessário saber quantos elementos existem em cada conjunot. Podemos manter um array auxiliar tamanho que é atualizado apenas na raiz durante a operação de união.

#include <iostream>
#include <vector>
#include <string>

class DSUComTamanho {
    std::vector<int> pai;
    std::vector<int> tam;

public:
    DSUComTamanho(int n) {
        pai.resize(n + 1);
        tam.assign(n + 1, 1);
        for (int i = 0; i <= n; ++i) pai[i] = i;
    }

    int buscar(int x) {
        return pai[x] == x ? x : pai[x] = buscar(pai[x]);
    }

    void conectar(int a, int b) {
        int rA = buscar(a);
        int rB = buscar(b);
        if (rA != rB) {
            pai[rA] = rB;
            tam[rB] += tam[rA]; // Acumula o tamanho na nova raiz
        }
    }

    int obter_tamanho(int x) {
        return tam[buscar(x)];
    }
};

3. Union-Find com Pesos (Cadeia Alimentar)

O DSU com pesos é uma técnica avançada que utiliza a ideia de vetores para representar relações entre nós. No exemplo clássico da cadeia alimentar (onde A come B, B come C e C come A), podemos usar a aritmética modular (módulo 3) para definir a relação de cada nó com seu pai na árvore.

#include <iostream>
#include <vector>

class WeightedDSU {
    std::vector<int> pai;
    std::vector<int> dist; // Distância relativa ao pai (mod 3)

public:
    WeightedDSU(int n) {
        pai.resize(n + 1);
        dist.assign(n + 1, 0);
        for (int i = 0; i <= n; ++i) pai[i] = i;
    }

    int buscar(int x) {
        if (pai[x] == x) return x;
        int original_pai = pai[x];
        pai[x] = buscar(pai[x]);
        dist[x] = (dist[x] + dist[original_pai]) % 3; // Atualiza peso baseado no caminho
        return pai[x];
    }

    bool validar_e_unir(int tipo, int x, int y, int n) {
        if (x > n || y > n) return false;
        if (tipo == 2 && x == y) return false;

        int rX = buscar(x);
        int rY = buscar(y);

        if (rX != rY) {
            pai[rX] = rY;
            // Cálculo da nova distância baseado na relação (tipo-1)
            dist[rX] = (dist[y] - dist[x] + (tipo - 1) + 3) % 3;
            return true;
        } else {
            // Se já estão no mesmo conjunto, verificamos a consistência
            int relacao = (dist[x] - dist[y] + 3) % 3;
            return relacao == (tipo - 1);
        }
    }
};

int main() {
    int n, k, falsas = 0;
    if (!(std::cin >> n >> k)) return 0;
    WeightedDSU dsu(n);

    while (k--) {
        int t, x, y;
        std::cin >> t >> x >> y;
        if (!dsu.validar_e_unir(t, x, y, n)) {
            falsas++;
        }
    }
    std::cout << falsas << std::endl;
    return 0;
}