Este é um resumo da seção 1.1 do livro de Sedgewick.
O programa 1.1, de Sedgewick
lê uma sequência de pares de inteiros,
todos no intervalo 0..N-1.
Cada par (p, q)
é interpretado como ligue os objetos p e q
.
O programa imprime o par lido se e só se os objetos ainda
não estão ligados, direta ou indiretamente.
#define N 10000
main (void) {
int i, p, q, t, id[N];
for (i = 0; i < N; i++)
id[i] = i;
while (scanf("%d %d\n", &p, &q) == 2) {
if (id[p] == id[q]) continue;
t = id[p];
for (i = 0; i < N; i++)
if (id[i] == t)
id[i] = id[q];
printf(" %d %d\n", p, q);
}
}
Invariante: No começo de cada iteração, id[i] == id[j] se e só se i e j estão ligados, direta ou indiretamente.
Eis o programa 1.2 de Sedgewick:
while (scanf("%d %d\n", &p, &q) == 2) {
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
id[i] = j;
printf(" %d %d\n", p, q);
}
Tempo para processar M pares de N objetos: da ordem de M N/2 no pior caso.
Eis o programa 1.3 de Sedgewick:
int sz[N];
while (scanf("%d %d\n", &p, &q) == 2) {
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
if (sz[i] < sz[j]) {
id[i] = j; sz[j] += sz[i];
}
else {
id[j] = i; sz[i] += sz[j];
}
printf(" %d %d\n", p, q);
}
Invariante: no começo de cada iteração, para cada i tal que id[i] == i, a árvore cuja raiz é i tem exatamente sz[i] elementos.
Tempo para processar M pares de N objetos: não mais que M lg N .
Para obter o programa 1.4 de Sedgewick
basta trocar os for
do programa anterior:
int sz[N];
while (scanf("%d %d\n", &p, &q) == 2) {
for (i = p; i != id[i]; i = id[i])
id[i] = id[id[i]];
for (j = q; j != id[j]; j = id[j])
id[j] = id[id[j]];
if (i == j) continue;
if (sz[i] < sz[j]) {
id[i] = j; sz[j] += sz[i];
}
else {
id[j] = i; sz[i] += sz[j];
}
printf(" %d %d\n", p, q);
}
Eis uma versão um pouco diferente do programa:
while (scanf("%d %d\n", &p, &q) == 2) {
for (i = p; i != id[i]; i = id[i]) ;
for (j = q; j != id[j]; j = id[j]) ;
if (i == j) continue;
if (sz[i] < sz[j]) {
id[i] = j; sz[j] += sz[i]; t = j;
}
else {
id[j] = i; sz[i] += sz[j]; t = i;
}
for (i = p; i != id[i]; i = id[i])
id[i] = t;
for (j = q; j != id[j]; j = id[j])
id[j] = t;
printf(" %d %d\n", p, q);
}
Quanto tempo o programa consome para processar M pares de N objetos? Demonstra-se (a prova é difícil!) que o consumo de tempo é proporcional a
M lg*(N)
no pior caso. A função lg* é definida assim:
int lg_estrela (int N) {
int i = 0, n = N;
while (n > 1) {
n = lg(n);
i++;
}
return i;
}