學(xué)號(hào)：20011214442

姓名：孫睿

原文鏈接：[](https://blog.csdn.net/liujian20150808/article/details/50848646)

力扣547：朋友圈的[GitHub鏈接](https://github.com/ThreeSR/LeetCode/blob/main/LC547_Social%20Circle.py)

注：本文前面并查集部分是參考鏈接中原文，力扣部分是自己添加。

【嵌牛導(dǎo)讀】本文將介紹并查集算法以及其C語(yǔ)言實(shí)現(xiàn)，最后附上[力扣547：朋友圈](https://leetcode-cn.com/problems/friend-circles/)。

【嵌牛鼻子】算法與數(shù)據(jù)結(jié)構(gòu)

【嵌牛正文】

并查集是我暑假?gòu)母呤帜抢飳W(xué)到的一招，覺(jué)得真是太精妙的設(shè)計(jì)了。以前我無(wú)法解決的一類(lèi)問(wèn)題竟然可以用如此簡(jiǎn)單高效的方法搞定。不分享出來(lái)真是對(duì)不起party了。（party：我靠，關(guān)我嘛事?。课腋愫苁烀?？）

來(lái)看一個(gè)實(shí)例，HDU1232暢通工程

首先在地圖上給你若干個(gè)城鎮(zhèn)，這些城鎮(zhèn)都可以看作點(diǎn)，然后告訴你哪些對(duì)城鎮(zhèn)之間是有道路直接相連的。最后要解決的是整幅圖的連通性問(wèn)題。比如隨意給你兩個(gè)點(diǎn)，讓你判斷它們是否連通，或者問(wèn)你整幅圖一共有幾個(gè)連通分支，也就是被分成了幾個(gè)互相獨(dú)立的塊。像暢通工程這題，問(wèn)還需要修幾條路，實(shí)質(zhì)就是求有幾個(gè)連通分支。如果是1個(gè)連通分支，說(shuō)明整幅圖上的點(diǎn)都連起來(lái)了，不用再修路了；如果是2個(gè)連通分支，則只要再修1條路，從兩個(gè)分支中各選一個(gè)點(diǎn)，把它們連起來(lái)，那么所有的點(diǎn)都是連起來(lái)的了；如果是3個(gè)連通分支，則只要再修兩條路……

以下面這組數(shù)據(jù)輸入數(shù)據(jù)來(lái)說(shuō)明

4 2 1 3 4 3

第一行告訴你，一共有4個(gè)點(diǎn)，2條路。下面兩行告訴你，1、3之間有條路，4、3之間有條路。那么整幅圖就被分成了1-3-4和2兩部分。只要再加一條路，把2和其他任意一個(gè)點(diǎn)連起來(lái)，暢通工程就實(shí)現(xiàn)了，那么這個(gè)這組數(shù)據(jù)的輸出結(jié)果就是1。好了，現(xiàn)在編程實(shí)現(xiàn)這個(gè)功能吧，城鎮(zhèn)有幾百個(gè)，路有不知道多少條，而且可能有回路。 這可如何是好？

我以前也不會(huì)呀，自從用了并查集之后，嗨，效果還真好！我們?nèi)叶加盟?/p>

并查集由一個(gè)整數(shù)型的數(shù)組和兩個(gè)函數(shù)構(gòu)成。數(shù)組pre[]記錄了每個(gè)點(diǎn)的前導(dǎo)點(diǎn)是什么，函數(shù)find是查找，join是合并。

```c

int pre[1000 ];

int find(int x)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //查找根節(jié)點(diǎn)

{

? ? int r=x;

? ? while ( pre[r] != r )? ? ? ? ? ? ? ? ? ? ? ? ? //返回根節(jié)點(diǎn) r

? ? ? ? ? r=pre[r];

? ? int i=x , j ;

? ? while( i != r )? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //路徑壓縮

? ? {

? ? ? ? j = pre[ i ]; // 在改變上級(jí)之前用臨時(shí)變量? j 記錄下他的值

? ? ? ? pre[ i ]= r ; //把上級(jí)改為根節(jié)點(diǎn)

? ? ? ? i=j;

? ? }

? ? return r ;

}

```

```c

void join(int x,int y)? ? ? ? ? ? ? ? ? ? ? ? ? //判斷x y是否連通，

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //如果已經(jīng)連通，就不用管了 如果不連通，就把它們所在的連通分支合并起,

{

? ? int fx=find(x),fy=find(y);

? ? if(fx!=fy)

? ? ? ? pre[fx ]=fy;

}

```

為了解釋并查集的原理，我將舉一個(gè)更有愛(ài)的例子。 話說(shuō)江湖上散落著各式各樣的大俠，有上千個(gè)之多。他們沒(méi)有什么正當(dāng)職業(yè)，整天背著劍在外面走來(lái)走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個(gè)優(yōu)點(diǎn)就是講義氣，絕對(duì)不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，只要是能通過(guò)朋友關(guān)系串聯(lián)起來(lái)的，不管拐了多少個(gè)彎，都認(rèn)為是自己人。這樣一來(lái)，江湖上就形成了一個(gè)一個(gè)的群落，通過(guò)兩兩之間的朋友關(guān)系串聯(lián)起來(lái)。而不在同一個(gè)群落的人，無(wú)論如何都無(wú)法通過(guò)朋友關(guān)系連起來(lái)，于是就可以放心往死了打。但是兩個(gè)原本互不相識(shí)的人，如何判斷是否屬于一個(gè)朋友圈呢？

我們可以在每個(gè)朋友圈內(nèi)推舉出一個(gè)比較有名望的人，作為該圈子的代表人物，這樣，每個(gè)圈子就可以這樣命名“齊達(dá)內(nèi)朋友之隊(duì)”“羅納爾多朋友之隊(duì)”……兩人只要互相對(duì)一下自己的隊(duì)長(zhǎng)是不是同一個(gè)人，就可以確定敵友關(guān)系了。

但是還有問(wèn)題啊，大俠們只知道自己直接的朋友是誰(shuí)，很多人壓根就不認(rèn)識(shí)隊(duì)長(zhǎng)，要判斷自己的隊(duì)長(zhǎng)是誰(shuí)，只能漫無(wú)目的的通過(guò)朋友的朋友關(guān)系問(wèn)下去：“你是不是隊(duì)長(zhǎng)？你是不是隊(duì)長(zhǎng)？”這樣一來(lái)，隊(duì)長(zhǎng)面子上掛不住了，而且效率太低，還有可能陷入無(wú)限循環(huán)中。于是隊(duì)長(zhǎng)下令，重新組隊(duì)。隊(duì)內(nèi)所有人實(shí)行分等級(jí)制度，形成樹(shù)狀結(jié)構(gòu)，我隊(duì)長(zhǎng)就是根節(jié)點(diǎn)，下面分別是二級(jí)隊(duì)員、三級(jí)隊(duì)員。每個(gè)人只要記住自己的上級(jí)是誰(shuí)就行了。遇到判斷敵友的時(shí)候，只要一層層向上問(wèn)，直到最高層，就可以在短時(shí)間內(nèi)確定隊(duì)長(zhǎng)是誰(shuí)了。由于我們關(guān)心的只是兩個(gè)人之間是否連通，至于他們是如何連通的，以及每個(gè)圈子內(nèi)部的結(jié)構(gòu)是怎樣的，甚至隊(duì)長(zhǎng)是誰(shuí)，并不重要。所以我們可以放任隊(duì)長(zhǎng)隨意重新組隊(duì)，只要不搞錯(cuò)敵友關(guān)系就好了。于是，門(mén)派產(chǎn)生了。


下面我們來(lái)看并查集的實(shí)現(xiàn)。 int pre[1000]; 這個(gè)數(shù)組，記錄了每個(gè)大俠的上級(jí)是誰(shuí)。大俠們從1或者0開(kāi)始編號(hào)（依據(jù)題意而定），pre[15]=3就表示15號(hào)大俠的上級(jí)是3號(hào)大俠。如果一個(gè)人的上級(jí)就是他自己，那說(shuō)明他就是掌門(mén)人了，查找到此為止。也有孤家寡人自成一派的，比如歐陽(yáng)鋒，那么他的上級(jí)就是他自己。每個(gè)人都只認(rèn)自己的上級(jí)。比如胡青牛同學(xué)只知道自己的上級(jí)是楊左使。張無(wú)忌是誰(shuí)？不認(rèn)識(shí)！要想知道自己的掌門(mén)是誰(shuí)，只能一級(jí)級(jí)查上去。 find這個(gè)函數(shù)就是找掌門(mén)用的，意義再清楚不過(guò)了（路徑壓縮算法先不論，后面再說(shuō)）。

```c

int find(int x)? ? ? ? ? ? ? ? ? ? //查找我（x）的掌門(mén)

{

? ? int r=x;? ? ? ? ? ? ? ? ? ? ? //委托 r 去找掌門(mén)

? ? while (pre[r ]!=r)? ? ? ? ? //如果r的上級(jí)不是r自己（也就是說(shuō)找到的大俠他不是掌門(mén) = =）

? ? r=pre[r ] ;? ? ? ? ? ? ? ? // r 就接著找他的上級(jí)，直到找到掌門(mén)為止。

? ? return? r ;? ? ? ? ? ? ? ? //掌門(mén)駕到~~~

}

```

再來(lái)看看join函數(shù)，就是在兩個(gè)點(diǎn)之間連一條線，這樣一來(lái)，原先它們所在的兩個(gè)板塊的所有點(diǎn)就都可以互通了。這在圖上很好辦，畫(huà)條線就行了。但我們現(xiàn)在是用并查集來(lái)描述武林中的狀況的，一共只有一個(gè)pre[]數(shù)組，該如何實(shí)現(xiàn)呢？ 還是舉江湖的例子，假設(shè)現(xiàn)在武林中的形勢(shì)如圖所示。虛竹小和尚與周芷若MM是我非常喜歡的兩個(gè)人物，他們的終極boss分別是玄慈方丈和滅絕師太，那明顯就是兩個(gè)陣營(yíng)了。我不希望他們互相打架，就對(duì)他倆說(shuō)：“你們兩位拉拉勾，做好朋友吧?！彼麄兛丛谖业拿孀由?，同意了。這一同意可非同小可，整個(gè)少林和峨眉派的人就不能打架了。這么重大的變化，可如何實(shí)現(xiàn)呀，要改動(dòng)多少地方？其實(shí)非常簡(jiǎn)單，我對(duì)玄慈方丈說(shuō)：“大師，麻煩你把你的上級(jí)改為滅絕師太吧。這樣一來(lái)，兩派原先的所有人員的終極boss都是師太，那還打個(gè)球??！反正我們關(guān)心的只是連通性，門(mén)派內(nèi)部的結(jié)構(gòu)不要緊的。”玄慈一聽(tīng)肯定火大了：“我靠，憑什么是我變成她手下呀，怎么不反過(guò)來(lái)？我抗議！”抗議無(wú)效，上天安排的，最大。反正誰(shuí)加入誰(shuí)效果是一樣的，我就隨手指定了一個(gè)。這段函數(shù)的意思很明白了吧？

```c

void join(int x,int y)? ? ? ? ? //我想讓虛竹和周芷若做朋友

{

? ? int fx=find(x),fy=find(y);? ? ? ? //虛竹的老大是玄慈，芷若MM的老大是滅絕

? ? if(fx!=fy)? ? ? ? ? ? ? ? ? ? ? ? //玄慈和滅絕顯然不是同一個(gè)人

? ? pre[fx ]=fy;? ? ? ? ? ? ? ? ? ? ? //方丈只好委委屈屈地當(dāng)了師太的手下啦

}

```

再來(lái)看看路徑壓縮算法。建立門(mén)派的過(guò)程是用join函數(shù)兩個(gè)人兩個(gè)人地連接起來(lái)的，誰(shuí)當(dāng)誰(shuí)的手下完全隨機(jī)。最后的樹(shù)狀結(jié)構(gòu)會(huì)變成什么胎唇樣，我也完全無(wú)法預(yù)計(jì)，一字長(zhǎng)蛇陣也有可能。這樣查找的效率就會(huì)比較低下。最理想的情況就是所有人的直接上級(jí)都是掌門(mén)，一共就兩級(jí)結(jié)構(gòu)，只要找一次就找到掌門(mén)了。哪怕不能完全做到，也最好盡量接近。這樣就產(chǎn)生了路徑壓縮算法。 設(shè)想這樣一個(gè)場(chǎng)景：兩個(gè)互不相識(shí)的大俠碰面了，想知道能不能揍。 于是趕緊打電話問(wèn)自己的上級(jí)：“你是不是掌門(mén)？” 上級(jí)說(shuō)：“我不是呀，我的上級(jí)是誰(shuí)誰(shuí)誰(shuí)，你問(wèn)問(wèn)他看看。” 一路問(wèn)下去，原來(lái)兩人的最終boss都是東廠曹公公。 “哎呀呀，原來(lái)是記己人，西禮西禮，在下三營(yíng)六組白面葫蘆娃!” “幸會(huì)幸會(huì)，在下九營(yíng)十八組仙子狗尾巴花！” 兩人高高興興地手拉手喝酒去了。 “等等等等，兩位同學(xué)請(qǐng)留步，還有事情沒(méi)完成呢！”我叫住他倆。 “哦，對(duì)了，還要做路徑壓縮?！眱扇诵盐?。 白面葫蘆娃打電話給他的上級(jí)六組長(zhǎng)：“組長(zhǎng)啊，我查過(guò)了，其習(xí)偶們的掌門(mén)是曹公公。不如偶們一起及接拜在曹公公手下吧，省得級(jí)別太低，以后查找掌門(mén)麻環(huán)?！?“唔，有道理?！?白面葫蘆娃接著打電話給剛才拜訪過(guò)的三營(yíng)長(zhǎng)……仙子狗尾巴花也做了同樣的事情。 這樣，查詢中所有涉及到的人物都聚集在曹公公的直接領(lǐng)導(dǎo)下。每次查詢都做了優(yōu)化處理，所以整個(gè)門(mén)派樹(shù)的層數(shù)都會(huì)維持在比較低的水平上。路徑壓縮的代碼，看得懂很好，看不懂也沒(méi)關(guān)系，直接抄上用就行了?？傊鶎?shí)現(xiàn)的功能就是這么個(gè)意思。


學(xué)習(xí)以上并查集知識(shí)之后，可以把它應(yīng)用于力扣547中：

題目概述：

班上有?N?名學(xué)生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B?的朋友，B 是 C?的朋友，那么我們可以認(rèn)為 A 也是 C?的朋友。所謂的朋友圈，是指所有朋友的集合。

給定一個(gè)?N * N?的矩陣?M，表示班級(jí)中學(xué)生之間的朋友關(guān)系。如果M[i][j] = 1，表示已知第 i 個(gè)和 j 個(gè)學(xué)生互為朋友關(guān)系，否則為不知道。你必須輸出所有學(xué)生中的已知的朋友圈總數(shù)。

```

輸入：

[[1,1,0],

[1,1,0],

[0,0,1]]

輸出：2

解釋：已知學(xué)生 0 和學(xué)生 1 互為朋友，他們?cè)谝粋€(gè)朋友圈。

第2個(gè)學(xué)生自己在一個(gè)朋友圈。所以返回 2 。

```

```

輸入：

[[1,1,0],

[1,1,1],

[0,1,1]]

輸出：1

解釋：已知學(xué)生 0 和學(xué)生 1 互為朋友，學(xué)生 1 和學(xué)生 2 互為朋友，所以學(xué)生 0 和學(xué)生 2 也是朋友，所以他們?nèi)齻€(gè)在一個(gè)朋友圈，返回 1 。

```

Solution:

```python

# -*- coding: utf-8 -*-

"""

Created on Wed Sep 23 11:15:09 2020

@author: Three

"""

importnumpyasnp

deffind(a):

iffather[a]!=a:

father[a]=find(father[a])

returnfather[a]

defunion(a,b):

father[find(a)]=find(b)

returnNone

M=np.array([[1,1,0],[1,1,1],[0,0,1]])

father=[iforiinrange(len(M))]

forainrange(len(M)):

forbinrange(a):

ifM[a][b]:

union(a,b)

foriinrange(len(M)):

find(i)

print(len(set(father)))

```