并查集的应用---连通块中点的数量

例题引入：

给定一个包含 n 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

1. C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 a 所在连通块中点的数量；

输入格式

第一行输入整数 n 和 m。

接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤10^5

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

首先，对于题目中的要求操作，两个元素之间连接一条边和查询两个元素是否在同一个连通图中完全等价于我们在并查集中所讲到的让两个集合合并和查询两个元素是否处于同一集合的操作

这里就不再多讲

这个题目要注意的就是：

当我们在合并完两个连通图之后，那么有一个连通图的祖宗节点会发生改变，这样就会导致再求它的元素个数的时候发生错误，因此，在合并之前，先计算合并后的元素个数，不然会被卡住！！！

还有一个点是，我刚开始将重点放在了两个相等元素上，所以我的判断条件是a==b那么我们退出本轮循环，继续下一轮新的循环，不然的话我们就开始合并（这样做只要两个元素数值不相等就开始合并了，但是有一种可能是虽然元素不相同，但是他们处于一个连通图中，导致多加了合并操作，其次会使得节点长度错误），而真正的判断条件是：a和b的祖宗节点不相等则开始合并； 完美避免了冗余代码，思路十分清晰；

上代码：

#include<iostream>
using  namespace std;const int N=1e5+10;
int q[N];
int  s[N];
int find(int x){//查找x的祖宗节点if(q[x]!=x)q[x]=find(q[x]);//一直往上追溯，直到找到x的祖宗节点return q[x];//返回x的祖宗节点
}
int main(){int n,m;cin>>n>>m;string op;for(int i=1;i<=n;i++){q[i]=i;s[i]=1;}while(m--){cin>>op;if(op=="Q1"){//a和b是否在同一个连通块中，a和b可能相等int a,b;cin>>a>>b;if(find(a)==find(b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}else if(op=="Q2"){//a所在连通块中点的数量int a;cin>>a;cout<<s[find(a)]<<endl;}else{//a和b之间连一条边，a和b可能相等int a,b;cin>>a>>b;// a=find(a);//b=find(b);//if(find(a)==find(b))continue;if(find(a)!=find(b)){//两个孩子的祖宗节点不相等时则需要进行合并s[find(b)]+=s[find(a)];//b集合长度加上a的集合长度q[find(a)]=find(b);//将a的祖宗节点作为b祖宗节点的孩子，则实现了两个集合的相互连接//先加长度在调换祖宗节点，不然会使得结果错误（根节点变化导致）}}}return 0;
}