看黑书看到并查集，练了一道并查集的题目，很典型，不是很难，但是细节上的处理还是比较容易出错的。

理解题意之后，首先对状态进行建模。分别建立三个数组，意义如下

int father[i];//记录 i 的父亲节点，注意不一定是根节点，路径压缩之后才一定是根节点

int total[i];//记录集合中元素个数，仅当i为根节点该值才有意义

int deep[i];//每棵树距离父亲的距离，注意不是根树，所以每次进行路径压缩压缩的时候，将原父亲改为根节点时不要忘记将深度值也同时进行修改

如果输入为M i j 那么就调用合并函数unin(i,j)

如果输入为C i 那么就首先查处i所在集合的根节点fatherI,在调用find(i)的同时，deep[i]也由于路径压缩，所以记录的一定为i到根节点的距离，所以 i所在集合的总的元素个数（即为total[fatherI]）减去(deep[i]+1)即为i后面的元素个数，问题得以求解

还需要提到的一点就是，在find()函数中的路径压缩阶段，比较啰嗦，尤其是对deep[]数组的修改，两个迭代缠在一起，并非同步，看代码即可知道，在每一次循环中，修改father[son]的父亲为root的后，修改的不是deep[son],而是deep[father[son]],自己画画图就清楚了。

代码如下：

#include
     
       using namespace std; const int SIZE = 30005; int father[SIZE];//记录每棵树的根节点（集合标记值） int total[SIZE];//记录集合中元素个数，仅根节点该值有意义 int deep[SIZE];//每棵树距离父亲的距离，注意不是根树，所以每次要进行路径压缩 //只有父亲直接指向树根，deep[i]值才是实际到树根的深度 void init(int n){
   for(int i=1;i<=n;i++){
           father[i]=i;         total[i]=1;         deep[i]=0;     } } int find(int i){
   int depth =deep[i]; int son = i; while(i!=father[i]){
           i=father[i];         depth+=deep[i];     }//找到根节点为i //路径压缩，同时进行deep[]数组的修改     int temp,tempLen=deep[son],tempLen2;     deep[son]=depth;//因为每次总是修改父亲的深度，所以现将第一个的深度修改掉     while(son!=father[son]){
           temp=father[son];         tempLen2 = deep[temp];//几下父亲最初和“父亲的父亲”的距离,为了实现迭代过程         father[son]=i;//路径压缩         deep[temp]=deep[son]- tempLen;         tempLen=tempLen2;//迭代 实现         son=temp;//迭代 实现     } return i; } void  unin(int i,int j){
   int fatherI= find(i); int fatherJ=find(j);     father[fatherJ]=fatherI;//合并     deep[fatherJ]=total[fatherI];//j所在集合要放在i所在集合的下面     total[fatherI]+=total[fatherJ];//两个集合合并之后修改根节点所包含的总的元素个数     return ; } int main(){
   int P,a,b,root;     cin>>P;     init(SIZE); char choice; while(P--){
           cin>>choice; if(choice=='M'){
               cin>>a>>b;             unin(a,b);         } else if(choice=='C'){
               cin>>a;             root=find(a);             cout<
      
       <