Template series-union set

并查集模板

1、初始化

void init{
    
	for(int i=1;i<=n;i++){
    
        fa[i]=i;//把结点iThe set number of is initialized to its own number
	}
}

2、查找

版本一：

int find(int i){
    
	while(i!=pi[i]){
    
        i=pi[i]=pi[pi[i]];
    }
	return pi[i];
}

版本二：

int find(int x) {
    
    if(x != fa[x]){
    //当xNot equal to its dad(when it is an ancestor,it has no dad) 
         fa[x] = find(fa[x]);//Keep looking for his dad's dad 
    }
    return fa[x];//返回祖先 
}//查找 

3、合并

void unity(int x, int y){
    
    int r1 = find(x);//找到x的祖先 
    int r2 = find(y);//找到y的祖先 
    if(r1!=r2){
    
        fa[r1] = r2;//Ancestors and ancestors become father and son(Anyone can be a father or a son) 
    }
}//合并