考研中给的参考并查集p数组担任找爹和计以此为根总结点数的功能，功能多一点，坏处是路径压缩代码不简洁，初始化是全部为-1.竞赛里常用的是初始话为i，好处是代码简洁，但要计数的话要多开一个数组

#include<bits/stdc++.h>
using namespace std;
const int maxsize = 20;


void initial(int p[]){
    for(int i=0;i<maxsize;i++)p[i]=-1;
}

int find(int p[],int x){
    int root = x;
    while(p[root]>=0)root = p[root];//找根
    while(x!=root){//路径压缩，把经过的点直接接到root上
        int t = p[x];
        p[x] = root;
        x = t;
    }
    return root;
}

void add(int p[],int a,int b){
    int pa = find(p,a) , pb = find(p,b);
//  printf("%d %d\n",pa,pb);
    if(pa==pb)return;
    if(p[pa]>p[pb]){//小树合并大树，pa为负数，绝对值表示以此为根的节点数量 pa结点少
        p[pb]+=p[pa];
        p[pa]=pb;//pa认pb为爹
    }else{//pb<pa
        p[pa]+=p[pb];
        p[pb]=pa;
    }
}

int main(){
    int p[maxsize];
    initial(p);
    add(p,1,2);
    add(p,3,4);
    add(p,5,6);
    add(p,7,8);
    add(p,0,5);
    add(p,1,9);
    add(p,9,3);
    add(p,8,0);
    add(p,4,6);
    for(int i=0;i<maxsize;i++)  printf("%d %d\n",i,p[i]);

    return 0;
}