<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看