Conjuntos
Disjuntos
Monitoria Algoritmos 2012.2
Conjuntos Disjuntos
Breve resumo
 Uma
coleção de elementos, e cada
elemento pertence a um conjunto. Unir
elementos é o mesmo que unir os
conjuntos os quais eles pertencem. Cada
conjunto tem o seu representante.
3
x
y
1
4
2
6
xUy
5
1 4
2 3
5
6
Conjuntos Disjuntos
3
x
y
1
4
2
6
xUy
5
1 4
2 3
5
6
Vamos supor que o representante do conjunto x é 1, e o
representante do conjunto y é 4.
Rep(x) é o representante do conjunto em que x está contido.
Rep(1) = Rep(2) = Rep(3) = 1
Rep(4) = Rep(5) = Rep(6) = 4
Conjuntos Disjuntos
3
x
y
1
4
2
6
xUy
5
1 4
2 3
5
6
unir(1,2) = unir(1,3) = unir(2,3) = x
unir(4,5) = unir(4,6) = unir(5,6) = y
unir(1,4) = unir(1,5) = unir(1,6) = unir(2,4) = ... = unir(3,6) = x U y
Conjuntos Disjuntos
Início:
6 conjuntos disjuntos
1
2
3
4
5
6
OBS.: a aresta significa
quem é o
representante do
elemento.
Como representar isso em código?
public void init (int N) {
for (int i = 1; i <= N; i++) {
rep[i] = i;
}
}
//rep[i] indica o representante do elemento i
Conjuntos Disjuntos
Vamos utilizar o seguinte
algoritmo para união:
unir(2,1)
public void unir (int i, int j) {
rep[i] = j;
1
3
4
5
6
}
2
unir(3,2)
1
4
5
6
2
3
Mas peraí, isso é eficiente?
Conjuntos Disjuntos
Não!
Imagine o caso:
unir(2,1), unir(3,2), unir(4,3), unir(5,4), etc.
Teríamos uma lista encadeada:
1
2
3
4
5
6
...
Se eu quiser saber o conjunto em que o 6
está contido, eu teria que percorrer os 5
elementos acima dele. Esta estratégia é
custosa (O(n) por consulta).
Precisamos pensar numa estratégia que
amortize este custo!
Conjuntos Disjuntos
E a estratégia nova que iremos adotar é simples! Ao invés
de unirmos um elemento diretamente a outro, vamos unir
o representante do conjunto de um com o representante
do conjunto do outro. Para isso, criaremos uma função
recursiva achaConjunto que faz o representante do elemento
atual ser igual ao representante do seu atual representante.
Isto é:
public int achaConjunto (int i) {
if (rep[i] = i) {
return i;
} else {
rep[i] = achaConjunto(rep[i]);
return rep[i];
}
}
Conjuntos Disjuntos
Nossa nova função de unir conjuntos agora será:
public void unir (int i, int j) {
rep[AchaConjunto(i)] = AchaConjunto(j);
}
Voltando à simulação em que estávamos antes:
1
3
4
5
6
2
unir(2,3)
1
2
3
4
5
6
Conjuntos Disjuntos
unir(2,3)
3
4
5
6
5
6
1
2
achaConjunto(2) = 3
3
4
1
2
Conjuntos Disjuntos
unir(1,5)
4
5
6
3
1
2
unir(4,2)
5
2
3
1
6
4
Conjuntos Disjuntos
public void init (int N) {
for (int i = 1; i <= N; i++) {
rep[i] = i;
}
}
public int achaConjunto (int i) {
if (rep[i] = i) {
return i;
} else {
rep[i] = achaConjunto(rep[i]);
return rep[i];
}
}
public void unir (int i, int j) {
rep[achaConjunto(i)] = achaConjunto(j);
}
Conjuntos Disjuntos
DESAFIO!
Há N discos no chão. Cada disco é definido por sua posição (x,y) e
seu raio r. Os discos são cobertos de cola, portanto dois discos estão
colados se eles se intersectam em pelo menos 2 pontos. Se você
levantar um disco do chão, você levantará todos os discos colados
a ele, e todos os discos colados aos discos colados a ele, e assim
por diante. Dados os N discos, você deverá informar a maior
quantidade de discos que se pode levantar de uma vez só
segurando um único disco. A entrada é composta por vários casos
de teste, e cada caso de teste começa com um inteiro N, e N linhas
se seguem, cada uma definindo x, y, r, onde (x,y) é a posição do
centro do disco, e r é o raio do mesmo. A entrada deverá ser lida
até o N encontrado ser -1. A saída para cada caso de teste é uma
linha contendo um único número com a resposta.
EXEMPLO INPUT
3
3.0 2.0 2.0
0.0 -0.5 1.0
0.0 0.0 2.0
EXEMPLO OUTPUT
2