Conjuntos Disjuntos

A estrutura de dados de conjuntos disjuntos é uma estrutura de dados que mantém eficientemente um conjunto de elementos particionado  em conjuntos disjuntos. Duas operações são importante sobre esta estrutura:

FIND: encontrar o conjunto de um dado elemento
UNION: unificar dois conjuntos


p[x] = representa o líder do conjunto disjuntos
rank[x] = é o limite superior para a altura do nó. O algoritmo constrói implicitamente uma árvore em que as folhas são os líderes de cada conjunto disjunto e todos os "liderados" apontam diretamente ou indiretamente para o líder do conjunto.

Make Set(x)
1) p[x] ← x
2) rank[x] ← 0

Union(x, y)
1) Link(Find Set(x),Find Set(y))

Link(x, y)
1) if rank[x] > rank[y]
2) then p[y] ← x
3) else p[x] ← y
4) if rank[x] = rank[y]
5) then rank[y] ← rank[x] + 1

Find Set(x)
1) if x == p[x]
2) then p[x] ← Find Set(p[x])
3) return p[x]

Heuristicas

Union By Rank: faça a raiz da árvore com menor número de elementos apontar para a raiz da árvore com maior número de elementos. O rank ou ordem é um limite superior para a altura do nó.

Path Compression: durante uma busca faça os nós do caminho apontar para a raiz

Vamos representar o vetor p[x] por uma seta apontando para o líder do conjunto e  rank será representado por um número ao lado do vértice

Operação Make-Set

UNION (1,2)

Union (1,3)

Union(4,5)

Union(1,4)

Note que a união é feita entre os líderes de cada conjunto, ou seja, será executada link(2,5)

Union(3,5)
Observe que o elemento 3 está no mesmo conjunto que o elemento 5. Nesse caso, a heuristica de compressão de caminho entra em ação.

Algumas aplicações:

• Descobrir se um grafo é conexo.
• Encontrar componentes conexas de um grafo.
• Algoritmo de kruskal.

Problemas:

http://br.spoj.com/problems/REDOTICA/

http://br.spoj.com/problems/ENERGIA/

http://br.spoj.com/problems/CIPO/

http://br.spoj.com/problems/FUSOES1/

http://uva.onlinejudge.org/external/101/10158.html

O código do union-find está neste post.