Fusões

fusões.cpp

#include <cstdio>
 
#define MAXN 100100

// declaro as variáveis que vou precisar
int n, k, pai[MAXN], peso[MAXN];

// funções do Union-Find otimizadas
int find(int x){
	
	if(pai[x]==x) return x;
	return pai[x]=find(pai[x]);
}
 
void join(int x, int y){
	
	x=find(x);
	y=find(y);
	
	if(x==y) return;
	
	if(peso[x]<peso[y]) pai[x]=y;
	if(peso[x]>peso[y]) pai[y]=x;
	
	if(peso[x]==peso[y]){
		
		pai[x]=y;
		peso[y]++;
	}
}

// os comandos da main seguem os mesmo do código anterior, não otimizado
int main(){
	
	scanf("%d %d", &n, &k);
	
	for(int i=1; i<=n; i++) pai[i]=i;
	
	char op;
	int banco1, banco2;
	
	for(int i=1; i<=k; i++){
		
		scanf(" %c %d %d", &op, &banco1, &banco2);
		if(op=='F') join(banco1, banco2);
		else{
			
			if(find(banco1)==find(banco2)) printf("S\n");
			else printf("N\n");
		}
	}
	
	return 0;
}