【基礎算法】并查集

定義

并查集是一種資料結構，可以高效的實作對【集合】的【并】與【查】操作

• 查找（Find）：确定某個元素處于哪個子集；
• 合并（Union）：将兩個子集合并成一個集合。

實作思路

• p[i]為i節點的父節點的值
• 每一個集合都可以用一個樹表示
• p[i]=i表示該節點為所在集合的樹的根節點
• 給數組p初始化指派，設其值為p[i]=i，也即是說，p[1]=1,p[2]=2，以此類推。

  

• 如果p[2]=1，p[3]=2則有：3節點的父節點為2，2節點的父節點為1，1節點的父節點為1，是以1為根節點。【1、2、3】在同一個集合内

  

代碼

查詢

• 查找一個集合的根節點（由于每個集合都可以用一個樹形結構來表示，是以該樹的根節點可以唯一标志一個集合）。下面代碼在查找根節點的過程中附帶了路徑壓縮功能
• 路徑壓縮前：

  

• 路徑壓縮後：

  

int find(int x)//尋找x的父節點
{
    if(p[x]!=x)//說明x不是根節點，是以尋找x的父節點的父節點，并且通過指派進行路徑壓縮
        p[x]=find(p[x]);
    return p[x];
}
           

合并

合并兩個集合隻需将一個集合的根節點指向另一個集合的根節點即可

合并a，b兩個集合：p[find(a)]=find(b);

#include <iostream>

using namespace std;

const int N=1e5+10;

int p[N];

int find(int x)//尋找x的父節點
{
    if(p[x]!=x)//說明x不是根節點，是以尋找x的父節點的父節點，并且通過指派進行路徑壓縮
        p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i]=i;
    
    for(int i=0;i<m;i++)
    {
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='M')//将a，b集合合并
            p[find(a)]=find(b);
        else if(c=='Q')//查詢a，b是否在一個集合内
            if(find(a)==find(b)) puts("Yes");
            else puts("No");
    }
    
    return 0;
}