O Union-Find com domínios estendidos é uma técnica que permite representar relações de múltiplos tipos entre elementos. Cada elemento é expandido para um conjunto de domínios, facilitando a classificação e o gerenciamento de relacionamentos complexos. Esta abordagem é particularmente útil em problemas onde os elementos pertencem a categorias distintas e interagem de maneiras específicas.

Para ilustarr a aplicação, considere o problema de alocar prisioneiros em duas prisões de modo a minimizar conflitos. Usamos Union-Find estendido para representar as possíveis alocações: um domínio para a prisão A e outro para a prisão B. Ao processar os conflitos em ordem decrescente de gravidade, verificamos se alocar um prisioneiro em uma prisão específica causa conflito imediato. Se houver conflito, reportamos a gravidade mínima inevitável.

#include <bits/stdc++.h>
using namespace std;

const int MAX_PRISIONEIROS = 20005;
const int MAX_CONFLITOS = 200005;

struct Conflito {
    int prisioneiro1, prisioneiro2, gravidade;
};

int lider[MAX_PRISIONEIROS * 2];

int encontrarLider(int elemento) {
    if (lider[elemento] != elemento) {
        lider[elemento] = encontrarLider(lider[elemento]);
    }
    return lider[elemento];
}

void unirConjuntos(int a, int b) {
    int raizA = encontrarLider(a);
    int raizB = encontrarLider(b);
    if (raizA != raizB) {
        lider[raizA] = raizB;
    }
}

int main() {
    int totalPrisioneiros, totalConflitos;
    cin >> totalPrisioneiros >> totalConflitos;
    
    Conflito conflitos[MAX_CONFLITOS];
    for (int i = 0; i < totalConflitos; i++) {
        cin >> conflitos[i].prisioneiro1 >> conflitos[i].prisioneiro2 >> conflitos[i].gravidade;
    }
    
    sort(conflitos, conflitos + totalConflitos, [](const Conflito& a, const Conflito& b) {
        return a.gravidade > b.gravidade;
    });
    
    for (int i = 0; i <= 2 * totalPrisioneiros; i++) {
        lider[i] = i;
    }
    
    int gravidadeMinima = 0;
    for (int i = 0; i < totalConflitos; i++) {
        int p1 = conflitos[i].prisioneiro1;
        int p2 = conflitos[i].prisioneiro2;
        int domA1 = p1, domB1 = p1 + totalPrisioneiros;
        int domA2 = p2, domB2 = p2 + totalPrisioneiros;
        
        if (encontrarLider(domA1) == encontrarLider(domA2) || encontrarLider(domB1) == encontrarLider(domB2)) {
            gravidadeMinima = conflitos[i].gravidade;
            break;
        }
        
        unirConjuntos(domA1, domB2);
        unirConjuntos(domB1, domA2);
    }
    
    cout << gravidadeMinima << endl;
    return 0;
}

Outro exemplo clássico é o problema da cadeia alimentar, onde elementos possuem relações de predatismo. Usamos três domínios para representar os tipos: tipo A, tipo B e tipo C, com relações circulares de alimentação. Cada operação define se dois elementos são da mesma espécie ou se um é predador do outro. Validamos as afirmações verificando contradições nos domínios estendidos.

#include <bits/stdc++.h>
using namespace std;

const int MAX_ELEMENTOS = 50005;

int lider[3 * MAX_ELEMENTOS];

int encontrarLider(int elemento) {
    if (lider[elemento] != elemento) {
        lider[elemento] = encontrarLider(lider[elemento]);
    }
    return lider[elemento];
}

void unirConjuntos(int a, int b) {
    int raizA = encontrarLider(a);
    int raizB = encontrarLider(b);
    if (raizA != raizB) {
        lider[raizA] = raizB;
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= 3 * n; i++) {
        lider[i] = i;
    }
    
    int afirMacoesFalsas = 0;
    while (k--) {
        int tipoOperacao, elem1, elem2;
        cin >> tipoOperacao >> elem1 >> elem2;
        
        if (elem1 > n || elem2 > n || (tipoOperacao == 2 && elem1 == elem2)) {
            afirMacoesFalsas++;
            continue;
        }
        
        int raizA1 = encontrarLider(elem1);
        int raizB1 = encontrarLider(elem1 + n);
        int raizC1 = encontrarLider(elem1 + 2 * n);
        int raizA2 = encontrarLider(elem2);
        int raizB2 = encontrarLider(elem2 + n);
        int raizC2 = encontrarLider(elem2 + 2 * n);
        
        if (tipoOperacao == 1) {
            if (raizA1 == raizB2 || raizB1 == raizA2) {
                afirMacoesFalsas++;
                continue;
            }
            unirConjuntos(raizA1, raizA2);
            unirConjuntos(raizB1, raizB2);
            unirConjuntos(raizC1, raizC2);
        } else {
            if (raizA1 == raizA2 || raizA2 == raizB1) {
                afirMacoesFalsas++;
                continue;
            }
            unirConjuntos(raizA1, raizB2);
            unirConjuntos(raizB1, raizC2);
            unirConjuntos(raizC1, raizA2);
        }
    }
    
    cout << afirMacoesFalsas << endl;
    return 0;
}

A estrutura de Union-Find estendida mantém a eficiência das operações de união e busca, com complexidade quase constante por operação após otimizações como compressão de caminho. A expansão dos domínios multiplica o número de eleemntos gerenciados, mas o algoritmo escala bem para problemas de tamanho moderado.