Noticias - 100pts (AC)

gistfile1.cpp

#include <bits/stdc++.h>
using namespace std;
int N, M;
int raiz[1000015];
int rango[1000015];
int encontrar(int n) {
	if( raiz[n] == n ) 
		return n;
	else raiz[n] = encontrar( raiz[n] ); 
	return raiz[n];
}

void unir(int x, int y){
	int rX, rY;
	rX = encontrar(x);
	rY = encontrar(y);
	if(rX != rY) {
		if(rango[rX] > rango[rY] ){
			raiz[rY] = rX;
			rango[rX] += rango[rY];
		} else {
			raiz[rX] = rY;
			rango[rY] += rango[rX];	
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int i;
	char op;
	int a, b, nodo, rnodo;
	cin>>N>>M;
	for(i=0; i<=N; ++i){
		raiz[i] = i;
		rango[i] = 1;
	}
	for(i=0; i<M; ++i){
		cin>>op;
		if(op == 'A'){
			cin>>a>>b;
			unir(a, b);
		} else {
			cin>>nodo;
			rnodo = encontrar(nodo);
			cout<<rango[rnodo]<<"\n";
		}
	}
	return 0;
}