Naïve Union-Find

naive_union-find.cpp

#define MAXN 100100

int pai[MAXN]; // crio o vetor que armazenará os pais

// função find: retorna o patriarca de um elemento x
int find(int x){ 
	
	// se ele for pai de si mesmo, ele é o patriarca
	if(pai[x]==x) return x;
	
	// se não, devo olhar o patriarca de seu pai
	return find(pai[x]);
}

// função join: faz a união dos conjuntos dos elementos x e y
void join(int x, int y){
	
	// basta fazer o patriarca de um se tornar pai do patriarca do outro
	pai[find(x)]=find(y);
}