Skip to content

UnionFind ​

UnionFind<T> implementa una estructura de datos disjoint set (union-find) con compresión de camino y unión por rango. Mantiene una colección de conjuntos no superpuestos y soporta operaciones eficientes de unión y búsqueda.

Construcción ​

SintaxisDescripción
UnionFind<u32>(n)Crea un nuevo conjunto disjunto con n elementos indexados de 0 a n - 1
UnionFind<u8>(n)Igual, con tipo de elemento u8
UnionFind<u16>(n)Igual, con tipo de elemento u16
UnionFind<u64>(n)Igual, con tipo de elemento u64

Solo se permiten tipos de enteros sin signo como tipo de elemento.

Métodos ​

MétodoFirmaRetornaDescripción
find(T) => TTRepresentante raíz del conjunto que contiene x
union(T, T) => booleanbooleanFusiona conjuntos; retorna true si hubo fusión
connected(T, T) => booleanbooleanSi x e y pertenecen al mismo conjunto
setCount() => TTNúmero de conjuntos disjuntos

Los elementos son enteros indexados desde 0 hasta n - 1. El handle nativo se libera automáticamente cuando la variable sale del ámbito.

Complejidad ​

OperaciónComplejidad Temporal
findAmortizado O(α(n)), prácticamente constante
unionAmortizado O(α(n)), prácticamente constante
connectedAmortizado O(α(n)), prácticamente constante
setCountO(1)

Donde α es la función inversa de Ackermann, que es efectivamente constante para todas las entradas prácticas.

Ejemplos ​

Construcción ​

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