摘要：很顯然，我們可以使用并查集來(lái)求解。并查集是用來(lái)將一系列的元素分組到不相交的集合中，并支持合并和查詢(xún)操作。理論總是過(guò)于抽象化，下面我們通過(guò)一個(gè)例子來(lái)說(shuō)明并查集是如何運(yùn)作的。采用這個(gè)方法，我們就可以寫(xiě)出最簡(jiǎn)單版本的并查集代碼。

朋友圈問(wèn)題

現(xiàn)在有 105個(gè)用戶(hù)，編號(hào)為 1- 105。已知有 m 對(duì)關(guān)系，每一對(duì)關(guān)系給你兩個(gè)數(shù) x 和 y ，代表編號(hào)為 x 的用戶(hù)和編號(hào)為 y 的用戶(hù)是在一個(gè)圈子中，例如： A 和 B 在一個(gè)圈子中， B 和 C 在一個(gè)圈子中，那么 A , B , C 就在一個(gè)圈子中。現(xiàn)在想知道最多的一個(gè)圈子內(nèi)有多少個(gè)用戶(hù)。

數(shù)據(jù)范圍：1<= m <= 2 * 10 6 。

進(jìn)階：空間復(fù)雜度 O（n），時(shí)間復(fù)雜度 O（nlogn）。

輸入描述:

第一行輸入一個(gè)整數(shù)T，接下來(lái)有T組測(cè)試數(shù)據(jù)。對(duì)于每一組測(cè)試數(shù)據(jù)：第一行輸入1個(gè)整數(shù)n，代表有n對(duì)關(guān)系。接下來(lái)n行，每一行輸入兩個(gè)數(shù)x和y，代表編號(hào)為x和編號(hào)為y的用戶(hù)在同一個(gè)圈子里。

1 ≤ T ≤ 10

1 ≤ n ≤ 2 * 106

1 ≤ x, y ≤ 105

輸出描述:

對(duì)于每組數(shù)據(jù)，輸出一個(gè)答案代表一個(gè)圈子內(nèi)的最多人數(shù)。

示例：

輸入：

241 23 45 61 641 23 45 67 8

輸出：

42

分析問(wèn)題

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

很顯然，我們可以使用并查集來(lái)求解。

首先，我們來(lái)看一下什么是并查集。

并查集是用來(lái)將一系列的元素分組到不相交的集合中，并支持合并和查詢(xún)操作。

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

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

理論總是過(guò)于抽象化，下面我們通過(guò)一個(gè)例子來(lái)說(shuō)明并查集是如何運(yùn)作的。

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

一開(kāi)始，江湖紛爭(zhēng)四起，所有大俠各自為戰(zhàn)，他們每個(gè)人都是自己的幫主（對(duì)于只有一個(gè)元素的集合，代表元素自然就是唯一的那個(gè)元素）。

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

然后，李四又和王五偶遇，兩個(gè)人互相不服，于是他們進(jìn)行了一場(chǎng)比武，結(jié)果李四又輸了（李四怎么那么菜呢），此時(shí)李四能乖乖認(rèn)慫，加入王五的幫派嗎？那當(dāng)然是不可能！！ 此時(shí)的李四已經(jīng)不再是一個(gè)人在戰(zhàn)斗，于是他呼叫他的老大張三來(lái)，張三聽(tīng)說(shuō)小弟被欺負(fù)了，那必須收拾他！！于是和王五比試了一番，結(jié)果張三贏了，然后把王五也拉入了麾下（其實(shí)李四沒(méi)必要和王五比試，因?yàn)槔钏谋容^慫，直接找大哥來(lái)收拾王五即可）。此時(shí)王五的幫主也是張三了。

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

通過(guò)上圖，我們可以知道，每個(gè)幫派（一個(gè)集合）是一個(gè)樹(shù)狀的結(jié)構(gòu)。

要想尋找到集合的代表元素（幫主），只需要一層層往上訪問(wèn)父節(jié)點(diǎn)，直達(dá)樹(shù)的根節(jié)點(diǎn)即可。其中根節(jié)點(diǎn)的父節(jié)點(diǎn)是它自己。

采用這個(gè)方法，我們就可以寫(xiě)出最簡(jiǎn)單版本的并查集代碼。

1. 初始化

   我們用數(shù)組 fa 來(lái)存儲(chǔ)每個(gè)元素的父節(jié)點(diǎn)（這里每個(gè)元素有且只有一個(gè)父節(jié)點(diǎn)）。一開(kāi)始，他們各自為戰(zhàn)，我們將它們的父節(jié)點(diǎn)設(shè)為自己（假設(shè)目前有編號(hào)為1~n的n個(gè)元素）。

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

2. 查詢(xún)

   這里我們使用遞歸的方式查找某個(gè)元素的代表元素，即一層一層的訪問(wèn)父節(jié)點(diǎn)，直至根節(jié)點(diǎn)（根節(jié)點(diǎn)是指其父節(jié)點(diǎn)是其本身的節(jié)點(diǎn)）。

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

3. 合并

   我們先找到兩個(gè)元素的根節(jié)點(diǎn)，然后將前者的父節(jié)點(diǎn)設(shè)為后者即可。當(dāng)然也可以將后者的父節(jié)點(diǎn)設(shè)為前者，這里暫時(shí)不重要。后面會(huì)給出一個(gè)更合理的比較方法。

       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

優(yōu)化

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

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

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

一直執(zhí)行下去，我們就會(huì)發(fā)現(xiàn)該算法可能會(huì)形成一條長(zhǎng)長(zhǎng)的鏈，隨著鏈越來(lái)越長(zhǎng)，我們想要從底部找到根節(jié)點(diǎn)會(huì)變得越來(lái)越難。

所以就需要進(jìn)行優(yōu)化處理，這里我們可以使用路徑壓縮的方法，即使每個(gè)元素到根節(jié)點(diǎn)的路徑盡可能的短。
具體來(lái)說(shuō)，我們?cè)诓樵?xún)的過(guò)程中，把沿途的每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都設(shè)置為根節(jié)點(diǎn)即可。那么下次再查詢(xún)時(shí)，就可以很簡(jiǎn)單的獲取到元素的根節(jié)點(diǎn)了。代碼如下所示：

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

經(jīng)過(guò)路徑壓縮后，并查集代碼的時(shí)間復(fù)雜度已經(jīng)很低了。

下面我們?cè)賮?lái)進(jìn)一步的進(jìn)行優(yōu)化處理---按秩合并。

這里我們需要先說(shuō)明一點(diǎn)，因?yàn)槁窂綁嚎s優(yōu)化只是在查詢(xún)時(shí)進(jìn)行的，也只能壓縮一條路徑，因此經(jīng)過(guò)路徑優(yōu)化后，并查集最終的結(jié)構(gòu)仍然可能是比較復(fù)雜的。假設(shè)，我們現(xiàn)在有一顆比較復(fù)雜的樹(shù)和一個(gè)元素進(jìn)行合并操作。

如果此時(shí)我們要merge(1，6)，我們應(yīng)該把6的父節(jié)點(diǎn)設(shè)為1。因?yàn)槿绻?的父節(jié)點(diǎn)設(shè)為6，會(huì)使樹(shù)的深度加深，這樣就會(huì)使樹(shù)中的每個(gè)元素到根節(jié)點(diǎn)的距離都變長(zhǎng)了，從而使得之后我們尋找根節(jié)點(diǎn)的路徑也就會(huì)相應(yīng)的變長(zhǎng)。而如果把6的父節(jié)點(diǎn)設(shè)為1，就不會(huì)出現(xiàn)這個(gè)問(wèn)題。

這就啟發(fā)我們應(yīng)該把簡(jiǎn)單的樹(shù)往復(fù)雜的樹(shù)上去合并，因?yàn)檫@樣合并后，到根節(jié)點(diǎn)距離變長(zhǎng)的節(jié)點(diǎn)個(gè)數(shù)比較少。

具體來(lái)說(shuō)，我們用一個(gè)數(shù)組rank 來(lái)記錄每個(gè)根節(jié)點(diǎn)對(duì)應(yīng)的樹(shù)的深度（如果對(duì)應(yīng)元素不是樹(shù)的根節(jié)點(diǎn)，其rank值相當(dāng)于以它作為根節(jié)點(diǎn)的子樹(shù)的深度）。

初始時(shí)，把所有元素的rank設(shè)為1。在合并時(shí)，比較兩個(gè)根節(jié)點(diǎn)，把rank較小者往較大者上合并。

下面我們來(lái)看一下代碼的實(shí)現(xiàn)。

    def merge(self,x,y):        #找個(gè)兩個(gè)元素對(duì)應(yīng)的根節(jié)點(diǎn)        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                #如果深度相同且根節(jié)點(diǎn)不同，則新的根節(jié)點(diǎn)的深度        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):        #找個(gè)兩個(gè)元素對(duì)應(yīng)的根節(jié)點(diǎn)        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        #如果深度相同且根節(jié)點(diǎn)不同，則新的根節(jié)點(diǎn)的深度        if self.rank[x_root] == self.rank[y_root] /                and x_root != y_root:           self.rank[y_root]=self.rank[y_root]+1

有了并查集的思想，那我們這道朋友圈的問(wèn)題就迎刃而解了。下面我們給出可以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):        #找個(gè)兩個(gè)元素對(duì)應(yīng)的根節(jié)點(diǎn)        x_root=self.find(x)        y_root=self.find(y)        if self.rank[x_root] <= self.rank[y_root]:            #將x_root集合合并到y(tǒng)_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]        #如果深度相同且根節(jié)點(diǎn)不同，則新的根節(jié)點(diǎn)的深度        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個(gè)用戶(hù)    N=100000    result=[]    T = int(input("請(qǐng)輸入多少組檢測(cè)數(shù)據(jù)？"))    while T>0:        n = int(input("輸入多少對(duì)用戶(hù)關(guān)系"))        print("輸入{}組用戶(hù)關(guān)系".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)

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

啰嗦一句

現(xiàn)在給出一個(gè)思考題，可以把你的思考寫(xiě)在留言區(qū)。

現(xiàn)在給出某個(gè)親戚關(guān)系圖，判斷任意給出的兩個(gè)人是否具有親戚關(guān)系。

原創(chuàng)不易！各位小伙伴覺(jué)得文章不錯(cuò)的話，不妨點(diǎn)贊（在看）、留言、轉(zhuǎn)發(fā)三連走起！

你知道的越多，你的思維越開(kāi)闊。我們下期再見(jiàn)。