Skip to content

UnionFind ​

UnionFind<T> implementa uma estrutura de dados disjoint set (union-find) com compressão de caminho e união por rank. Ele mantém uma coleção de conjuntos não sobrepostos e suporta operações eficientes de união e busca.

Construção ​

SintaxeDescrição
UnionFind<u32>(n)Cria um novo conjunto disjunto com n elementos indexados de 0 a n - 1
UnionFind<u8>(n)Mesmo, com tipo de elemento u8
UnionFind<u16>(n)Mesmo, com tipo de elemento u16
UnionFind<u64>(n)Mesmo, com tipo de elemento u64

Somente tipos de inteiro sem sinal são permitidos como tipo de elemento.

Métodos ​

MétodoAssinaturaRetornaDescrição
find(T) => TTRepresentante raiz do conjunto que contém x
union(T, T) => booleanbooleanFunde conjuntos; retorna true se houve fusão
connected(T, T) => booleanbooleanSe x e y pertencem ao mesmo conjunto
setCount() => TTNúmero de conjuntos disjuntos

Os elementos são inteiros indexados a partir de 0 até n - 1. O handle nativo é liberado automaticamente quando a variável sai de escopo.

Complexidade ​

OperaçãoComplexidade Temporal
findAmortizado O(α(n)), praticamente constante
unionAmortizado O(α(n)), praticamente constante
connectedAmortizado O(α(n)), praticamente constante
setCountO(1)

Onde α é a função inversa de Ackermann, que é efetivamente constante para todas as entradas práticas.

Exemplos ​

Construção ​

tyrus
import { UnionFind } from "tyrus:algorithm";

const uf = UnionFind<u32>(10);

find ​

tyrus
const uf = UnionFind<u32>(5);

print(uf.find(0));  // 0
print(uf.find(3));  // 3

uf.union(0, 1);
uf.union(1, 2);

print(uf.find(2));  // 0

union ​

tyrus
const uf = UnionFind<u32>(5);

print(uf.union(0, 1));  // true
print(uf.union(2, 3));  // true
print(uf.union(0, 1));  // false

connected ​

tyrus
const uf = UnionFind<u32>(5);

uf.union(0, 1);
uf.union(2, 3);

print(uf.connected(0, 1));  // true
print(uf.connected(0, 3));  // false
print(uf.connected(2, 3));  // true

setCount ​

tyrus
const uf = UnionFind<u32>(5);

print(uf.setCount());  // 5

uf.union(0, 1);
uf.union(2, 3);

print(uf.setCount());  // 3