Skip to Content
CTRL K

Union-Find / conjuntos disjuntos

HechoFuenteNombreDificultadTagsSolución
YSUnion FindFácilDSUen el módulo

Recursos

Recursos
FuenteRecursoNotas
CF EDUDSU

explicación en video + problemas de DSU

CSADisjoint Data Sets

ambas optimizaciones, diagramas

PAPS113.1 - Union-Find

ambas optimizaciones, sin diagramas

CPH15.2 - Union-Find

small to large, diagramas

IUSACO10.6 - Disjoint-Set Data Structure

compresión de caminos, diagramas

TCDisjoint Set Data Structures

diagramas

Demostraciones de la complejidad de DSU

Implementación

Recursos
FuenteRecursoNotas
Benq (from KACTL)DSU

Abajo hay una implementación de un DSU. Utiliza fusión small-to-large y compresión de caminos para ejecutar union-find rápidamente. sizes[x] guarda el tamaño de la componente de xx, y parents[x] guarda el padre de xx (igual a xx si es el representante).

#include <bits/stdc++.h>
using namespace std;
 
class DisjointSets {
  private:
	vector<int> parents;
	vector<int> sizes;
 
  public:
	DisjointSets(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}
 
	/** @return el nodo "representante" de la componente de x */
	int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
 
	/** @return si la fusión cambió la conectividad */
	bool unite(int x, int y) {
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root) { return false; }
 
		if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}
 
	/** @return si x e y están en la misma componente conexa */
	bool connected(int x, int y) { return find(x) == find(y); }
};
import java.util.*;
 
public class DisjointSets {
	int[] parents;
	int[] sizes;
 
	public DisjointSets(int size) {
		parents = new int[size];
		sizes = new int[size];
		for (int i = 0; i < size; i++) {
			parents[i] = i;
			sizes[i] = 1;
		}
	}
 
	/** @return el nodo "representante" de la componente de x */
	public int find(int x) {
		return parents[x] == x ? x : (parents[x] = find(parents[x]));
	}
 
	/** @return si la fusión cambió la conectividad */
	public boolean unite(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot == yRoot) { return false; }
 
		if (sizes[xRoot] < sizes[yRoot]) { return unite(yRoot, xRoot); }
		parents[yRoot] = xRoot;
		sizes[xRoot] += sizes[yRoot];
		return true;
	}
 
	/** @return si x e y están en la misma componente conexa */
	public boolean connected(int x, int y) { return find(x) == find(y); }
}
class DisjointSets:
	def __init__(self, size: int) -> None:
		self.parents = [i for i in range(size)]
		self.sizes = [1 for _ in range(size)]
 
	def find(self, x: int) -> int:
		""":return: el nodo "representante" de la componente de x"""
		if self.parents[x] == x:
			return x
		self.parents[x] = self.find(self.parents[x])
		return self.parents[x]
 
	def unite(self, x: int, y: int) -> bool:
		""":return: si la fusión cambió la conectividad"""
		x_root = self.find(x)
		y_root = self.find(y)
		if x_root == y_root:
			return False
 
		if self.sizes[x_root] < self.sizes[y_root]:
			x_root, y_root = y_root, x_root
 
		self.parents[y_root] = x_root
		self.sizes[x_root] += self.sizes[y_root]
		return True
 
	def connected(self, x: int, y: int) -> bool:
		""":return: si x e y están en la misma componente conexa"""
		return self.find(x) == self.find(y)

Como la implementación es bastante simple, puede preferirse usarla en lugar de DFS para calcular componentes conexas.

Solución - Problema foco

Sin union-find, tendríamos que representar el grafo con una lista de adyacencia y usar flood fill para calcular componentes conexas. Este enfoque toma O(NQ)\mathcal{O}(NQ) tiempo, que es demasiado lento, lo que nos motiva a usar union-find.

Al representar el grafo con la estructura de datos union-find que se implementó arriba, podemos usar sus métodos tanto para unir vértices como para comprobar si dos vértices uiu_i y viv_i están en la misma componente conexa usando solo O(α(N))\mathcal{O}(\alpha(N)) tiempo amortizado.

Esto reduce la complejidad temporal total a O(Qα(N))\mathcal{O}(Q \alpha(N)), que es una mejora sustancial y nos permite pasar todos los casos de prueba.

Implementación

Complejidad temporal: O(Qα(N))\mathcal{O}(Q \alpha(N))

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{DSU}
class DisjointSets {
  private:
	vector<int> parents;
	vector<int> sizes;
 
  public:
	DisjointSets(int size) : parents(size), sizes(size, 1) {
		for (int i = 0; i < size; i++) { parents[i] = i; }
	}
 
	/** @return el nodo "representante" de la componente de x */
	int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
 
	/** @return si la fusión cambió la conectividad */
	bool unite(int x, int y) {
		int x_root = find(x);
		int y_root = find(y);
		if (x_root == y_root) { return false; }
 
		if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
		sizes[x_root] += sizes[y_root];
		parents[y_root] = x_root;
		return true;
	}
 
	/** @return si x e y están en la misma componente conexa */
	bool connected(int x, int y) { return find(x) == find(y); }
};
// EndCodeSnip
 
int main() {
	int node_num, query_num;
	cin >> node_num >> query_num;
 
	DisjointSets dsu(node_num);
	for (int i = 0; i < query_num; i++) {
		int type, u, v;
		cin >> type >> u >> v;
		if (type == 0) {
			dsu.unite(u, v);
		} else {
			cout << dsu.connected(u, v) << endl;
		}
	}
}
import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int size = io.nextInt();
		int queryNum = io.nextInt();
 
		DisjointSets dsu = new DisjointSets(size);
		for (int i = 0; i < queryNum; i++) {
			int type = io.nextInt();
			int u = io.nextInt();
			int v = io.nextInt();
			if (type == 0) {
				dsu.unite(u, v);
			} else {
				if (dsu.connected(u, v)) {
					io.println(1);
				} else {
					io.println(0);
				}
			}
		}
		io.close();
	}
 
	// CodeSnip{Kattio}
}
 
// BeginCodeSnip{DSU}
class DisjointSets {
	int[] parents;  // indexado desde 0
	int[] sizes;
 
	public DisjointSets(int size) {
		parents = new int[size];
		sizes = new int[size];
		for (int i = 0; i < size; i++) {
			parents[i] = i;
			sizes[i] = 1;
		}
	}
 
	/** @return el nodo "representante" de la componente de x */
	public int find(int x) {
		return parents[x] == x ? x : (parents[x] = find(parents[x]));
	}
 
	/** @return si la fusión cambió la conectividad */
	public boolean unite(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot == yRoot) { return false; }
 
		if (sizes[xRoot] < sizes[yRoot]) { return unite(yRoot, xRoot); }
		parents[yRoot] = xRoot;
		sizes[xRoot] += sizes[yRoot];
		return true;
	}
 
	/** @return si x e y están en la misma componente conexa */
	public boolean connected(int x, int y) { return find(x) == find(y); }
}
// EndCodeSnip
# BeginCodeSnip{DSU}
class DisjointSets:
	def __init__(self, size: int) -> None:
		self.parents = [i for i in range(size)]
		self.sizes = [1 for _ in range(size)]
 
	def find(self, x: int) -> int:
		""":return: el nodo "representante" de la componente de x"""
		if self.parents[x] == x:
			return x
		self.parents[x] = self.find(self.parents[x])
		return self.parents[x]
 
	def unite(self, x: int, y: int) -> bool:
		""":return: si la fusión cambió la conectividad"""
		x_root = self.find(x)
		y_root = self.find(y)
		if x_root == y_root:
			return False
 
		if self.sizes[x_root] < self.sizes[y_root]:
			x_root, y_root = y_root, x_root
 
		self.parents[y_root] = x_root
		self.sizes[x_root] += self.sizes[y_root]
		return True
 
	def connected(self, x: int, y: int) -> bool:
		""":return: si x e y están en la misma componente conexa"""
		return self.find(x) == self.find(y)
 
 
# EndCodeSnip
 
 
size, query_num = [int(i) for i in input().split()]
 
dsu = DisjointSets(size)
for _ in range(query_num):
	q_type, u, v = [int(i) for i in input().split()]
	if q_type == 0:
		dsu.unite(u, v)
	else:
		print(1 if dsu.connected(u, v) else 0)

Problemas

Estándar

Ya se deberían conocer las soluciones con DFS / búsqueda binaria de “Wormhole Sort” y “Moocast”.

HechoFuenteNombreDificultadTagsSolución
CSESRoad ConstructionFácilDSUSolución
GoldClosing the FarmFácilDSUSolución
Gold★ MootubeFácilDSUSolución
Silver★ Wormhole SortFácilDSUSolución
GoldMoocastFácilDSUSolución
Old SilverTractorFácilDSUSolución
CSAMountain TimeNormalDSUSolución
CFTwo SetsNormalDSUSolución
GoldReachable PairsNormalDSUSolución

Más difíciles

No hay que preocuparse por resolver estos si es la primera vez que se ve DSU.

HechoFuenteNombreDificultadTagsSolución
CSESNew Roads QueriesDifícilDSU, MergingSolución
GoldStrongest Friendship GroupDifícilDSU, Merging, Sorted Set—
Old GoldSki Course RatingDifícilDSUSolución
onlinejudge.orgWarDifícilDSUSolución
Baltic OI2016 - ParkMuy difícilDSUSolución
Gold★ Favorite ColorsMuy difícilDSU—
PlatinumValleysMuy difícilDSUSolución
Caminos más cortos con aristas no ponderadasUnion-Find / conjuntos disjuntos (DSU)