c++中并查集實(shí)現(xiàn)

何謂并查集

并查集實(shí)際上就是并集和查集的過程非驮。那么什么是集呢?你可以把他近似地理解為一棵樹。即一個(gè)根結(jié)點(diǎn)連著無數(shù)個(gè)子節(jié)點(diǎn)阐肤。

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

給出例題:例題源網(wǎng)站(洛谷)
這里附:
題目描述

如題,現(xiàn)在有一個(gè)并查集讲坎,你需要完成合并和查詢操作孕惜。

輸入輸出格式

輸入格式:
第一行包含兩個(gè)整數(shù)N、M晨炕,表示共有N個(gè)元素和M個(gè)操作衫画。

接下來M行,每行包含三個(gè)整數(shù)Zi瓮栗、Xi削罩、Yi

當(dāng)Zi=1時(shí),將Xi與Yi所在的集合合并

當(dāng)Zi=2時(shí)费奸,輸出Xi與Yi是否在同一集合內(nèi)弥激,是的話輸出Y;否則話輸出N

輸出格式:
如上货邓,對(duì)于每一個(gè)Zi=2的操作秆撮,都有一行輸出,每行包含一個(gè)大寫字母换况,為Y或者N

輸入輸出樣例

輸入樣例#1:
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
輸出樣例#1:
N
Y
N
Y
這就是最最基礎(chǔ)的并查集模版了

初始化

我們會(huì)用到一個(gè)father數(shù)組职辨,記錄每一個(gè)節(jié)點(diǎn)的根結(jié)點(diǎn)
最初要把每一個(gè)節(jié)點(diǎn)都當(dāng)作一個(gè)集盗蟆,即

    father[i]=i;

這里我們需要用一個(gè)循環(huán)來實(shí)現(xiàn),完整代碼如下

    for(int i=1;i<=n;/*n即n個(gè)元素*/i++)
        father[i]=i;

然后初始化就完成啦舒裤。喳资。

函數(shù)

并查集一定會(huì)用到一個(gè)getfather函數(shù)(其實(shí)名字你隨便起)
這個(gè)函數(shù)就是去找根節(jié)點(diǎn)

int getfather(int x)//找x的根結(jié)點(diǎn)
{//這其實(shí)是一個(gè)遞歸函數(shù)
    if(father[x]==x)//邊界條件,如果x的根結(jié)點(diǎn)就是x(也就是說它沒有更上邊的祖宗了)
        return x;//就會(huì)返回x的值
    else
    {
        father[x]=getfather(father[x]); //不然的話就會(huì)一級(jí)一級(jí)找上去(先找到它爸爸腾供,在找到它爸爸的爸爸仆邓,再找到它爸爸的爸爸的爸爸。伴鳖。节值。。榜聂。)
    }
    return father[x];
}

讀入

先上代碼吧搞疗。。畢竟沒什么難度

for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z[i],&x[i],&y[i]);
        z1[i]=getfather(x[i]);//z1數(shù)組用于存儲(chǔ)每一個(gè)x[i]的根結(jié)點(diǎn)
        z2[i]=getfather(y[i]);//z2數(shù)組用于存儲(chǔ)每一個(gè)y[i]的根結(jié)點(diǎn)
    }

并集

目的就是讓一個(gè)集合的根結(jié)點(diǎn)成為另一個(gè)集合的根結(jié)點(diǎn)须肆,這樣這兩個(gè)集合就有同一個(gè)根結(jié)點(diǎn)匿乃,就起到了合并的作用。(比如說小明的爺爺也是小李的爺爺豌汇,他倆就是親戚)
代碼如下

if(z[i]==1)
    {
        if (z1[i]!=z2[i])
            Union(z1[i],z2[i]);
    }

這個(gè)Union是我自己寫的一個(gè)函數(shù)幢炸,它長這樣:

void Union(int xx,int yy)
{
    int f1=getfather(xx);//f1就是 xx的根結(jié)點(diǎn)
    int f2=getfather(yy);//f2就是yy的根結(jié)點(diǎn)
    father[f1]=f2;//讓xx的根結(jié)點(diǎn)成為yy的根結(jié)點(diǎn)(上面有解釋)
    return;
}

由于這是一個(gè)void函數(shù),所以你也可以直接把代碼 粘出來拒贱。

查集

鑒于我們已經(jīng)做過并集的工作宛徊,查集就變得輕松了很多,我們只需要確認(rèn)兩個(gè)點(diǎn)是否有 同一個(gè)根結(jié)點(diǎn)就行了柜思,代碼如下:

if(z[i]==2)
    {
        if(getfather(x[i])==getfather(y[i]))//如果 x[i]的根結(jié)點(diǎn)就是y[i]的根結(jié)點(diǎn)
        {
            cout<<"Y"<<endl;//就輸出y
        }
        else
        {
            cout<<"N"<<endl;//不然就輸出 n
        }
    }

應(yīng)該不難懂吧岩调?

本題完整代碼如下

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,father[200000];
int z[200000],y[200000],x[200000];
int getfather(int x)
{
    if(father[x]==x)
        return x;
    else
    {
        father[x]=getfather(father[x]); 
    }
    return father[x];
}
void Union(int xx,int yy)
{
    int f1=getfather(xx);
    int f2=getfather(yy);
    father[f1]=f2;
    return;
}
int main()
{
    int z1[200000],z2[200000];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z[i],&x[i],&y[i]);
        z1[i]=getfather(x[i]);
        z2[i]=getfather(y[i]);
    }
    for(int i=1;i<=m;i++)
    {
        if(z[i]==1)
        {
            if (z1[i]!=z2[i])
                Union(z1[i],z2[i]);
        }
        if(z[i]==2)
        {
            if(getfather(x[i])==getfather(y[i]))
            {
                cout<<"Y"<<endl;
            }
            else
            {
                cout<<"N"<<endl;
            }
        }
    }
    return 0;
}

還是建議自己去寫一遍。
這里還有幾道題
極其類似模版的題
局域網(wǎng)
營救
不會(huì)的可以自己去看一下題解赡盘。

tks

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末号枕,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子陨享,更是在濱河造成了極大的恐慌葱淳,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件抛姑,死亡現(xiàn)場(chǎng)離奇詭異赞厕,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)定硝,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門皿桑,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人,你說我怎么就攤上這事诲侮《婆埃” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵沟绪,是天一觀的道長刮便。 經(jīng)常有香客問我,道長绽慈,這世上最難降的妖魔是什么恨旱? 我笑而不...
    開封第一講書人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮坝疼,結(jié)果婚禮上搜贤,老公的妹妹穿的比我還像新娘。我一直安慰自己裙士,他們只是感情好入客,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著腿椎,像睡著了一般。 火紅的嫁衣襯著肌膚如雪夭咬。 梳的紋絲不亂的頭發(fā)上啃炸,一...
    開封第一講書人閱讀 52,713評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音卓舵,去河邊找鬼南用。 笑死,一個(gè)胖子當(dāng)著我的面吹牛掏湾,可吹牛的內(nèi)容都是我干的裹虫。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼融击,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼筑公!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起尊浪,我...
    開封第一講書人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤匣屡,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后拇涤,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體捣作,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年鹅士,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了券躁。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖也拜,靈堂內(nèi)的尸體忽然破棺而出旭贬,到底是詐尸還是另有隱情,我是刑警寧澤搪泳,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布稀轨,位于F島的核電站,受9級(jí)特大地震影響岸军,放射性物質(zhì)發(fā)生泄漏奋刽。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一艰赞、第九天 我趴在偏房一處隱蔽的房頂上張望佣谐。 院中可真熱鬧,春花似錦方妖、人聲如沸狭魂。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽雌澄。三九已至,卻和暖如春杯瞻,著一層夾襖步出監(jiān)牢的瞬間镐牺,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來泰國打工魁莉, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留睬涧,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓旗唁,卻偏偏與公主長得像畦浓,于是被迫代替她去往敵國和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子检疫,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容