#并查集#信息学奥赛一本通 1389 亲戚

链接

---

题目

求每次提问后家庭的人数。

---

分析

用并查集。

---

代码

#include <cstdio>
#include <cctype>
using namespace std;
int f[100001],sum[100001],n,m; char k;
int in(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
int getf(int u){return (f[u]==u)?u:f[u]=getf(f[u]);}
void uni(int x,int y){
	int fa=getf(x),fb=getf(y);
	if (fa!=fb) f[fb]=fa,sum[fa]+=sum[fb];
}
int main(){
	n=in(); m=in();
	for (int i=1;i<=n;i++) f[i]=i,sum[i]=1;
	while (m--){
		while (!isalpha(k)) k=getchar();
		if (k=='M') uni(in(),in());
		else printf("%d\n",sum[getf(in())]);
		k=getchar();
	}
	return 0;
}