OIA-Wiki

¡Esta es una revisión vieja del documento!

Dejo codigo de clase PAP 2017 https://git.exactas.uba.ar/ltaravilse/pap-alumnos/blob/master/clases/clase03-grafos/grafos.pdf

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]++;
		}
	}
}