什么是并查集？

并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，常用于處理一些不相交集合（Disjoint Sets）的合并及查詢問題。

并查集可以高效的進行如下操作：

• 合并兩個不相同的集合
• 判斷兩個元素是否屬于同一個集合

并查集常見操作

init()初始化所有元素獨立為一個集合(即父節(jié)點是自身)

• 定義數(shù)組fa[],fa[x]存儲x的父節(jié)點。
• 初始化所有元素的父節(jié)點為-1,若fa[x]=-1則代表元素x自身為一個集合。

void init(){
    memset(fa,-1,sizeof(fa));//
}

find()查找元素所在的集合返回根節(jié)點

• 如果x獨立為一個集合，返回x，否則返回fa[x]。

int find(int x){
    if(fa[x]==-1) return x;
    return find(fa[x]);
}

unite(x,y)合并兩個不相同的集合

• 先找到x和y的代表元素。
• 如果相同，則說明x和y已經(jīng)屬于同一個集合，不用處理。
• 如果不同，將一個代表元素指向另一個代表元素。

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y) return;
    fa[x]=y;
}

same(x,y)判斷兩個元素是否屬于同一個集合

• 分別找到x和y的代表元素。
• 如果相同，說明x和y屬于同一個集合。

bool same(int x,int y){
    return find(x)==find(y);
}

并查集的優(yōu)化

路徑壓縮

尋找父節(jié)點是采用遞歸的方法，不采取任何判斷的合并，樹有可能會退化成一條鏈，每次find都會是O(n)的復(fù)雜度。所以必須進行路徑壓縮。在我們找到根節(jié)點的時候，直接把根節(jié)點作為它的父節(jié)點。

int find(int x){
    if(fa[x]==-1) return x;
    return fa[x=]find(fa[x]);
}

按樹的高度合并

合并時將元素所在深度低的集合合并到元素所在深度高的集合。

• 定義一個deep[]數(shù)組，默認只有一個節(jié)點的集合深度為0；
• 在unite()操作中，判斷x和y的高度，將高度小的樹連接到另一顆樹的根節(jié)點上。

void unite(int x,int y){
    
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(deep[x]<deep[y]) fa[x]=y;
    else{
        fa[y]=x;
        if(deep[x]==deep[y]) deep[x]++;
    }
}

優(yōu)化后的代碼

int fa[N],deep[N];
void init(){
    memset(fa,-1,sizeof(fa));
    memset(deep,0,sizeof(deep));
}
int find(int x){
    if(fa[x]==-1) return x;
    return fa[x=]find(fa[x]);
}
void unite(int x,int y){
    
    x=find(x);
    y=find(y);
    if(x==y) return;
    if(deep[x]<deep[y]) fa[x]=y;
    else{
        fa[y]=x;
        if(deep[x]==deep[y]) deep[x]++;
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}