各位看官老爺好，今天咱們來聊一聊一種我很喜歡的資料結構：並查集。初步計劃會分4期講一講，今天是開篇第一期。

至於為什麼選擇並查集作為資料結構系列的開篇之作，其實我也說不出個理由。只是覺得這種資料結構比較常用，也比較精巧，尤其是它還比較容易說清楚，所以很想先和大家分享一下。

好了，廢話不多說，我們從一個簡單的需求場景開始。

假設我們現在面臨的是這樣的一個場景：一共有N個元素，這N個元素被劃分為了若干個集合，即每個元素屬於且僅屬於一個集合當中。例如，假設一共有5個元素，那麼一種可能的劃分是元素1和元素2屬於同一個集合，元素3和元素4屬於同一個集合，最後元素5自己單獨屬於一個集合。用數學一點的符號表示的話就是

。

好，假設N個元素和集合的劃分都已經確定了。現在我們面臨這樣的一個需求：我們隨時需要查詢兩個元素是否屬於同一個集合。比如說如果我們查詢元素1和元素2是否屬於同一個集合，那麼結果是真的；如果我們查詢元素1和元素3是否屬於同一集合，那麼結果是假的，以此類推。對於任意一對給定的元素，我們希望能夠儘可能高效的獲知它們是否屬於同一個集合。

那麼我們應當如何解決這個問題呢？應該不難想到如下的思路：我們給劃分當中的每一個集合編個號，比如說上邊例子裡

是1號集合，

是2號集合，

是3號集合。然後，我們可以用一個長度為N的陣列做一個表，記錄一下每個元素所屬的集合的編號，示意圖如下：

這樣，每次我們希望查詢兩個元素是否屬於同一個集合的時候，只需要去比對兩個元素對應的集合編號是否相同。如果相同，那麼兩個元素屬於同一個集合，否則不屬於同一個集合。

OK，目前我們的需求就已經得到滿足了。這裡，還可以對整個方法做一個小的調整。集合的編號實際上起到的作用是給集合提供一個唯一的標識，這樣一來所有元素都可以以這個標識來標記自己所屬的集合。如果想起到一樣的作用，其實並不一定需要透過編號來實現。一種變通的方法是直接從集合中選出一個代表元素，來作為該集合的標識。比如，對於集合

，我們可以選元素2作為它的代表元素，以2作為這個集合的標識。對於這個集合裡的所有元素，我們知道它們都是和元素2處於同一個集合的，因此他們兩兩之間也都是屬於同一個集合的。舉個形象點的例子，作為集合標識的2可以被看做是整個集合裡所有元素的“帶頭大哥”，其它元素都是“小弟”。小弟想表明自己屬於哪個山頭的時候，只需要報自己的大哥的名字就行了。擁有同一個大哥的小弟自然都是屬於同一個山頭的。對於大哥來說，它的大哥就是他自己。

集合代表的選擇可以遵循任意標準，隨機選擇也可以，只需要保證一個集合裡只有一個代表元素就行了。還用上邊的例子，假設三個集合選出來的代表分別是2、3、5，那麼之前儲存集合編號的表就變成了：

同樣可以透過這個表來快速獲知兩個元素是否屬於同一個集合。

OK，到這裡，上邊的問題需求已經明確的被解決了。在有上述這個表的前提下，查詢兩個元素是否屬於同一集合的時間開銷是O（1）的，事實上就是隻需要兩次查表和一次比較就可以搞定了。那麼下面，我們把問題變的複雜一點：假設在查詢的過程當中，可能出現集合合併的情況，即兩個小集合合併成為一個大集合，那麼我們應當如何做來保持查詢的正確性呢？

我們來舉一個例子：假設我們一開始先基於上邊講的劃分查詢元素1和元素5是否屬於同一集合，那麼由查表可知答案為假。然後，

和

發生了合併，變成了一個更大的集合

，然後我們再查詢元素1和元素5是否屬於同一集合，此時答案變為真。那麼，我們應當如何捕捉到集合的變化情況，從而能夠保證輸出最新的正確結果呢？

我們沿著之前的思路，看看能否做一些修改以適應新的需求。之前，我們用集合代表來表示元素屬於哪一個集合。我們把這個方法類比為拉山頭，用帶頭大哥來表示山頭。那麼，在這個類比裡，集合合併就對應了山頭火併（誤），兩個小山頭合併成了一個大山頭。正所謂一山不容二虎，一個山頭是不能有兩個帶頭大哥的，於是原來的兩個大哥一定只能剩下一個作為新的大哥。戰敗的一方原來擁有的小弟現在就都被戰勝的一方吞掉了。於是這些小弟只能紛紛倒戈，認一個新的大哥以宣示自己的勢力所屬。

從上邊這個例子裡，多少應該可以看出一些端倪了。還是回到集合，集合合併之後，我們可以從原有的兩個集合的兩個代表元素中選出一個，作為新的大集合的代表元素。新集合中的所有元素都以這個新的代表元素作為標識就可以了。我們再舉一個直觀點的例子：假設兩個集合分別有4個和6個元素，合併之後以4個元素的集合的代表作為新的代表。那麼對於另外6個元素，把它們的代表元素都修改為新的代表就可以了。

怎麼從兩個代表裡挑選新的代表呢？從正確性的角度來看，仍然是隨機挑選即可，只要保證新的集合裡只有一個唯一的代表就行了。不過，相信看官老爺們在這個地方可以看出點問題。還是舉上邊的例子，如果我們選4個元素的代表作為新代表，那麼需要修改6個元素的代表；如果選6個元素的代表作為新代表，那麼只需要修改4個元素的代表。從時間開銷的角度看，自然應該選擇6個元素的代表（也就是小弟比較多的大哥）作為新的代表，這樣可以減少修改代表的操作次數。

我們用一個示意圖來展現合併的過程。假設我們合併的是

和

，兩個集合原本的代表元素是2和3，新的代表元素是2，那麼這個過程為：

其中每個元素都指向自己的代表元素，代表元素本身自然就指向它自己。合併前，1和2指向2、3和4指向3。合併後，1、2、3、4都指向2了。

方法到這裡就完成了，我們來分析一下這個過程的開銷有多大。如上所言，合併兩個集合的開銷主要取決於修改代表的次數，而修改代表的次數其實就等於兩個集合裡比較小的那一個集合的元素個數。從規模上看，這個複雜度最好是O（1）的（當某一個集合只有1個元素時），最壞是O（N）的（當兩個集合元素數相等時）。平均下來也是O（N）的。對於查詢來說，開銷不變，仍然是O（1）的，兩次查詢+一次比較就行了。

上邊這個方法的正確性想必已經無需多言了。但是在時間開銷上，能否進行最佳化呢？透過上邊的討論，我們知道查詢的複雜度沒有變化，開銷主要花費在了合併集合上。在合併集合時，需要修改一個集合中的所有元素的代表元素，這是時間開銷的來源。這個開銷有沒有可能最佳化呢？

我們還是從山頭火併這個場景入手。現在山頭A和山頭B火併了，大哥A和大哥B爭奪新大哥之位，大哥A最終勝出，併發生了如下對話：

大哥A：我贏了，我是新的大哥。讓你和你的小弟都來改認我做大哥。

大哥B：我有好多好多的小弟，一個個通知他們改認大哥太麻煩了。不如這樣吧，就我自己改認你做大哥，而我的小弟們還是認我做大哥不變。以後有人問他們的大哥是誰的時候，他們會說是我，但是我會緊跟著告訴提問的人我的大哥是你，這樣他不就知道實際上你才是他們真正的大哥了嗎？

大哥A：我看行。

小劇場結束，不知道各位看官老爺看出意思了沒。在這個故事裡，人員已經出現了

層級化

的結構，也就是一個樹狀結構。雖然代表一個山頭的大哥仍然只能有唯一的一個，但是中間可以有中間層級的小頭目。這樣一來，不需要每個人都去和唯一的大哥掛鉤，而是可以只和一箇中間頭目掛鉤，只要透過它最後能追溯到唯一的大哥就可以了。對應到集合問題，每個元素不必一定記錄自己所處的集合的唯一代表，而是可以只記錄一個“上級元素”，透過這個上級元素再向上逐層尋找，直到找到最頂級的元素，也就是集合的代表元素。如何判斷向上的查詢已經到頂了呢？很簡單，如果一個元素的上級就是它自己，說明它沒有上級了，它自己就是頂了。

仍然以上邊提到的例子來看，合併過程變為：

可以看到，合併後，只修改了3指向的元素。4仍然指向3而不是2。查詢4的頂級元素時，會先查到4的直接上級3，然後再查到3的直接上級2。2的上級就是它自己，所以它就是頂級元素了。

這樣做的好處非常明顯：集合合併的時候，只需要把一個原有的代表元素的上級指定為另一個原有的代表元素就行了。這樣集合合併的開銷變成了1。但是副作用也隨之而來：查詢的開銷變大了。在沒有層次化結構的時候，查詢一個元素的代表元素只需要一次查詢。但是有了層次化結構之後，查詢的複雜度取決於元素所處的層次深度，越深則複雜度越大。在極端情況下，整個層次結構會退化為一條鏈（即1的上級是2，2的上級是3……構成一條鏈），此時查詢的複雜度就退化到O（N）了——相當於查詢和合並的複雜度對調了，實際上沒有產生任何最佳化。

難不成我們白忙活了？不急，在兩種方案之間，我們是可以找到一個更優的平衡點的。

從前邊的分析可以看出來，採用層次化結構的目標是為了減少合併的開銷，卻增加了查詢的開銷。當一個元素在樹狀結構中處於比較深的位置時，查詢它的頂級代表的開銷就會比較大。但是好在，這個查詢開銷我們只需要花費一次！

比如說，假設在一個樹結構中，有這麼一條鏈：1->2->3->4，其中a->b表示b是a的上級。如果我們要查詢1的頂級代表是誰，那麼透過3次查詢，可以知道答案是4。那麼，下次如果我們需要再次查詢1的頂級代表，還需要再經過一次這個過程麼？顯然是不需要的。層級關係的存在可以被看做是為了減少合併開銷的緩兵之計，是手段而不是目的。我們關心的僅僅是1的頂級代表是4，而需要經過怎樣的路徑找到4不是我們需要知道的，這反而是負擔。因此，如果透過一次查詢，我們已經知道了1的頂級代表是4，那麼我們可以把這個結果記錄下來，下次如果再有查詢直接使用即可，不需要再次重走一遍查詢了。

如何記錄這個資訊呢？再用另外一個表來記錄嘛？不需要！我們可以直接把1的上級代表變成4即可。這樣一來，再次查詢1的頂級代表時，可以直接查詢到4，查詢就結束了。中間過程全部略去，一步到位得到答案。

另外，還可以發現，在第一次查詢1的頂級代表時，在層層追溯的過程中，我們實際上也知道了2和3的頂級代表都是4。那麼，我們可以同時把2和3的上級代表也變為4。示意圖如下：

因此，以後無論是再查詢1、2、3中任何一個的頂級代表，都只需要一次查詢即可。這樣的操作過後，原來的一條長的查詢路徑被轉換成了一個扁平的結構，因此這個過程稱之為

路徑壓縮

。

講到這裡，並查集的思路其實已經全部介紹完了。

所以，並查集這個名字終於要出場了。

並查集是一種資料結構，用於處理對N個元素的集合劃分和判斷是否屬於同集合的問題。顧名思義，它支援兩種操作：並和查。查就是查詢兩個元素是否屬於同一個集合。並就是合併兩個小集合成為一個大集合。具體在實踐中，並也是透過指定兩個元素、合併這兩個元素所屬的集合來實現的。

並查集內部用一個上邊介紹的層次結構來表示。對於每一個元素，只需要記錄它的上級代表元素的編號，因此用一個長度為N的陣列即可實現。查操作和並操作的具體過程是這樣的：

查：透過逐級向上追溯的方法，找到兩個元素各自的頂級代表，然後判斷頂級代表是否相同從而判斷兩個元素是否屬於同一個集合。在查詢後進行路徑壓縮，從而將下次查詢的複雜度變成1。

並：對於給定的兩個元素，先找到他們各自的頂級代表，然後把代表1的上級元素設為代表2即可。可以看到，並其實也依賴於查。在查結束後，同樣也進行路徑壓縮。

並查集就是這樣的一個數據結構，想必到這裡它的場景和基本思路已經比較明確了。但是並查集究竟如何透過程式碼實現？並查集真的能夠達到更好的複雜度嘛？並查集究竟能夠解決哪些真實的問題呢？請各位看官老爺靜候下回分解~~~

多謝各位！