本文主要是介绍1389：亲戚(并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。
规定：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
思路：
最普通的并查集，思路应该没错但是不知道为啥总要几个测试点超时
代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
int n , m;
int f[100005] ;
int k[100005];
void init()
{for(int i = 1 ; i <= n ; i++){f[i] = i;k[i] = 1;}
}
int getf(int u)
{if( f[u] == u ) return u;else return getf(f[u]);
}
void merge1(int u , int v)
{int t1 = getf(u);int t2 = getf(v);if( t1 != t2){f[t2] = t1;k[t1] += k[t2];}
}
int main()
{char c;int x , y , z;cin>>n>>m;init();for(int i = 1 ; i <= m ; i++){cin>>c;if(c == 'M'){cin>>x>>y;merge1( x , y );}else{cin>>z;cout<<k[getf(z)]<<endl;}}
}
这篇关于1389：亲戚(并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
