Conjuntos disjuntos (ou union-find) são estruturas de dados usadas para gerenciar a partição de elementos em conjuntos disjuntos. Implementados como uma floresta, cada árvore representa um conjunto, e os nós dentro da árvore correspondem aos elementos desse conjunto.

A estrutura suporta duas operações principais:

• União (Union): combina dois conjuntos disjuntos em um único conjunto.
• Busca (Find): determina o conjunto ao qual um elemento pertence, tipicamenet retornando a raiz da árvore correspondente.

Além dessas operações básicas, versões estendidas podem lidar com a remoção ou movimentação de elementos individualmente, e usando estruturas como árvores de segmentos dinâmicas, é possível implementar versões persistentes.

Implementação Básica

A operação de busca frequentemente utiliza compressão de caminho para otimização, enquanto a união pode ser implementada de forma simples. Em certos casos, como em união por tamanho ou rank, a compressão de caminho pode ser omitida para manter propriedades específicas.

int buscar(int vertice) {
    if (vertice == pai[vertice]) return vertice;
    return pai[vertice] = buscar(pai[vertice]);
}

void unir(int u, int v) {
    int raizU = buscar(u);
    int raizV = buscar(v);
    if (raizU != raizV) pai[raizU] = raizV;
}

Operações adicionais podem ser requeridas dependendo do problema específico.

Conjuntos Disjuntos com Pesos

Em conjuntos disjuntos com pesos, as arestas da árvore possuem valores que representam relações entre um nó e sua raiz. Durante as operações de busca e união, esses pesos precisam ser atualizados corretamente. A ideia é manter um array de distâncias que é ajustado durante a compressão de caminho e a união.

A busca atualiza o peso acumulando as distâncias ao longo do caminho:

int buscar(int vertice) {
    if (vertice == pai[vertice]) return vertice;
    int ancestral = pai[vertice];
    pai[vertice] = buscar(pai[vertice]);
    distancia[vertice] += distancia[ancestral];
    return pai[vertice];
}

A união estabelece o peso com base na nova aresta adicionada:

void unir(int u, int v, int peso) {
    int raizU = buscar(u);
    int raizV = buscar(v);
    if (raizU == raizV) return;
    pai[raizU] = raizV;
    distancia[raizU] = -distancia[u] + distancia[v] + peso;
}

POJ1703: Determinando Relações

Neste problema, o peso representa a relação entre elementos: 0 para mesmo grupo e 1 para grupos diferentes. Se dois elementos estão no mesmo conjunto, a paridade da diferença de seus pesos indica se pertencem ao mesmo grupo. Se não estão no mesmo conjunto, a relação é indeterminada.

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 100005;
int pai[MAXN], dist[MAXN];

int buscar(int x) {
    if (x == pai[x]) return x;
    int temp = pai[x];
    pai[x] = buscar(pai[x]);
    dist[x] = (dist[x] + dist[temp]) % 2;
    return pai[x];
}

void unir(int a, int b, int d) {
    int raizA = buscar(a);
    int raizB = buscar(b);
    if (raizA == raizB) return;
    pai[raizA] = raizB;
    dist[raizA] = (dist[a] + dist[b] + d) % 2;
}

int main() {
    int casos;
    scanf("%d", &casos);
    while (casos--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            pai[i] = i;
            dist[i] = 0;
        }
        while (m--) {
            char op;
            int x, y;
            scanf(" %c%d%d", &op, &x, &y);
            if (op == 'A') {
                int raizX = buscar(x);
                int raizY = buscar(y);
                if (raizX != raizY) printf("Not sure yet.\n");
                else if ((dist[x] - dist[y] + 2) % 2 == 0) printf("In the same gang.\n");
                else printf("In different gangs.\n");
            } else {
                unir(x, y, 1);
            }
        }
    }
    return 0;
}

HDU3038: Contagem de Contradições em Intervalos

Transforma a soma de um intervalo em uma relação de diferença: a soma de l a r é equivalente a pref[r] - pref[l-1] = valor. Cada afirmação adiciona uma aresta ponderada entre l-1 e r. Contradições ocorrem quando a afirmação conflita com relações já estabelecidas.

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 200005;
int pai[MAXN], dist[MAXN];

int buscar(int x) {
    if (x == pai[x]) return x;
    int temp = pai[x];
    pai[x] = buscar(pai[x]);
    dist[x] += dist[temp];
    return pai[x];
}

void unir(int a, int b, int peso) {
    int raizA = buscar(a);
    int raizB = buscar(b);
    if (raizA == raizB) return;
    pai[raizA] = raizB;
    dist[raizA] = -dist[a] + dist[b] + peso;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            pai[i] = i;
            dist[i] = 0;
        }
        for (int i = 0; i < m; i++) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            l--;
            int raizL = buscar(l);
            int raizR = buscar(r);
            if (raizL == raizR) {
                if (dist[r] - dist[l] != k) ans++;
            } else {
                unir(r, l, k);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

P1525: Apritionamento de Criminosos

Os conflitos são ordenados por severidade decrescente. Para cada par, tenta-se uni-los em grupos opostos usando peso 1. Se já estiverem no mesmo conjunto e a paridade dos pesos indicar o mesmo grupo, ocorre uma contradição, e a severidade atual é a resposta.

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 20005;
int pai[MAXN], dist[MAXN];

struct Conflito {
    int a, b, c;
};

int buscar(int x) {
    if (x == pai[x]) return x;
    int temp = pai[x];
    pai[x] = buscar(pai[x]);
    dist[x] = (dist[x] + dist[temp]) % 2;
    return pai[x];
}

bool unir(int u, int v) {
    int raizU = buscar(u);
    int raizV = buscar(v);
    if (raizU == raizV) {
        return (dist[u] + dist[v]) % 2 == 1;
    }
    pai[raizU] = raizV;
    dist[raizU] = (dist[u] + dist[v] + 1) % 2;
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    Conflito conflitos[m];
    for (int i = 0; i < m; i++) {
        cin >> conflitos[i].a >> conflitos[i].b >> conflitos[i].c;
    }
    for (int i = 1; i <= n; i++) {
        pai[i] = i;
        dist[i] = 0;
    }
    sort(conflitos, conflitos + m, [](Conflito x, Conflito y) { return x.c > y.c; });
    for (int i = 0; i < m; i++) {
        if (!unir(conflitos[i].a, conflitos[i].b)) {
            cout << conflitos[i].c << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}

P1196: Lenda dos Heróis Galácticos

Esta variante mantém o tamanho de cada conjunto e o deslocamento de um nó em relação à raiz. Ao unir dois conjuntos, o nó da raiz da primeira árvore recebe como peso o tamanho atual do segundo conjunto, e o tamanho do segundo conjunto é incrementado. A distância entre dois elementos no mesmo conjunto é |dist[a] - dist[b]| - 1.

#include <iostream>
#include <cmath>
using namespace std;

const int MAXN = 30005;
int pai[MAXN], dist[MAXN], tam[MAXN];

int buscar(int x) {
    if (x == pai[x]) return x;
    int temp = pai[x];
    pai[x] = buscar(pai[x]);
    dist[x] += dist[temp];
    return pai[x];
}

void unir(int a, int b) {
    int raizA = buscar(a);
    int raizB = buscar(b);
    if (raizA == raizB) return;
    pai[raizA] = raizB;
    dist[raizA] = tam[raizB];
    tam[raizB] += tam[raizA];
}

int consulta(int a, int b) {
    int raizA = buscar(a);
    int raizB = buscar(b);
    if (raizA != raizB) return -1;
    return abs(dist[a] - dist[b]) - 1;
}

int main() {
    for (int i = 1; i < MAXN; i++) {
        pai[i] = i;
        dist[i] = 0;
        tam[i] = 1;
    }
    int t;
    cin >> t;
    while (t--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if (op == 'M') unir(a, b);
        else cout << consulta(a, b) << endl;
    }
    return 0;
}

P2024: Cadeia Alimentar

Com pesos módulo 3: 0 para relação de mesma espécie, 1 para predação, e 2 para presa. As operações de busca e união ajustam os pesos modulo 3. Declarações inválidas ou contraditórias são contadas como erros.

#include <iostream>
using namespace std;

const int MAXN = 50005;
int pai[MAXN], rel[MAXN];

int buscar(int x) {
    if (x == pai[x]) return x;
    int temp = pai[x];
    pai[x] = buscar(pai[x]);
    rel[x] = (rel[x] + rel[temp]) % 3;
    return pai[x];
}

void unir(int a, int b, int r) {
    int raizA = buscar(a);
    int raizB = buscar(b);
    if (raizA == raizB) return;
    pai[raizA] = raizB;
    rel[raizA] = (rel[b] - rel[a] + r + 3) % 3;
}

int main() {
    int n, m;
    cin >> n >> m;
    int erros = 0;
    for (int i = 1; i <= n; i++) {
        pai[i] = i;
        rel[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        int tipo, a, b;
        cin >> tipo >> a >> b;
        if (a > n || b > n || (tipo == 2 && a == b)) {
            erros++;
            continue;
        }
        int raizA = buscar(a);
        int raizB = buscar(b);
        if (tipo == 1) {
            if (raizA == raizB && rel[a] != rel[b]) erros++;
            else if (raizA != raizB) unir(a, b, 0);
        } else {
            if (raizA == raizB && (rel[a] - rel[b] + 3) % 3 != 1) erros++;
            else if (raizA != raizB) unir(a, b, 1);
        }
    }
    cout << erros << endl;
    return 0;
}

Conjuntos Disjuntos por Domínio Estendido

Uma abordagem alternativa é expandir os conjuntos disjuntos por domínio, onde cada elemento é replicado em múltiplos nós para representar diferentes relações. Esta técnica oferece funcionalidade semelhante aos conjuntos disjuntos com pesos, mas com uma implementação distinta que pode ser mais intuitiva em certos contextos.