標(biāo)題：并查集的查詢與合并詳解 作者：@Ggggggtm 寄語：與其忙著訴苦，不如低頭趕路，奮路前行，終將遇到一番好風(fēng)景

一、并查集的概念

并查集是一種樹形的數(shù)據(jù)結(jié)構(gòu)。使用樹型結(jié)構(gòu)來存儲數(shù)據(jù)。樹根的編號即為整個樹的標(biāo)號，且每個節(jié)點(diǎn)存儲的數(shù)據(jù)是他的父節(jié)點(diǎn)下標(biāo)。

并查集被很多OIer認(rèn)為是最簡潔而優(yōu)雅的數(shù)據(jù)結(jié)構(gòu)之一，主要用于解決一些元素分組的問題。它管理一系列不相交的集合，并支持兩種操作：

• 合并（Union）：把兩個不相交的集合合并為一個集合。
• 查詢（Find）：查詢兩個元素是否在同一個集合中。

二、并查集的實(shí)現(xiàn)

1.并查集不同集合(樹)的形成

我們把并查集不同集合（樹）的實(shí)現(xiàn)主要分為以下幾個點(diǎn)：

• 我們先給出n個數(shù)據(jù)，把n個數(shù)據(jù)存儲到不同的集合當(dāng)中（p[ i ] = i），在這里我們把每個p[ i ]分別看成一個不同集合（也就是一棵樹）。
• p[ i ] = i，i即為這棵樹的編號，這顆樹下面的孩子節(jié)點(diǎn)存儲的數(shù)據(jù)是父節(jié)點(diǎn)的下標(biāo)。
• 當(dāng)p[ i]=i 時，就相當(dāng)于找到了根節(jié)點(diǎn)。
• 我們剛開始每個集合中的元素只有一個。后續(xù)合并后，集合元素個數(shù)不斷增加。

2.find()函數(shù)找一個元素集合的編號

（元素所屬于樹的祖宗）

我們查找一個元素的集合，把元素的當(dāng)作下標(biāo)傳給find()函數(shù)，代碼如下：

int find(int x)
{
    if(p[x]!=x)
    {
        p[x]=find(p[x]);
    }
    return p[x];
}

我們p[x]中存儲的正是他的父節(jié)點(diǎn)，從而就可以一直往上查找，直到p[ x ]=x時結(jié)束。當(dāng)p[ x ]=x時，就相當(dāng)于找到了根節(jié)點(diǎn)。此時的p[ x ]存儲的是這棵樹的編號。我這發(fā)現(xiàn)，剛開始每個集合當(dāng)中都只有一個元素，也就是p[ x ]，后面我們會對不同的集合進(jìn)行合并，使得一個集合有多個元素。

我們再找祖宗節(jié)點(diǎn)時進(jìn)行了路徑壓縮。什么是路徑壓縮呢？路徑壓縮就是我們在查找某個元素的祖宗時，在找父節(jié)點(diǎn)的這條路經(jīng)上的元素都指向祖宗節(jié)點(diǎn)，以便于我們后面的查找的時間復(fù)雜度近乎O（1）。

3.合并兩個不同集合(合并兩棵不同的樹)

我們直到了每棵樹的根節(jié)點(diǎn)存儲的是這個樹的編號，而不是父節(jié)點(diǎn)。當(dāng)我們要合并兩顆樹時，我們只需要把一棵樹的根節(jié)點(diǎn)存儲的編號改為另一棵樹的根節(jié)點(diǎn)編號。簡單的理解就是一個樹的根節(jié)不再是根節(jié)點(diǎn)，而是一個子節(jié)點(diǎn)，該樹的根節(jié)點(diǎn)存儲的也不再是編號，而是存儲的父節(jié)點(diǎn)，該父節(jié)點(diǎn)就是另一棵樹的根節(jié)點(diǎn)。我們看代碼：

//合并  把a(bǔ)的祖宗節(jié)點(diǎn)的父節(jié)點(diǎn)當(dāng)作b的祖宗結(jié)點(diǎn)
p[find(a)]=find(b);

4.查詢兩個元素是否在一個集合

我們有了find（）函數(shù)，就可以很簡單的判斷出兩個元素的是否在同一個集合當(dāng)中（兩個元素是否在同一個樹中）。我們只需要判斷兩個元素集合的編號是否相同（兩個元素的祖宗節(jié)點(diǎn)是否相同）即可。我們看代碼：

//看a、b兩個元素是否在同一個集合當(dāng)中
if(find(a)==find(b))
    cout<<"Yes"<<endl;
else
    cout<<"No"<<endl;

5.并查集例題訓(xùn)練1

一共有 n 個數(shù)，編號是1∼n，最開始每個數(shù)各自在一個集合中。

現(xiàn)在要進(jìn)行m個操作，操作共有兩種：

• M a b，將編號為a和b的兩個數(shù)所在的集合合并，如果兩個數(shù)已經(jīng)在同一個集合中，則忽略這個操作；
• Q a b，詢問編號為a和b的兩個數(shù)是否在同一個集合中；

輸入格式：

第一行輸入整數(shù)n和m。

接下來m行，每行包含一個操作指令，指令為M a b或Q a b中的一種。

輸出格式：

對于每個詢問指令Q a b，都要輸出一個結(jié)果，如果a和b在同一集合內(nèi)，則輸出Yes，否則輸出No。

每個結(jié)果占一行。

數(shù)據(jù)范圍：

1≤n,m≤10e5 1≤n,m≤10e5

輸入樣例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

輸出樣例：

Yes
No
Yes

答案如下：

#include<iostream>
using namespace std;
const int N=100010;
int p[N];
//找祖宗+路徑壓縮
int find(int x)
{
    if(p[x]!=x)
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        p[i]=i;
    while(m--)
    {
        char op[2];
        int a,b;
        cin>>op>>a>>b;
        if(op[0]=='M')
        {
            //合并  把a(bǔ)的祖宗節(jié)點(diǎn)的父節(jié)點(diǎn)當(dāng)作b的祖宗結(jié)點(diǎn)
            p[find(a)]=find(b);
        }
        else
        {
            if(find(a)==find(b))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
    return 0;
}

6.并查集例題訓(xùn)練2

給定一個包含nn個點(diǎn)（編號為1∼n1∼n）的無向圖，初始時圖中沒有邊。

現(xiàn)在要進(jìn)行mm個操作，操作共有三種：

• C a b，在點(diǎn)aa和點(diǎn)bb之間連一條邊，aa和bb可能相等；
• Q1 a b，詢問點(diǎn)aa和點(diǎn)bb是否在同一個連通塊中，aa和bb可能相等；
• Q2 a，詢問點(diǎn)aa所在連通塊中點(diǎn)的數(shù)量；

輸入格式

第一行輸入整數(shù)nn和mm。

接下來mm行，每行包含一個操作指令，指令為C a b，Q1 a b或Q2 a中的一種。

輸出格式

對于每個詢問指令Q1 a b，如果aa和bb在同一個連通塊中，則輸出Yes，否則輸出No。

對于每個詢問指令Q2 a，輸出一個整數(shù)表示點(diǎn)aa所在連通塊中點(diǎn)的數(shù)量

每個結(jié)果占一行。

數(shù)據(jù)范圍

1≤n,m≤1051≤n,m≤105

輸入樣例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

輸出樣例：

Yes
2
3

我們這個題相對于上個題就是對出了一個統(tǒng)計(jì)一個集合元素的個數(shù)。整體思路大同小異，我們直接看代碼解析：

#include<iostream>
using namespace std;
const int N=100010;
int p[N],cnt[N];
int find(int x)
{
    if(p[x]!=x)
    {
        p[x]=find(p[x]);
    }
    return p[x];
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        p[i]=i;
        cnt[i]=1;
    }
    while(m--)
    {
        char op[5];
        int a,b;
        scanf("%s",op);
        if(op[0]=='C')
        {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b))
                continue;
            cnt[find(b)]+=cnt[find(a)];
            p[find(a)]=find(b);
        }
        else if(op[1]=='1')
        {
            scanf("%d%d",&a,&b);
            if(find(a)==find(b))
                printf("Yes\n");
            else
                printf("No\n");
        }
        else
        {
            scanf("%d",&a);
            printf("%d\n",cnt[find(a)]);
        }
    }
    return 0;
}

注意，我們剛開始每個集合中的元素只有一個。后續(xù)合并后，集合元素個數(shù)不斷增加。

三、總結(jié)

我們主要掌握find（）函數(shù)，并查集算法中，最為核心的就是find（）函數(shù)。在這個算法中，路徑壓縮給我們的算法效率提高了很多，這個也是需要理解的。合并、查詢是并查集的兩個主要操作，我們也應(yīng)該熟悉理解。

到此這篇關(guān)于C/C++并查集的查詢與合并實(shí)現(xiàn)原理的文章就介紹到這了,更多相關(guān)C++并查集內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論