1389：亲戚
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
【输入】
第一行：三个整数n，（n≤100,000,m≤200,000），分别表示有n个人，m个信息。
以下m行：信息包含两种形式：
M a b：表示a和b具有亲戚关系。
Q a：要求输出a所在家族的人数。
【输出】
要求输出a所在家族的人数。
【输入样例】
5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4
【输出样例】
1
1
3
1
4
1. //示例代码 2. #include <iostream> 3. #include <cstdio> 4. using namespace std; 5. 6. const int N=1e5+10; // 定义常量 N，表示数组大小 7. int n,m; 8. int f[N],num[N]; // 数组 f 和 num 分别存储父节点和节点数量 9. 10. // 并查集中的查找操作，实现路径压缩 11. int find(int x){ 12. if(f[x]==x) return f[x]; 13. return f[x]=find(f[x]); 14. } 15. 16. int main() 17. { 18. scanf("%d %d",&n,&m); // 输入节点数和操作数 19. for(int i=1;i<=n;i++){ // 初始化并查集，每一个节点是其自己的祖先，并且节点数量为 1. 20. f[i]=i;num[i]=1; 21. } 22. int a,b; 23. char c[2]; 24. for(int i=1;i<=m;i++){ // 进行一些操作。可以对每个节点进行合并或查询。 25. scanf("%s",c); 26. if(c[0]=='M'){ // 如果是合并操作，在输入两个整数A、B，表示要合并的节点。 27. scanf("%d %d",&a,&b); 28. int x=find(a); 29. int y=find(b); 30. if(x==y) continue; 31. f[y]=x; 32. num[x]+=num[y]; 33. } 34. else if(c[0]=='Q'){ // 如果是查询操作，输入一个节点 A，输出该节点所在的连通块中的节点数量。 35. scanf("%d",&a); 36. int x=find(a); 37. printf("%d\n",num[x]); 38. } 39. } 40. return 0; 41. }
