Fusões Ingênuo

naive_fusoes.cpp

#include <cstdio>
 
#define MAXN 100100
 
int n, k;
 
int pai[MAXN], peso[MAXN];

// funções do Union-Find
int find(int x){
	
	if(pai[x]==x) return x;
	return find(pai[x]);
}
 
void join(int x, int y){
	
	pai[find(x)]=find(y);
}
 
int main(){
	
	// leio os valores de n e k
	scanf("%d %d", &n, &k);
	
	// inicializo todos os bancos como pais de si mesmos
	for(int i=1; i<=n; i++) pai[i]=i;
	
	char op;
	int banco1, banco2;
	
	// para cada operação a ser realizada
	for(int i=1; i<=k; i++){
		
		// leio o tipo de operação e os bancos envolvidos
		scanf(" %c %d %d", &op, &banco1, &banco2);
		
		// se a operação for a de fusão
		if(op=='F') join(banco1, banco2); // realizo a união dos conjuntos
		
		// se não for, é uma consulta
		else{
			// se os bancos estiverem no mesmo conjunto
			if(find(banco1)==find(banco2)) printf("S\n"); // imprimo 'S'
			
			// se não, imprimo 'N'
			else printf("N\n");
		}
	}
	
	return 0;
}