<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之旅 廣告
                # 0886. 可能的二分法 ## 題目地址(886. 可能的二分法) <https://leetcode-cn.com/problems/is-graph-bipartite/> ## 題目描述 ``` <pre class="calibre18">``` 給定一組 N 人(編號為 1, 2, ..., N), 我們想把每個人分進任意大小的兩組。 每個人都可能不喜歡其他人,那么他們不應該屬于同一組。 形式上,如果 dislikes[i] = [a, b],表示不允許將編號為 a 和 b 的人歸入同一組。 當可以用這種方法將每個人分進兩組時,返回 true;否則返回 false。 示例 1: 輸入:N = 4, dislikes = [[1,2],[1,3],[2,4]] 輸出:true 解釋:group1 [1,4], group2 [2,3] 示例 2: 輸入:N = 3, dislikes = [[1,2],[1,3],[2,3]] 輸出:false 示例 3: 輸入:N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] 輸出:false 提示: 1 <= N <= 2000 0 <= dislikes.length <= 10000 dislikes[i].length == 2 1 <= dislikes[i][j] <= N dislikes[i][0] < dislikes[i][1] 對于dislikes[i] == dislikes[j] 不存在 i != j ``` ``` ## 前置知識 - 圖的遍歷 - DFS ## 公司 - 暫無 ## 思路 這是一個圖的問題。解決這種問題一般是要遍歷圖才行的,這也是圖的套路。 那么遍歷的話,你要有一個合適的數據結構。 比較常見的圖存儲方式是鄰接矩陣和鄰接表。 而我們這里為了操作方便(代碼量),直接使用鄰接矩陣。由于是互相不喜歡,不存在一個喜歡另一個,另一個不喜歡一個的情況,因此這是無向圖。而無向圖鄰接矩陣實際上是會浪費空間,具體看我下方畫的圖。 而題目給我們的二維矩陣并不是現成的鄰接矩陣形式,因此我們需要自己生成。 我們用 1 表示互相不喜歡(dislike each other)。 ``` <pre class="calibre18">``` graph = [[<span class="hljs-params">0</span>] * N <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(N)] <span class="hljs-keyword">for</span> a, b <span class="hljs-keyword">in</span> dislikes: graph[a - <span class="hljs-params">1</span>][b - <span class="hljs-params">1</span>] = <span class="hljs-params">1</span> graph[b - <span class="hljs-params">1</span>][a - <span class="hljs-params">1</span>] = <span class="hljs-params">1</span> ``` ``` ![](https://img.kancloud.cn/e4/de/e4de86de14a80d16572add8a19a09f5f_528x470.jpg) 同時可以用 hashmap 或者數組存儲 N 個人的分組情況, 業界關于這種算法一般叫染色法,因此我們命名為 colors,其實對應的本題叫 groups 更合適。 ![](https://img.kancloud.cn/42/76/42766bfa4c33f66ae0e5abaf5043e98c_316x110.jpg) 我們用: - 0 表示沒有分組 - 1 表示分組 1 - -1 表示分組 2 之所以用 0,1,-1,而不是 0,1,2 是因為我們會在不能分配某一組的時候嘗試分另外一組,這個時候有其中一組轉變為另外一組就可以直接乘以-1,而 0,1,2 這種就稍微麻煩一點而已。 具體算法: - 遍歷每一個人,嘗試給他們進行分組,比如默認分配組 1. ![](https://img.kancloud.cn/6d/57/6d57f8709c279659f35582e7df45f1a7_415x202.jpg) - 然后遍歷這個人討厭的人,嘗試給他們分另外一組,如果不可以分配另外一組,則返回 False 那問題的關鍵在于如何判斷“不可以分配另外一組”呢? ![](https://img.kancloud.cn/9e/7a/9e7a41cd1f78416c18e5bc860c2865c4_1421x733.jpg) 實際上,我們已經用 colors 記錄了分組信息,對于每一個人如果分組確定了,我們就更新 colors,那么對于一個人如果分配了一個組,并且他討厭的人也被分組之后,**分配的組和它只能是一組**,那么“就是不可以分配另外一組”。 代碼表示就是: ``` <pre class="calibre18">``` <span class="hljs-title"># 其中j 表示當前是第幾個人,N表示總人數。 dfs的功能就是根據colors和graph分配組,true表示可以分,false表示不可以,具體代碼見代碼區。</span> <span class="hljs-keyword">if</span> colors[j] == <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> self.dfs(graph, colors, j, <span class="hljs-params">-1</span> * color, N) ``` ``` ## 關鍵點 - 二分圖 - 染色法 - 圖的建立和遍歷 - colors 數組 ## 代碼 ``` <pre class="calibre18">``` <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">dfs</span><span class="hljs-params">(self, graph, colors, i, color, N)</span>:</span> colors[i] = color <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(N): <span class="hljs-title"># dislike eachother</span> <span class="hljs-keyword">if</span> graph[i][j] == <span class="hljs-params">1</span>: <span class="hljs-keyword">if</span> colors[j] == color: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">if</span> colors[j] == <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> self.dfs(graph, colors, j, <span class="hljs-params">-1</span> * color, N): <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">possibleBipartition</span><span class="hljs-params">(self, N: int, dislikes: List[List[int]])</span> -> bool:</span> graph = [[<span class="hljs-params">0</span>] * N <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(N)] colors = [<span class="hljs-params">0</span>] * N <span class="hljs-keyword">for</span> a, b <span class="hljs-keyword">in</span> dislikes: graph[a - <span class="hljs-params">1</span>][b - <span class="hljs-params">1</span>] = <span class="hljs-params">1</span> graph[b - <span class="hljs-params">1</span>][a - <span class="hljs-params">1</span>] = <span class="hljs-params">1</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(N): <span class="hljs-keyword">if</span> colors[i] == <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> <span class="hljs-keyword">not</span> self.dfs(graph, colors, i, <span class="hljs-params">1</span>, N): <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> ``` ``` **復雜度分析** - 時間復雜度:O(N2)O(N^2)O(N2) - 空間復雜度:O(N)O(N)O(N) ## 相關問題 - [785. 判斷二分圖](785.is-graph-bipartite.html) 更多題解可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 關注公眾號力扣加加,努力用清晰直白的語言還原解題思路,并且有大量圖解,手把手教你識別套路,高效刷題。
                  <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>

                              哎呀哎呀视频在线观看