<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之旅 廣告
                # 0785. 判斷二分圖 ## 題目地址(785. 判斷二分圖) <https://leetcode-cn.com/problems/is-graph-bipartite/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個無向圖 graph,當這個圖為二分圖時返回 true。 如果我們能將一個圖的節點集合分割成兩個獨立的子集 A 和 B,并使圖中的每一條邊的兩個節點一個來自 A 集合,一個來自 B 集合,我們就將這個圖稱為二分圖。 graph 將會以鄰接表方式給出,graph[i]表示圖中與節點 i 相連的所有節點。每個節點都是一個在 0 到 graph.length-1 之間的整數。這圖中沒有自環和平行邊: graph[i] 中不存在 i,并且 graph[i]中沒有重復的值。 示例 1: 輸入: [[1,3], [0,2], [1,3], [0,2]] 輸出: true 解釋: 無向圖如下: 0----1 | | | | 3----2 我們可以將節點分成兩組: {0, 2} 和 {1, 3}。 示例 2: 輸入: [[1,2,3], [0,2], [0,1,3], [0,2]] 輸出: false 解釋: 無向圖如下: 0----1 | \ | | \ | 3----2 我們不能將節點分割成兩個獨立的子集。 注意: graph 的長度范圍為 [1, 100]。 graph[i] 中的元素的范圍為 [0, graph.length - 1]。 graph[i] 不會包含 i 或者有重復的值。 圖是無向的: 如果 j 在 graph[i]里邊, 那么 i 也會在 graph[j]里邊。 ``` ``` ## 前置知識 - 圖的遍歷 - DFS ## 公司 - 暫無 ## 思路 和 886 思路一樣。 我甚至**直接拿過來 dfs 函數一行代碼沒改就 AC 了**。 唯一需要調整的地方是 graph 。 我將其轉換了一下,具體可以看代碼,非常簡單易懂。 具體算法: - 設置一個長度為 N 的數組 colors,colors\[i\] 表示 節點 i 的顏色,0 表示無顏色, 1 表示一種顏色, - 1 表示另一種顏色。 - 初始化 colors 全部為 0 - 構圖(這里有鄰接矩陣) 使得 grid\[i\]\[j\] 表示 i 和 j 是否有連接(這里用 0 表示無, 1 表示有) - 遍歷圖。 - 如果當前節點未染色,則染色,不妨染為顏色 1 - 遞歸遍歷其鄰居 - 如果鄰居沒有染色, 則染為另一種顏色。即 color \* - 1,其中 color 為當前節點的顏色 - 否則,判斷當前節點和鄰居的顏色是否一致,不一致則返回 False,否則返回 True 強烈建議兩道題一起練習一下。 ## 關鍵點 - 圖的建立和遍歷 - 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, grid, 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-keyword">if</span> grid[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(grid, 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">isBipartite</span><span class="hljs-params">(self, graph: List[List[int]])</span> -> bool:</span> N = len(graph) grid = [[<span class="hljs-params">0</span>] * N <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(N)] colors = [<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> j <span class="hljs-keyword">in</span> graph[i]: grid[i][j] = <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(grid, 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) ## 相關問題 - [886. 可能的二分法](886.possible-bipartition.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>

                              哎呀哎呀视频在线观看