談一談并查集QAQ（上）

最近幾日理了理學過的很多oi知識。。。發現不知不覺就有很多的知識忘記了。。。

在聊聊并查集的時候順便當作鞏固吧。。。。

什么是并查集呢?

( Union Find Set ) 是一種用于處理分離集合的抽象數據結構類型。

具體一點:

　　當我們給出兩個元素的一個無序對（a,b）時，需要快速合并a和b所在的集合，這期間需要反復查找出某元素所在的集合，“并”、“查”和“集”三字由此而來。也就是說，并查集的作用是動態地維護和處理集合元素之間的復雜關系。

　　在并查集中，n個不同的元素被分為若干組，每組是一個集合，這種集合就叫做“分離集合”。并查集支持查找一個元素所屬的集合以及兩個元素各自所屬集合的合并操作。

例如，我們有這樣一個問題：

　　一個城鎮里居住著n個市民，已知一些人互為朋友，而且朋友的朋友也是朋友，也就是說，如果A和B是朋友，C和B是朋友，則A和C也是朋友，請你根據給出的若干組朋友關系，求出最大的一個朋友圈的人數。

　　這就有了并查集的用武之地了，一開始我們把所有人都各自放在一個集合中，然后根據依次給出的朋友關系，查找判斷兩個人是否屬于同一個集合（是否已經是朋友），如果不在同一個集合，則將這兩個集合合并成一個集合（行成一個朋友圈），最后看哪個集合的元素最多并輸出個數即可。

然而并查集有什么主要操作呢？

　　使用并查集首先要記錄一組分離的動態集合S = {S1，S2，···，S_n}，每個集合還要設置一個代表來識別，代表只是要選擇該集合中的某個元素即可，哪一個元素被選作代表是無所謂的，重要的是，如果請求某一動態集合的代表兩次，且在兩次請求間不修改集合，則兩次得到的答案應該是相同的。并查集主要有三種操作：初始化、查找與合并。

　　（1）初始化：make-set(x)

　　建立一個新的集合，其僅有的成員是x（同時就是代表）。由于各集合是分離的，所以要求x在沒有其他集合中出現過。使用并查集前都需要執行一次初始化操作，無論采用何種實現方式，其時間復雜度都是O（n）。

　　（2）查找：find-set(x)

　　查找一個元素所在的集合，本操作返回一個包含x的集合的代表。查找是并查集的核心操作，也是優化并查集效率的重點。

　　（3）合并：merge(x，y)

　　將包含x和y的動態集合（假設為Sx和Sy）合并成一個新的集合S，本操作返回集合Sx∪Sy的代表。一般來說，在不同的實現中通常以Sx或者Sy的代表作為新集合的代表。合并之前一般要先判斷兩個元素是否屬于同一集合，這可以通過查找操作來實現。

終于到了并查集的實現了！！

　　并查集可以采用數組、鏈表和樹三種數據結構來實現，選擇不同的實現方式會給查找操作和合并操作的效率帶來很大的差別。

并查集的數組實現：

　　實現并查集的最簡單的方法就是用數組記錄每個元素所屬集合的編號，A[i] = j 表示元素i屬于第j 類集合，初始化A[i] = i。查找元素所屬的集合時，只需讀出數組中記錄的該元素所屬集合的編號A[i]，時間復雜度為O（1）。合并兩個元素各自所屬集合時，需要將數組中屬于其中一個集合的元素所對應的數組元素值全部更新為另一個集合的編號值，時間復雜度為O（n）。所以用數組實現并查集是最簡單的方法，而且容易理解，實際使用較多。但是，合并操作的代價太高，在最壞的情況下，所有集合合并成一個集合的總代價會達到O（n²）。

并查集的鏈表實現：

　　用鏈表實現并查集也是一種很常見的手段。每個分離集合對應一個鏈表，鏈表有一個表頭，每個元素有一個指針指向表頭，表明了它所屬集合的類別，另設一個指針指向它的下一個元素，同時為了方便實現，再設一個指針last表示鏈表的表尾。

　　因為并查集問題處理的對象往往都是連續的整數，所以一般選擇用靜態數組來模擬鏈表，用下標對應集合的元素。具體數據結構體定義如下qwq：

?

struct node{int head,next,last;
}S[maxn];

　　

　　此時，初始化和查找操作的實現就很簡單了。

?

make-set(x){S[x].head = x;S[x].next = 0;
}
find-set(x){return S[x].head；
}

?

　　對于合并操作，我們先假設merge（x，y）的參數是有序的，是把y所屬的集合合并到x所在的集合。首先執行查找操作，當出現find-set（x）≠ find-set（y）時，直接將y的表頭接到x的表尾，同時將y所在集合的所有元素head值設為find-set（x），x的表尾也設為y的表尾。需要注意的是，last指針只要在表頭結點中記錄即可，因為每一次查找到find-set（x）都可以得到表頭元素，而鏈表中其他元素記錄last值是毫無意義的。

　　考慮到輸入數據的特殊性，根據以上合并方法，我們總是把y接到x后面，如果y所在的集合非常大，每次復制的代價就會非常高，比如輸入數據形如：（2,1），（3,1），（4,1），·····，（n，1），顯然y所在的集合就會越來越龐大，此時時間復雜度就會達到O（n²）。不過，我們可以很快滴想到一個優化方法：不妨比較x和y所在集合的大小，把較短的鏈表接在較長的鏈表尾部，這樣效果是一樣的，但時間效率肯定不比原來差。具體實現時可以在node里多設一個number域，用來記錄此條鏈表中成員的個數。顯然，number記錄在表頭元素中即可。將兩個鏈表合并的時候，只需要將鏈表的number域相加，因此維護起來是非常方便的。這種快速實現的方法稱為“加權啟發式”合并，這里的權就是指number域。假設有n個元素，則可以證明這種方法合并操作的總次數不超過nlog₂n次。

?

merge(x,y){x = find-set(x);y = find-set(y);if(x.number > y.number)merge(x,y);merge(y,x);
}

　　

　　以上是并查集的兩種實現方法qwq。然而最最最重要以及實用的是并查集的樹實現。我會在? 談一談并查集QAQ（下） 中仔細講解qwq。

?

　　

?