〔C++算法分析〕并查集

? ? ? ? 并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合(Disjoint Sets)的合并及查詢問題。常常在使用中以森林來表示届谈。

? ? ? ? 舉個例子,某鄉(xiāng)鎮(zhèn)有多個村子弯汰,為了出行方便艰山,需要進(jìn)行修路,使所有村子連在一起咏闪。


某鄉(xiāng)鎮(zhèn)

????????現(xiàn)在曙搬,按照如下pair修路,按順序如果兩村之間已經(jīng)可以互相到達(dá)則不需要再修路。(不將就距離問題纵装,只看是否連通)

? ? ? ? 1.5? ? 2.4? ? 1.6? ? 6.7? ? 1.7????3.4? ? 3.6? ? 1.2

路線

? ? ? ? 如圖進(jìn)行連接 征讲,綠色的為修路的路線,紅色的為按順序不必要修的路線橡娄。

? ? ? ? 整體路線大概為2-4-3-6-1(7)-5诗箍。

? ? ? ? 正如標(biāo)題所說,形成的一種樹狀圖形挽唉,其中節(jié)點6的度為2滤祖。


? ? ? ? 那么問題來了,我們?nèi)绾尾拍苤榔孔眩@個兩個節(jié)點是否已經(jīng)是連在一條線上的呢匠童?

????????這里我們采用數(shù)組的方法來解決。

? ? ? ? 首先塑顺,我們需要一個數(shù)組汤求,數(shù)組的下標(biāo)即是村莊(節(jié)點)。然后严拒,我們的到需要修路的村莊pair扬绪,我們先驚醒判定,如果兩村莊不在一條線上糙俗,就綁在一條線上(綁定方法為找頭)勒奇,如果已經(jīng)在一條線上,就不做處理巧骚。

????????找頭的時候赊颠,我們需要先對數(shù)組進(jìn)行初始化,初始化為數(shù)組的值為數(shù)組的下標(biāo)劈彪。而這個下標(biāo)節(jié)點對應(yīng)的值便是這個節(jié)點的上級頭目竣蹦,一直向上尋找,當(dāng)下標(biāo)節(jié)點的值等于下標(biāo)時沧奴,便是頭痘括。

for(int i = 0; i < n; i++)

? ? v[i] = i;

? ? ? ? 然后,我們通過調(diào)用函數(shù)的方式滔吠,對得到的一組村莊進(jìn)行判定纲菌,如果二者的頭是同一個數(shù)組下標(biāo),則為統(tǒng)一條線的村莊疮绷,如果頭的下標(biāo)不同翰舌,則是兩條不同的線,可以進(jìn)行連線冬骚。

連線的方式也很普通椅贱,由于找頭之后懂算,節(jié)點目前的位置在頭處,只需將其中一個頭連接到另一個頭上即可庇麦。

int getf(int v){

????if(v == f[v])

????????return v;

????return f[v] = getf(f[v]);

}

void merge(int v,int u){

????int t1 = getf(v);

????int t2 = getf(u);

????if(t1 != t2)

????????f[t1] = t2;

}

不必?fù)?dān)心计技,兩個頭誰連接到誰的問題,因為都是頭山橄,無論誰連接到誰垮媒,被連接的部分不變,連接的部分得到一個新頭驾胆。如圖所示:

????圖中涣澡,1與2已經(jīng)相連,需要對2和3進(jìn)行連接丧诺,已經(jīng)查到2的頭為1(f【2】=1,f【1】=1)奄薇,3的頭為3(f【3】=3)驳阎,我們得到兩種連接方式,分別為

1馁蒂、連接結(jié)果為f【2】=1? ? f【1】=1????f【3】=1? ? 2(3)-1

2呵晚、連接結(jié)果為f【2】=1? ? f【1】=3? ? f【3】=3? ? 2-1-3


按照以上操作將需要處理的數(shù)據(jù)處理完,我們就通過并查集獲得多條線(稱為樹更合適)沫屡,這些線在一起饵隙,組成森林,我們通過遍歷的方式沮脖,對每個數(shù)組下標(biāo)進(jìn)行遍歷金矛,如果此下標(biāo)的頭第一次出現(xiàn),計數(shù)器++勺届,如果已經(jīng)出現(xiàn)驶俊,跳過,遍歷結(jié)束免姿,我們即可得到森林里有多少顆樹饼酿。

并查集可以做很多題目

1.暢通工程(修路)

2.食物鏈判斷

3.判斷是否為樹

4.將很多人按照熟悉的人進(jìn)行分組

等等。胚膊。故俐。


by:有我wa

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市紊婉,隨后出現(xiàn)的幾起案子药版,更是在濱河造成了極大的恐慌,老刑警劉巖肩榕,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件刚陡,死亡現(xiàn)場離奇詭異惩妇,居然都是意外死亡,警方通過查閱死者的電腦和手機筐乳,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進(jìn)店門歌殃,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人蝙云,你說我怎么就攤上這事氓皱。” “怎么了勃刨?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵波材,是天一觀的道長。 經(jīng)常有香客問我身隐,道長廷区,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任贾铝,我火速辦了婚禮隙轻,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘垢揩。我一直安慰自己玖绿,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布叁巨。 她就那樣靜靜地躺著斑匪,像睡著了一般。 火紅的嫁衣襯著肌膚如雪锋勺。 梳的紋絲不亂的頭發(fā)上蚀瘸,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天,我揣著相機與錄音宙刘,去河邊找鬼苍姜。 笑死,一個胖子當(dāng)著我的面吹牛悬包,可吹牛的內(nèi)容都是我干的衙猪。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼布近,長吁一口氣:“原來是場噩夢啊……” “哼垫释!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起撑瞧,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤善已,失蹤者是張志新(化名)和其女友劉穎苦蒿,沒想到半個月后熙揍,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡曼尊,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了脏嚷。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片骆撇。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖父叙,靈堂內(nèi)的尸體忽然破棺而出神郊,到底是詐尸還是另有隱情,我是刑警寧澤趾唱,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布涌乳,位于F島的核電站,受9級特大地震影響甜癞,放射性物質(zhì)發(fā)生泄漏夕晓。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一带欢、第九天 我趴在偏房一處隱蔽的房頂上張望运授。 院中可真熱鬧,春花似錦乔煞、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至雄右,卻和暖如春空骚,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背擂仍。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工囤屹, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人逢渔。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓肋坚,卻偏偏與公主長得像,于是被迫代替她去往敵國和親肃廓。 傳聞我的和親對象是個殘疾皇子智厌,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,876評論 2 361

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