# 0547. 朋友圈 ## 題目地址（547. 朋友圈） <https://leetcode-cn.com/problems/friend-circles/> ## 題目描述 ``` <pre class="calibre18">``` 班上有 N 名學生。其中有些人是朋友，有些則不是。他們的友誼具有是傳遞性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我們可以認為 A 也是 C 的朋友。所謂的朋友圈，是指所有朋友的集合。 給定一個 N \* N 的矩陣 M，表示班級中學生之間的朋友關系。如果 M[i][j] = 1，表示已知第 i 個和 j 個學生互為朋友關系，否則為不知道。你必須輸出所有學生中的已知的朋友圈總數。 示例 1: 輸入: [[1,1,0], [1,1,0], [0,0,1]] 輸出: 2 說明：已知學生 0 和學生 1 互為朋友，他們在一個朋友圈。 第 2 個學生自己在一個朋友圈。所以返回 2。 示例 2: 輸入: [[1,1,0], [1,1,1], [0,1,1]] 輸出: 1 說明：已知學生 0 和學生 1 互為朋友，學生 1 和學生 2 互為朋友，所以學生 0 和學生 2 也是朋友，所以他們三個在一個朋友圈，返回 1。 注意： N 在[1,200]的范圍內。 對于所有學生，有 M[i][i] = 1。 如果有 M[i][j] = 1，則有 M[j][i] = 1。 ``` ``` ## 前置知識 - 并查集 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 并查集有一個功能是可以輕松計算出連通分量，然而本題的朋友圈的個數，本質上就是連通分量的個數，因此用并查集可以完美解決。 為了簡單更加清晰，我將并查集模板代碼單盡量獨拿出來。 ## 代碼 `find`, `union`, `connected` 都是典型的模板方法。 懂的同學可能也發現了，我沒有做路徑壓縮，這直接導致 find union connected 的時間復雜度最差的情況退化到 O(N)O(N)O(N)。 當然優化也不難，我們只需要給每一個頂層元素設置一個 size 用來表示連通分量的大小，這樣 union 的時候我們將小的拼接到大的上即可。 另外 find 的時候我們甚至可以路徑壓縮，將樹高限定到常數，這樣時間復雜度可以降低到 O(1)O(1)O(1)。 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">UF</span>:</span> parent = {} cnt = <span class="hljs-params">0</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, M)</span>:</span> n = len(M) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): self.parent[i] = i self.cnt += <span class="hljs-params">1</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">find</span><span class="hljs-params">(self, x)</span>:</span> <span class="hljs-keyword">while</span> x != self.parent[x]: x = self.parent[x] <span class="hljs-keyword">return</span> x <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">union</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">if</span> self.connected(p, q): <span class="hljs-keyword">return</span> self.parent[self.find(p)] = self.find(q) self.cnt -= <span class="hljs-params">1</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">connected</span><span class="hljs-params">(self, p, q)</span>:</span> <span class="hljs-keyword">return</span> self.find(p) == self.find(q) <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findCircleNum</span><span class="hljs-params">(self, M: List[List[int]])</span> -> int:</span> n = len(M) uf = UF(M) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i): <span class="hljs-keyword">if</span> M[i][j] == <span class="hljs-params">1</span>: uf.union(i, j) <span class="hljs-keyword">return</span> uf.cnt ``` ``` **復雜度分析** - 時間復雜度：平均 O(logN)O(logN)O(logN)，最壞的情況是 O(N)O(N)O(N) - 空間復雜度：我們使用了 parent， 因此空間復雜度為 O(N)O(N)O(N) ## 相關專題 - [并查集專題](https://github.com/azl397985856/leetcode/blob/master/thinkings/union-find.md) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 36K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。