進階資料結構設計－－并查集及實作學習筆記（有趣篇）
并查集的程式設計：
為了解釋并查集的原理，我将舉一個更有趣的例子。
話說江湖上散落着各式各樣的大俠，有上千個之多。他們沒有什麼正當職業，整天背着劍在外面走來走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個優點就是講義氣，絕對不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，隻要是能通過朋友關系串聯起來的，不管拐了多少個彎，都認為是自己人。這樣一來，江湖上就形成了一個一個的群落，通過兩兩之間的朋友關系串聯起來。而不在同一個群落的人，無論如何都無法通過朋友關系連起來，于是就可以放心往死了打。但是兩個原本互不相識的人，如何判斷是否屬于一個朋友圈呢？我們可以在每個朋友圈内推舉出一個比較有名望的人，作為該圈子的代表人物，這樣，每個圈子就可以這樣命名“齊達内朋友之隊”“羅納爾多朋友之隊”……兩人隻要互相對一下自己的隊長是不是同一個人，就可以确定敵友關系了。
但是還有問題啊，大俠們隻知道自己直接的朋友是誰，很多人壓根就不認識隊長，要判斷自己的隊長是誰，隻能漫無目的的通過朋友的朋友關系問下去：“你是不是隊長？你是不是隊長？”這樣一來，隊長面子上挂不住了，而且效率太低，還有可能陷入無限循環中。于是隊長下令，重新組隊。隊内所有人實行分等級制度，形成樹狀結構，我隊長就是根節點，下面分别是二級隊員、三級隊員。每個人隻要記住自己的上級是誰就行了。遇到判斷敵友的時候，隻要一層層向上問，直到最高層，就可以在短時間内确定隊長是誰了。由于我們關心的隻是兩個人之間是否連通，至于他們是如何連通的，以及每個圈子内部的結構是怎樣的，甚至隊長是誰，并不重要。是以我們可以放任隊長随意重新組隊，隻要不搞錯敵友關系就好了。于是，門派産生了。
下面我們來看并查集的實作。
int pre[1000];
這個數組，記錄了每個大俠的上級是誰。大俠們從1或者0開始編号（依據題意而定），pre[15]=3就表示15号大俠的上級是3号大俠。如果一個人的上級就是他自己，那說明他就是掌門人了，查找到此為止。也有孤家寡人自成一派的，比如歐陽鋒，那麼他的上級就是他自己。每個人都隻認自己的上級。比如胡青牛同學隻知道自己的上級是楊左使。張無忌是誰？不認識！要想知道自己的掌門是誰，隻能一級級查上去。
find這個函數就是找掌門用的，意義再清楚不過了（路徑壓縮算法先不論，後面再說）。
再來看看join函數，就是在兩個點之間連一條線，這樣一來，原先它們所在的兩個闆塊的所有點就都可以互通了。這在圖上很好辦，畫條線就行了。但我們現在是用并查集來描述武林中的狀況的，一共隻有一個pre[]數組，該如何實作呢？
還是舉江湖的例子，假設現在武林中的形勢如圖所示。虛竹小和尚與周芷若MM是我非常喜歡的兩個人物，他們的終極boss分别是玄慈方丈和滅絕師太，那明顯就是兩個陣營了。我不希望他們互相打架，就對他倆說：“你們兩位拉拉勾，做好朋友吧。”他們看在我的面子上，同意了。這一同意可非同小可，整個少林和峨眉派的人就不能打架了。這麼重大的變化，可如何實作呀，要改動多少地方？其實非常簡單，我對玄慈方丈說：“大師，麻煩你把你的上級改為滅絕師太吧。這樣一來，兩派原先的所有人員的終極boss都是師太，那還打個球啊！反正我們關心的隻是連通性，門派内部的結構不要緊的。”玄慈一聽肯定火大了：“我靠，憑什麼是我變成她手下呀，怎麼不反過來？我抗議！”抗議無效，上天安排的，最大。反正誰加入誰效果是一樣的，我就随手指定了一個。這段函數的意思很明白了吧？
再來看看路徑壓縮算法。建立門派的過程是用join函數兩個人兩個人地連接配接起來的，誰當誰的手下完全随機。最後的樹狀結構會變成什麼胎唇樣，我也完全無法預計，一字長蛇陣也有可能。這樣查找的效率就會比較低下。最理想的情況就是所有人的直接上級都是掌門，一共就兩級結構，隻要找一次就找到掌門了。哪怕不能完全做到，也最好盡量接近。這樣就産生了路徑壓縮算法。
設想這樣一個場景：兩個互不相識的大俠碰面了，想知道能不能揍。
于是趕緊打電話問自己的上級：“你是不是掌門？”
上級說：“我不是呀，我的上級是誰誰誰，你問問他看看。”
一路問下去，原來兩人的最終boss都是東廠曹公公。
“哎呀呀，原來是記己人，西禮西禮，在下三營六組白面葫蘆娃!”
“幸會幸會，在下九營十八組仙子狗尾巴花！”
兩人高高興興地手拉手喝酒去了。
“等等等等，兩位同學請留步，還有事情沒完成呢！”我叫住他倆。
“哦，對了，還要做路徑壓縮。”兩人醒悟。
白面葫蘆娃打電話給他的上級六組長：“組長啊，我查過了，其習偶們的掌門是曹公公。不如偶們一起及接拜在曹公公手下吧，省得級别太低，以後查找掌門麻環。”
“唔，有道理。”
白面葫蘆娃接着打電話給剛才拜訪過的三營長……仙子狗尾巴花也做了同樣的事情。
這樣，查詢中所有涉及到的人物都聚集在曹公公的直接上司下。每次查詢都做了優化處理，是以整個門派樹的層數都會維持在比較低的水準上。路徑壓縮的代碼，看得懂很好，看不懂也沒關系，直接抄上用就行了。總之它所實作的功能就是這麼個意思。
提到并查集就不得不提并查集最經典的例子：食物鍊。
POJ 1182 食物鍊
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182
題目告訴有3種動物，互相吃與被吃，現在告訴你m句話，其中有真有假，叫你判斷假的個數(如果前面沒有與目前話沖突的，即認為其為真話)
這題有幾種做法，我以前的做法是每個集合(或者稱為子樹，說集合的編号相當于子樹的根結點，一個概念)中的元素都各自分為A, B, C三類，在合并時更改根結點的種類，其他點相應更改偏移量。但這種方法公式很難推，特别是偏移量很容易計算錯誤。
下面來介紹一種通用且易于了解的方法：
首先，集合裡的每個點我們都記錄它與它這個集合(或者稱為子樹)的根結點的相對關系relation。0表示它與根結點為同類，1表示它吃根結點，2表示它被根結點吃。
那麼判斷兩個點a, b的關系，我們令p = Find(a), q =Find(b)，即p, q分别為a, b子樹的根結點。
1. 如果p != q，說明a, b暫時沒有關系，那麼關于他們的判斷都是正确的，然後合并這兩個子樹。這裡是關鍵，如何合并兩個子樹使得合并後的新樹能保證正确呢？這裡我們規定隻能p合并到q(剛才說過了，啟發式合并的優化效果并不那麼明顯，如果我們用啟發式合并，就要推出兩個式子，而這個推式子是件比較累的活...是以一般我們都規定一個子樹合到另一個子樹)。那麼合并後，p的relation肯定要改變，那麼改成多少呢？這裡的方法就是找規律，列出部分可能的情況，就差不多能推出式子了。這裡式子為 :tree[p].relation = (tree[b].relation - tree[a].relation + 2 + d) % 3; 這裡的d為判斷語句中a, b的關系。還有個問題，我們是否需要周遊整個a子樹并更新每個結點的狀态呢？答案是不需要的，因為我們可以在Find()函數稍微修改，即結點x繼承它的父親(注意是前父親，因為路徑壓縮後父親就會改變)，即它會繼承到p結點的改變，是以我們不需要每個都周遊過去更新。
2. 如果p = q，說明a, b之前已經有關系了。那麼我們就判斷語句是否是對的，同樣找規律推出式子。即if ((tree[b].relation + d + 2) % 3 != tree[a].relation ), 那麼這句話就是錯誤的。
3. 再對Find()函數進行些修改，即在路徑壓縮前紀錄前父親是誰，然後路徑壓縮後，更新該點的狀态(通過繼承前父親的狀态，這時候前父親的狀态是已經更新的)。
核心的兩個函數為：
int Find(int x)
{
int temp_p;
if (tree[x].parent != x)
{
// 因為路徑壓縮，該結點的與根結點的關系要更新(因為前面合并時可能還沒來得及更新).
temp_p = tree[x].parent;
tree[x].parent = Find(tree[x].parent);
// x與根結點的關系更新(因為根結點變了)，此時的temp_p為它原來子樹的根結點.
tree[x].relation = (tree[x].relation + tree[temp_p].relation) % 3;
}
return tree[x].parent;
}
void Merge(int a, int b,int p, int q, int d)
{
// 公式是找規律推出來的.
tree[p].parent = q; // 這裡的下标相同，都是tree[p].
tree[p].relation = (tree[b].relation - tree[a].relation + 2 + d) % 3;
}
而這種紀錄與根結點關系的方法，适用于幾乎所有的并查集判斷關系(至少我現在沒遇到過不适用的情況…可能是自己做的還太少了…)，是以向大家強烈推薦～～
搞定了食物鍊這題，基本POJ上大部分基礎并查集題目就可以順秒了，這裡僅列個題目編号: POJ1308 1611 1703 1988 2236 2492 2524。
下面來講解幾道稍微提高點的題目:
POJ 1456 Supermarket
http://acm.pku.edu.cn/JudgeOnline/problem?id=1456
這道題貪心的思想很明顯，不過O(n^2)的複雜度明顯不行，我們可以用堆進行優化，這裡講下并查集的優化方法(很巧妙)。我們把連續的被占用的區間看成一個集合(子樹)，它的根結點為這個區間左邊第一個未被占用的區間。
先排序，然後每次判斷Find(b[i])是否大于0，大于0說明左邊還有未被占用的空間，則占用它，然後合并(b[i], Find(b[i])– 1)即可。同樣這裡我們規定隻能左邊的子樹合并到右邊的子樹(想想為什麼～～)。
POJ 1733 Parity game
http://acm.pku.edu.cn/JudgeOnline/problem?id=1733
這題同樣用類似食物鍊的思想。
首先我們先離散化，因為原來的區間太大了(10^9)，我們可以根據問題數目離散成(10^4)。我們要了解，這裡的離散化并不影響最終的結果，因為區間裡1的奇偶個數與區間的大小無關(這句話有點奇怪，可以忽略...)，然後每次輸入a, b，我們把b++，如果他倆在一個集合内，那麼區間[a, b]裡1的個數相當于b.relation ^a.relation，判斷對錯即可。如果不在一個集合内，合并集合(這裡我們規定根結點小的子樹合并根結點大的，是以要根據不同情況推式子)，修改子樹的根結點的狀态，子樹的其他結點狀态通過Find()函數來更新。
hdu 3038 How Many Answers Are Wrong
http://acm.hdu.edu.cn/showproblem.php?pid=3038
上面那題的加強版，不需要離散化，因為區間的和與區間的大小有關(和上面的那句話對比下，同樣可以忽略之…)，做法與上面那題差不多，隻是式子變了，自己推推就搞定了。但這題還有個條件，就是每個點的值在[0, 100]之間，那麼如果a, b不在一個子樹内，我們就合并，但在合并之前還要判斷合并後會不會使得區間的和不合法，如果會說明該合并是非法的，那麼就不合并，同樣認為該句話是錯誤的。
POJ 1417 True Liars(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1417
并查集 + DP(或搜尋)。
題目中告訴兩種人，一種隻說真話，一種隻說假話。然後告訴m條語句，問是否能判斷哪些人是隻說真話的那類人。
其實并查集部分跟食物鍊還是相似，而且種類變少了一種，更容易了。我們可以通過并查集把有關系的一些人合并到一個集合内(具體方法參見食物鍊講解)。
現在的問題轉化為，有n個集合，每個集合都有a, b連個數字，現在要求n個集合中各跳出一個數(a或者b)，使得他們之和等于n1(說真話的人數)。而這個用dp可以很好的解決，用f[i][j]表示到第i個集合和為j個的情況數，我們還用過pre[i][j]記錄目前選的是a還是b，用于後面判斷狀态。方程為f[i][j] = f[i – 1][j – a] + f[i – 1][j – b], j >= a, j>= b。如果最後f[n][n1] == 1說明是唯一的情況，輸出該情況，否則輸出 “no”(多解算no)
注意點 :
1. 這題的m, n1, n2都有可能出現0，可以特殊處理，也可以一起處理。
2. 按上面的dp寫法，f[i][j]可能會很大，因為n可以達到三位數。其實我們關心的隻是f[i][j] 等于0，等于1，大于1三種情況，是以當f[i][j] > 1時，我們都讓它等于2即可。
POJ 2912 Rochambeau(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=2912
Baidu Star 2006 Preliminary的題目，感覺出的很好，在并查集題目中算是較難的了。其實這題跟食物鍊完全一個磨子，同樣三類食物，同樣的互相制約關系。是以食物鍊代碼拿過來改都不需要改。但這題有個judge，他可以出任意手勢。于是我們的做法是，枚舉每個小孩為judge，判斷他為judge時在第幾句話出錯err[i](即到第幾句話能判斷該小孩不是judge)。
1. 如果隻有1個小孩是judge時全部語句都是正确的，說明該小孩是judge，那麼判斷的句子數即為其他小孩的err[i]的最大值。如果
2. 如果每個小孩的都不是judge(即都可以找到出錯的語句)，那麼就是impossible。
3. 多于1個小孩是judge時沒有找到出錯的語句，就是Can not determine。
ZOJ 3261 Connections in Galaxy War http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3563
nuaa 1087 聯通or不連通
http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1087
兩題做法差不多，都是反過來的并查集題目，先對邊集排序，然後把要删去的邊從二分在邊集中标記。然後并查集連接配接沒有标記的邊集，再按查詢反向做就可。第一題合并結點時按照題目要求的優先級合并即可。
這裡介紹的并查集題目，主要都是處理些集合之間的關系(這是并查集的看家本領～～)，至于并查集還有個用處就在求最小生成樹的Kruskal算法中，那個是圖論中求最小生成樹的問題(一般這個難點不在于并查集，它隻是用于求最小生成樹的一種方法)，就不在這裡贅述了～～
分享來自Tina_Z_Y和czyuan 感謝兩個牛人！