Gincana

gincana.cpp

#include <cstdio>

#define MAXN 1100

int n, m, resp;

int pai[MAXN], peso[MAXN];

int find(int x){ //funcao do Union-Find
	
	if(pai[x]==x) return x;
	return pai[x]=find(pai[x]);
}

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

}

int main(){
	
	scanf("%d %d", &n, &m); // leia os valores de n e m
	
	for(int i=1; i<=n; i++){ // estabeleca que todo mundo é líder de sua própria equipe, apenas consigo mesmo
		
		pai[i]=i;
	}
	
	for(int i=1; i<=m; i++){ // para cada uma das m linhas seguintes
		
		int a, b;
		scanf("%d %d", &a, &b); // leia os valores dos números dos amigos
		
		join(a, b); // coloque os dois na mesma equipe
	}
	
	for(int i=1; i<=n; i++) if(find(i)==i) resp++; // a quantidade de líderes de equipe será a quantidade equipes
	
	printf("%d\n", resp); // imprima a resposta
	
	return 0;
}