0886. 可能的二分法 · ttttt

# 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 = [[0] * N for i in range(N)] for a, b in dislikes: graph[a - 1][b - 1] = 1 graph[b - 1][a - 1] = 1 ``` ``` ![](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">``` # 其中j 表示當前是第幾個人，N表示總人數。 dfs的功能就是根據colors和graph分配組，true表示可以分，false表示不可以，具體代碼見代碼區。 if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, N) ``` ``` ## 關鍵點 - 二分圖 - 染色法 - 圖的建立和遍歷 - colors 數組 ## 代碼 ``` <pre class="calibre18">``` class Solution: def dfs(self, graph, colors, i, color, N): colors[i] = color for j in range(N): # dislike eachother if graph[i][j] == 1: if colors[j] == color: return False if colors[j] == 0 and not self.dfs(graph, colors, j, -1 * color, N): return False return True def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool: graph = [[0] * N for i in range(N)] colors = [0] * N for a, b in dislikes: graph[a - 1][b - 1] = 1 graph[b - 1][a - 1] = 1 for i in range(N): if colors[i] == 0 and not self.dfs(graph, colors, i, 1, N): return False return True ``` ``` **復雜度分析** - 時間復雜度：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 啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。