欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C/C++并查集的查詢與合并實現(xiàn)原理

 更新時間:2023年02月13日 09:32:52   作者:Ggggggtm  
這篇文章主要介紹了C/C++并查集的查詢與合并,并查集是一種用來管理元素分組情況的數(shù)據(jù)結構。并查集可以高效地進行如下操作

標題:并查集的查詢與合并詳解 作者:@Ggggggtm 寄語:與其忙著訴苦,不如低頭趕路,奮路前行,終將遇到一番好風景

一、并查集的概念

并查集是一種樹形的數(shù)據(jù)結構。使用樹型結構來存儲數(shù)據(jù)。樹根的編號即為整個樹的標號,且每個節(jié)點存儲的數(shù)據(jù)是他的父節(jié)點下標。

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

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

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

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

我們把并查集不同集合(樹)的實現(xiàn)主要分為以下幾個點:

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

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

(元素所屬于樹的祖宗)

我們查找一個元素的集合,把元素的當作下標傳給find()函數(shù),代碼如下:

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

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

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

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

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

//合并  把a的祖宗節(jié)點的父節(jié)點當作b的祖宗結點
p[find(a)]=find(b);

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

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

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

5.并查集例題訓練1

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

現(xiàn)在要進行m個操作,操作共有兩種:

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

輸入格式:

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

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

輸出格式:

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

每個結果占一行。

數(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的祖宗節(jié)點的父節(jié)點當作b的祖宗結點
            p[find(a)]=find(b);
        }
        else
        {
            if(find(a)==find(b))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    }
    return 0;
}

6.并查集例題訓練2

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

現(xiàn)在要進行mm個操作,操作共有三種:

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

輸入格式

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

接下來mm行,每行包含一個操作指令,指令為C a bQ1 a bQ2 a中的一種。

輸出格式

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

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

每個結果占一行。

數(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)計一個集合元素的個數(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ù)不斷增加。

三、總結

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

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

相關文章

  • MFC實現(xiàn)對話框編輯控件上拖拽文件

    MFC實現(xiàn)對話框編輯控件上拖拽文件

    這篇文章主要為大家詳細介紹了MFC實現(xiàn)對話框編輯控件上拖拽文件,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-06-06
  • C++解析obj模型文件方法介紹

    C++解析obj模型文件方法介紹

    由于本人打算使用Assimp來加載模型,這里記錄一下tinyobjloader庫的使用。之前也研究過fbxsdk,除了骨骼動畫暫未讀取外,代碼自認為還算可靠
    2022-09-09
  • c++ KMP字符串匹配算法

    c++ KMP字符串匹配算法

    大家好,本篇文章主要講的是c++ KMP字符串匹配算法,感興趣的同學趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-01-01
  • C語言實現(xiàn)磁盤映射

    C語言實現(xiàn)磁盤映射

    磁盤映射技術通過將文件映射到內(nèi)存中,提高了文件操作的效率,本文就來介紹一下C語言實現(xiàn)磁盤映射,感興趣的可以了解一下
    2024-09-09
  • 代碼分析c++中string類

    代碼分析c++中string類

    本篇內(nèi)容通過詳細的源代碼詳細分析了C++中string類的用法以及知識點,有興趣的讀者們參考下。
    2018-03-03
  • C語言實現(xiàn)萬年歷小程序

    C語言實現(xiàn)萬年歷小程序

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)萬年歷小程序,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-10-10
  • C語言基礎指針詳解教程

    C語言基礎指針詳解教程

    此處對于指針做一些簡要的介紹,作者實屬初學,寫博客也是作者學習的一個過程,難免文章中有內(nèi)容理解不到位或者有不當之處,還請朋友們不吝指正,希望大家給予支持
    2021-11-11
  • C++類和對象實例解析(二)

    C++類和對象實例解析(二)

    這篇文章主要介紹了C++類和對象,從定義出發(fā)再到實例解析,深入的理解C++類和對象,需要的朋友可以參考下
    2015-08-08
  • win10環(huán)境下C++ vs2015編譯opencv249的教程

    win10環(huán)境下C++ vs2015編譯opencv249的教程

    這篇文章主要介紹了win10環(huán)境下C++ vs2015編譯opencv249的教程,本文分步驟給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-03-03
  • C++使用CriticalSection實現(xiàn)線程同步實例

    C++使用CriticalSection實現(xiàn)線程同步實例

    這篇文章主要介紹了C++使用CriticalSection實現(xiàn)線程同步實例,是使用CriticalSection對前文實例的擴展,具有一定的參考借鑒價值,需要的朋友可以參考下
    2014-10-10

最新評論