# 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 啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。