Embedded Files
Essa estrutura de dados é útil para resolver uma série de problemas:
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=359
Quando você terminar de ler essa página e entender o algoritmo, resolva todos os problemas do link acima.
Comece pelo UVA 11503.
Veja aqui também as aulas do prof. Márcio Ribeiro.
Além disso, ela também é usada por outros algoritmos, como por exemplo o algoritmo de Kruskal.
A ideia é a seguinte:
Imagine que você vai organizar os seus livros em caixas, onde cada caixa representa uma certa categoria. Assim, ao final da sua organização, você terá vários conjuntos de livros, sendo cada conjunto o representante de uma categoria.
Depois, você quer fazer buscas do tipo:
- Quantos livros existem no conjunto do livro 'a' ?
- Os livros 'a' e 'b' pertencem ao mesmo conjunto?
Para isso, vamos representar cada conjunto por uma árvore. Cada nó da árvore guardará a informação para o seu pai. Não guardaremos a informação para os filhos, pois andaremos nessa árvore sempre de baixo pra cima.
Assim, criaremos um array parent[n], onde parent[i] é o pai do nó i (0<= i< n).
Suponha que você possui n livros. Então inicialmente, criaremos n conjuntos. Ou seja, cada livro está sozinho em seu conjunto.
A primeira "sacada" desse algoritmo é escolher um representante para o conjunto. Nesse caso, como existem n conjuntos, o representante de cada conjunto é justamente cada livro. E eles não possuem pais.
Para exemplificar, suponha 6 livros: 0, 1, 2, 3, 4 e 5.
Assim, teremos 6 árvores, cada uma contendo apenas um único livro (representado aqui por números).
E o array parent estará: [-1, -1, -1, -1, -1, -1]
Depois, você começa a classificar, colocando os livros em uma mesma categoria, par a par através de uma operação de merge:
merge( livro a, livro b)
Depois que esse merge é executado, o livro a e o livro b pertencerão ao mesmo conjunto. A ideia do merge é fazer com que cada nó desse conjunto aponte para o mesmo representante. Assim, para saber se dois nós pertencem ao mesmo conjunto, basta depois compararmos seus representantes.
Assim, suponha que você deseja colocar os livros 0 e 3 no mesmo conjunto: merge (0, 3)
Temos que escolher que vai ser o representante desse novo conjunto, formado pela união dos conjuntos que contém o 0 e do que contém o 3.
Como ambos são do mesmo tamanho, tanto faz. Mas daremos preferência a sempre colocar o conjunto maior embaixo do menor, assim, minimizaremos a altura da árvore.
Suponha que escolhemos o 3 como representante. Assim, faremos o parent[0] ter o valor 3, pois 3 é o representante do conjunto que o 0 faz parte.
Agora, suponha que queremos juntar o 0 com o 5: merge(0, 5). Para isso, temos que fazer o parent[5] apontar para o mesmo parent[0], ou seja, ambos terão como representantes o nó 3.
Espero que você tenha conseguido capturar a intuição do processo. O algoritmo em si, possui mais algumas peculiaridades.
Mas para explicar, achei melhor colocar o código abaixo e colocar comentários nas principais partes. Leia-o com atenção.
/* Estrutura: Disjoint Sets Rodrigo Paes. Inicialmente o parent está inicializado com -1*/#include <bits/stdc++.h>using namespace std;int parent[6]; // {0},{1},{2},{3},{4},{5}/* Retorna o elemento da raiz que representa o conjunto do vértice v */int root(int v){ if (parent[v] < 0) { return v; } else { // Cria um atalho. Faz o pai do nó pesquisado apontar diretamente para o nó raiz. parent[v] = root( parent[v] ); return parent[v]; }}/*Indica se os dois vértices pertencem ao mesmo conjunto.Nesse caso, comparamos os 2 representantes de cada conjunto*/bool is_same_set(int v, int u){ return root(v) == root(u);}/*Coloca os 2 vértices no mesmo conjunto.*/void merge(int v, int u){ v = root(v); u = root(u); if (v==u) return; /* O trecho de código a seguir serve para minimizar a altura da árvore. A ideia é que o parent do nó raiz guarde sempre a quantidade de nós da árvore, só que em valores negativos. Ou seja, nesse ponto, tanto u quanto v são os nós raízes. Portanto, quanto menor for o parent, significa que existem mais nós na árvore. Pagamos a menor árvore e colocamos a maior árvore como filha dela. */ if (parent[u] < parent[v]) { /* Se a menor árvore é u, fazemos: swap(parent[u],parent[v]) de tal forma que v será sempre a menor árvore */ int aux = parent[u]; parent[u] = parent[v]; parent[v] = aux; } /* como o parent[u] será sempre negativo, colocamos u embaixo de v. para isso adicionamos a parent[v] a quantidade de nós existentes na árvore de u */ parent[v] += parent[u]; /* E finalmente fazemos u ficar como filho de v */ parent[u] = v;}int set_size(int v){ return -1 * parent[root(v)];}int main(){ memset(parent, -1, sizeof(parent)); cout << is_same_set(0,4) << endl; merge(0,4); // {0,4},{1},{2},{3},{5} cout << is_same_set(0,4) << endl; cout << parent[0] <<" "<< parent[4] << endl; merge(0,5); cout << parent[0] <<" "<< parent[5] << endl; cout << set_size(0) << endl;}Agora, resolva os problemas do início da página.
Google Sites
Report abuse