并查集模板

 并查集模板（寻找祖先用递归实现）：

#include<stdio.h>
#include<string.h>

const int maxn=1e5+5;
int fa[maxn];

void init(int n){        //初始化函数
    for(int i=0;i<=n;i++)fa[i]=i;
}

int find(int x){        //寻找祖宗
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void unio(int x,int y){    //合并两点
    int dx=find(x),dy=find(y);
    if(dx!=dy)fa[dx]=dy;
}

并查集模板（寻找祖先用循环实现，速度上并没有发现显著提高，但学长说可以避免卡栈溢出，合并过程直接在主函数内实现）：

#include<stdio.h>
#include<string.h>

const int maxn=1e5+5;
int fa[maxn];

void init(int n){
    for(int i=0;i<=n;i++)fa[i]=i;
}

int find(int x){
    int r=x,t;
    while(r!=fa[r])r=fa[r];        //先循环一遍寻找祖先
    while(x!=r){                //再循环一遍更新父亲结点
        t=fa[x];
        fa[x]=r;
        x=t;
    }
    return r;
}

int x=find(a),y=find(b);        //主函数中完全可以直接实现合并
if(x!=y)fa[x]=y;

 

带权并查集（仅记录集合元素个数）：

#include<stdio.h>
#include<string.h>

const int maxn=1e5+5;
int fa[maxn],num[maxn];

void init(int n){
    for(int i=0;i<=n;i++){fa[i]=i;num[i]=1;}    //初始化每个集合元素个数为1
}

int find(int x){
    int r=x,t;
    while(fa[r]!=r)r=fa[r];
    while(x!=r){
        t=fa[x];
        fa[x]=r;
        x=t;
    }
    return r;
}

int x=find(a),y=find(b);
if(x!=y){
    fa[x]=y;
    num[y]+=num[x];        //合并集合时在祖先结点上改合并后的集合元素个数
}

  

种类并查集（本质也是带权并查集，但是是记录元素的性质的，权值一般表示与父亲结点的关系）：

#include<stdio.h>
#include<string.h>

const int maxn=1e5+5;
int fa[maxn],num[maxn];

void init(int n){
    for(int i=0;i<=n;i++){
        fa[i]=i;
        num[i]=0;        //此处表示和父亲节点的大小差距，初始化0
    }
}

int find(int x){                //这里压缩路径并更新结点权值的思想是先循环加每个结点到父节点的权值，再次循环时每次减去之前更新完的权值再更新
    int r=x,t1,t2,c=0;
    while(r!=fa[r]){
        c+=num[r];
        r=fa[r];
    }
    while(x!=r){
        t1=fa[x];
        t2=c-num[x];
        num[x]=c;
        fa[x]=r;
        c=t2;
        x=t1;
    }
    return r;
}

int x=find(a),y=find(b);
if(x!=y){            //合并时的操作
    fa[x]=y;
    num[x]=num[b]+v-num[a];
}