Conjuntos-Disjuntos (Disjoint-Set)

Uma estrutura de dados muito interessante e útil é a utilizada para identificar conjuntos disjuntos, ou seja, conjunto que não estão ligados, em um grafo. Por exemplo:

Grafo bidirecional

No grafo acima de N = 6 nós, os nós (1, 2 e 5) formam um conjunto conexo (a partir de um deles você consegue chegar nos outros), assim como (3, 4) e (6), totalizando 3 conjuntos conexos.

O algoritmo da estrutura começa com N conjuntos, e possui duas funções principais:

• Union: Une dois conjuntos
• Find: Retorna em que conjunto um nó está inserido

A lógica é: para cada aresta (par de nós conectados), checa se fazem parte de conjuntos diferentes utilizando o método Find. Se sim, une os dois nós.

Para isso, basta criar um vetor que armazena o conjunto de que os nós fazem parte. Inicialmente, temos:

Os métodos Union e Find poderiam ser:

int Find(int node) {
    return pai[node];
}

void Union(int node_A, int node_B) {
    int pai_A = Find(node_A);
    int pai_B = Find(node_B);
    
    if(pai_A == pai_B) return; //Se tem os mesmos pais,
                               //entao estao ligados e fim

    //Para todos os N nos, atualiza os que apontavam para node_B
    //agora devem apontar para node_A
    pai[pai_B] = pai_A;

    for(int i = 0; i < N; i++) {
        if(pai[i] == pai_B) {
            pai[i] = node_A;
        }
    }
    return;
}

Ou seja, se descobrimos que o pai de B é diferente do pai de A, fazemos pai de B recebe pai de A. Mas com isso, precisaríamos atualizar todos os nós que tivessem como pai o mesmo pai de B, o que demoraria O(N) para executar cada função Union (varia proporcionalmente com o tamanho do grafo, ruim!).

Outra opção, que é a usada: armazenar cada conjunto como um árvore, o vetor "pai" armazena o pai do nó da árvore, e o método Find retorna a raiz da árvore (o pai da raiz é a própria raiz). Explico melhor.

 

Agora, consideremos a aresta 1-2, e unimos:

 

A aresta 3-4:

 

A aresta 2-5:

E os métodos Union-Find se tornam:

int Find(int node) {
    while(pai[node] != node) //enquanto nao encontra a raiz
        node = pai[node];
    return pai[node];
}

void Union(int node_A, int node_B) {
    int pai_A = Find(node_A);
    int pai_B = Find(node_B);
    
    if(pai_A == pai_B) return; //Se tem os mesmos pais,
                               //entao estao ligados e fim

    pai[pai_B] = pai_A;
    return;
}

Essa é a ideia básica do algoritmo. Com as otimizações certas (procure por Union-by-rank ou Path-Compression), é garantido que os métodos tem, no pior dos casos, O(logN) de complexidade.

Esse algoritmo é importante também para resolver um problema de grafos conhecido como Árvore Geradora Mínima, utilizando o algoritmo de Kruskal. Sugiro a resolução desse problema do URI, que aborda o assunto:
https://www.urionlinejudge.com.br/judge/pt/problems/view/1082

E esse do SPOJ, que é resolvido com o algoritmo de Kruskal:
http://br.spoj.com/problems/CIPO/

P.S.: Esse tópico é o primeiro assunto do curso de algoritmos de Princeton disponível no Coursera (https://pt.coursera.org/course/algs4partI) e que é muito bom!