OIA-Wiki

La estructura Union-Find, también llamada Disjoint-set Union (abreviado DSU), es una estructura que nos permite manejar conjuntos disjuntos de elementos. Un ejemplo de esto en grafos son las componentes conexas, que son conjuntos disjuntos de nodos.

Cada conjunto va a tener un representante que lo identifica, y las operaciones que debemos poder realizar eficientemente son:

• find(x): Dado un elemento $x$, nos dice quién es el representante del conjunto al que pertenece.
• union(x,y): Dados dos elementos $x$ e $y$, unir los conjuntos, es decir, que pasen a ser uno solo, con un solo representantes para los elementos de ambos conjuntos.

La primera idea poco eficiente que suele surgir, es simplemente tener, para cada elemento, su representante (lo que facilita la función union), y que al intentar unir dos conjuntos con los elementos $x$ e $y$, recorremos todos los elementos, y si su representante es el mismo que el representante de $x$ (pertenecen al mismo conjunto actualmente), entonces su representante pasa a ser el representante de $y$.

Esto podemos hacerlo con un vector que en la posición $i$ tenga el representante del elemento $i$. Pero esto es poco pues eficiente, pues si bien chequear el representante es $O(1)$, unir dos conjuntos es $O(n)$ donde $n$ es la cantidad total de elementos, pues los revisamos todos.

Una posible mejora, es, además de guardar el representante de cada elemento, para cada representante guardar una lista con los elementos de su conjunto. Luego, al unir $x$ con $y$, recorremos el conjunto más chico de los que contienen al $x$ y al $y$ (mirando las listas de sus representantes), y agregamos todos sus elementos a la lista de $y$, cambiamos sus representates por el representante de $y$, y vaciamos la lista del representante de $x$.

Con esta mejora, como a cada elemento lo agregamos a un conjunto más grande que en el que está, se puede ver que si hay $O(m)$ operaciones, a cada elemento lo agregamos a lo sumo a $O(log(m))$ conjuntos, por lo que la complejidad queda de $O(m*log(m))$.

Una optimización más: Podemos pensar que cada conjunto es un árbol! El representante será la raíz, saber la raíz de un árbol (o sea el representante de un conjunto) es ir yendo a los padres de cada elemento, y agregar el conjunto de representante $rx$ al de representante $ry$, es decirle a $rx$ que su padre es $ry$, que sería como colgar el árbol de $rx$ de la raíz $ry$. Si colgamos el árbol de menor tamaño al de mayor, como antes con las listas, haremos menos operaciones. Y si además de esto, al buscar el padre de un elemento recursivamente, lo actualizamos cuando encontremos la raíz, las alturas de los árboles se achican muchísimo, y al calcular el representante de un elemento dos veces por ejemplo, en la primera lo encontramos, se lo asignamos como padre, y luego al buscar el representante es subir una sola vez.

La complejidad es un poco más baja que $O(m*log(m))$, podría decirse que es lineal: para $O(m)$ operaciones el tiempo que lleva procesarlas es casi $O(m)$.

El código queda así (obtenido de una clase de Melanie Sclar):

union-find.cpp

vector<int> padre, altura;
 
void init(int n){
	forn(i, n){
		padre.push_back(i);
		altura.push_back(1);
	}
}
 
int find(int x){
	if(padre[x]!=x){
		padre[x]=find(padre[x]);
	}
	return padre[x];
}
 
void merge(int x, int y){
	int px=find(x), py=find(y);
	if(altura[px]<altura[py]){
		padre[px]=py;
	}else{
		padre[py]=px;
		if(altura[px]==altura[py]){
			altura[px]++;
		}
	}
}

Ir agregando ejes

Unir y saber tamaños

Destroying Array, puede resolverse tranquilamente sin UnionFind, pero es lindo para pensarlo con.