摘要：很顯然，我們可以使用并查集來求解。并查集是用來將一系列的元素分組到不相交的集合中，并支持合并和查詢操作。理論總是過于抽象化，下面我們通過一個例子來說明并查集是如何運作的。采用這個方法，我們就可以寫出最簡單版本的并查集代碼。

朋友圈問題

現在有 105個用戶，編號為 1- 105。已知有 m 對關系，每一對關系給你兩個數 x 和 y ，代表編號為 x 的用戶和編號為 y 的用戶是在一個圈子中，例如： A 和 B 在一個圈子中， B 和 C 在一個圈子中，那么 A , B , C 就在一個圈子中?，F在想知道最多的一個圈子內有多少個用戶。

數據范圍：1<= m <= 2 * 10 6 。

進階：空間復雜度 O（n），時間復雜度 O（nlogn）。

輸入描述:

第一行輸入一個整數T，接下來有T組測試數據。對于每一組測試數據：第一行輸入1個整數n，代表有n對關系。接下來n行，每一行輸入兩個數x和y，代表編號為x和編號為y的用戶在同一個圈子里。

1 ≤ T ≤ 10

1 ≤ n ≤ 2 * 106

1 ≤ x, y ≤ 105

輸出描述:

對于每組數據，輸出一個答案代表一個圈子內的最多人數。

示例：

輸入：

241 23 45 61 641 23 45 67 8

輸出：

42

分析問題

通過分析題目，我們可以知道，這道題是求元素分組的問題，即將所有用戶分配到不相交的圈子中，然后求出所有圈子中人數最多的那個圈子。

很顯然，我們可以使用并查集來求解。

首先，我們來看一下什么是并查集。

并查集是用來將一系列的元素分組到不相交的集合中，并支持合并和查詢操作。

• 合并（Union）：把兩個不相交的集合合并為一個集合。
• 查詢（Find）：查詢兩個元素是否在同一個集合中。

并查集的重要思想在于，用集合中的一個元素代表集合。

理論總是過于抽象化，下面我們通過一個例子來說明并查集是如何運作的。

我們這里把集合比喻成幫派，而集合中的代表就是幫主。

一開始，江湖紛爭四起，所有大俠各自為戰，他們每個人都是自己的幫主（對于只有一個元素的集合，代表元素自然就是唯一的那個元素）。

有一天，江湖人士張三和李四偶遇，都想把對方招募到麾下，于是他們進行了一場比武，結果張三贏了，于是把李四招募到了麾下，那么李四的幫主就變成了張三（合并兩個集合，幫主就是這個集合的代表元素）。

然后，李四又和王五偶遇，兩個人互相不服，于是他們進行了一場比武，結果李四又輸了（李四怎么那么菜呢），此時李四能乖乖認慫，加入王五的幫派嗎？那當然是不可能??！ 此時的李四已經不再是一個人在戰斗，于是他呼叫他的老大張三來，張三聽說小弟被欺負了，那必須收拾他?。∮谑呛屯跷灞仍嚵艘环Y果張三贏了，然后把王五也拉入了麾下（其實李四沒必要和王五比試，因為李四比較慫，直接找大哥來收拾王五即可）。此時王五的幫主也是張三了。

我們假設張三二，李四二也進行了幫派的合并，江湖局勢變成了如下的樣子，形成了兩大幫派。

通過上圖，我們可以知道，每個幫派（一個集合）是一個樹狀的結構。

要想尋找到集合的代表元素（幫主），只需要一層層往上訪問父節點，直達樹的根節點即可。其中根節點的父節點是它自己。

采用這個方法，我們就可以寫出最簡單版本的并查集代碼。

1. 初始化

   我們用數組 fa 來存儲每個元素的父節點（這里每個元素有且只有一個父節點）。一開始，他們各自為戰，我們將它們的父節點設為自己（假設目前有編號為1~n的n個元素）。

    def __init__(self,n):        self.fa=[0]*(n+1)        for i in range(1,n+1):            self.fa[i]=i

2. 查詢

   這里我們使用遞歸的方式查找某個元素的代表元素，即一層一層的訪問父節點，直至根節點（根節點是指其父節點是其本身的節點）。

    def find(self,x):        if self.fa[x]==x:            return x        else:            return self.find(self.fa[x])

3. 合并

   我們先找到兩個元素的根節點，然后將前者的父節點設為后者即可。當然也可以將后者的父節點設為前者，這里暫時不重要。后面會給出一個更合理的比較方法。

       def merge(self,x,y):        x_root=self.find(x)        y_root=self.find(y)        self.fa[x_root]=y_root

整體代碼如下所示。

class Solution(object):    def __init__(self,n):        self.fa=[0]*(n+1)        for i in range(1,n+1):            self.fa[i]=i    def find(self,x):        if self.fa[x]==x:            return x        else:            return self.find(self.fa[x])    def merge(self,x,y):        x_root=self.find(x)        y_root=self.find(y)        self.fa[x_root]=y_root

優化

上述最簡單的并查集代碼的效率比較低。假設目前的集合情況如下所示。

此時要調用merge(2,4)函數，于是從2找到1，然后執行f[1]=4，即此時的集合情況變成如下形式。

然后我們執行merge(2,5)函數，于是從2找到1，然后找到4，最后執行f[4]=5，即此時的集合情況變成如下形式。

一直執行下去，我們就會發現該算法可能會形成一條長長的鏈，隨著鏈越來越長，我們想要從底部找到根節點會變得越來越難。

所以就需要進行優化處理，這里我們可以使用路徑壓縮的方法，即使每個元素到根節點的路徑盡可能的短。
具體來說，我們在查詢的過程中，把沿途的每個節點的父節點都設置為根節點即可。那么下次再查詢時，就可以很簡單的獲取到元素的根節點了。代碼如下所示：

    def find(self,x):        if x==self.fa[x]:            return x        else:            self.fa[x] = self.find(self.fa[x])            return self.fa[x]

經過路徑壓縮后，并查集代碼的時間復雜度已經很低了。

下面我們再來進一步的進行優化處理---按秩合并。

這里我們需要先說明一點，因為路徑壓縮優化只是在查詢時進行的，也只能壓縮一條路徑，因此經過路徑優化后，并查集最終的結構仍然可能是比較復雜的。假設，我們現在有一顆比較復雜的樹和一個元素進行合并操作。

如果此時我們要merge(1，6)，我們應該把6的父節點設為1。因為如果把1的父節點設為6，會使樹的深度加深，這樣就會使樹中的每個元素到根節點的距離都變長了，從而使得之后我們尋找根節點的路徑也就會相應的變長。而如果把6的父節點設為1，就不會出現這個問題。

這就啟發我們應該把簡單的樹往復雜的樹上去合并，因為這樣合并后，到根節點距離變長的節點個數比較少。

具體來說，我們用一個數組rank 來記錄每個根節點對應的樹的深度（如果對應元素不是樹的根節點，其rank值相當于以它作為根節點的子樹的深度）。

初始時，把所有元素的rank設為1。在合并時，比較兩個根節點，把rank較小者往較大者上合并。

下面我們來看一下代碼的實現。

    def merge(self,x,y):        #找個兩個元素對應的根節點        x_root=self.find(x)        y_root=self.find(y)                if self.rank[x_root] <= self.rank[y_root]:            self.fa[x_root]=y_root        else:            self.fa[y_root] = x_root                #如果深度相同且根節點不同，則新的根節點的深度        if self.rank[x_root] == self.rank[y_root] /                and x_root != y_root:           self.rank[y_root]=self.rank[y_root]+1

所以，我們終極版的并查集代碼如下所示。

class Solution(object):    def __init__(self,n):        self.fa=[0]*(n+1)        self.rank=[0]*(n+1)        for i in range(1,n+1):            self.fa[i]=i            self.rank[i]=i    def find(self,x):        if x==self.fa[x]:            return x        else:            self.fa[x] = self.find(self.fa[x])            return self.fa[x]    def merge(self,x,y):        #找個兩個元素對應的根節點        x_root=self.find(x)        y_root=self.find(y)        if self.rank[x_root] <= self.rank[y_root]:            self.fa[x_root]=y_root        else:            self.fa[y_root] = x_root        #如果深度相同且根節點不同，則新的根節點的深度        if self.rank[x_root] == self.rank[y_root] /                and x_root != y_root:           self.rank[y_root]=self.rank[y_root]+1

有了并查集的思想，那我們這道朋友圈的問題就迎刃而解了。下面我們給出可以AC的代碼。

class Solution(object):    def __init__(self,n):        self.fa=[0]*(n+1)        self.rank=[0]*(n+1)        self.node_num=[0]*(n+1)        for i in range(1,n+1):            self.fa[i]=i            self.rank[i]=1            self.node_num[i]=1    def find(self,x):        if x==self.fa[x]:            return x        else:            self.fa[x] = self.find(self.fa[x])            return self.fa[x]    def merge(self,x,y):        #找個兩個元素對應的根節點        x_root=self.find(x)        y_root=self.find(y)        if self.rank[x_root] <= self.rank[y_root]:            #將x_root集合合并到y_root上            self.fa[x_root]=y_root            self.node_num[y_root] = self.node_num[y_root] + self.node_num[x_root]        else:            #將y_root集合合并到x_root上            self.fa[y_root] = x_root            self.node_num[x_root] = self.node_num[x_root] + self.node_num[y_root]        #如果深度相同且根節點不同，則新的根節點的深度        if self.rank[x_root] == self.rank[y_root] /                and x_root != y_root:           self.rank[y_root]=self.rank[y_root]+1if __name__ == __main__:    #最多有N個用戶    N=100000    result=[]    T = int(input("請輸入多少組檢測數據？"))    while T>0:        n = int(input("輸入多少對用戶關系"))        print("輸入{}組用戶關系".format(n))        s1=Solution(N)        for i in range(n):            cur=input()            cur_users=cur.split(" ")            s1.merge(int(cur_users[0]), int(cur_users[1]))        max_people=1        for i in range(len(s1.node_num)):            max_people=max(max_people, s1.node_num[i])        result.append(max_people)        T=T-1    for x in result:        print(x)

到此，我們的并查集就聊完了。

啰嗦一句

現在給出一個思考題，可以把你的思考寫在留言區。

現在給出某個親戚關系圖，判斷任意給出的兩個人是否具有親戚關系。

原創不易！各位小伙伴覺得文章不錯的話，不妨點贊（在看）、留言、轉發三連走起！

你知道的越多，你的思維越開闊。我們下期再見。