題目

https://leetcode.com/problems/is-graph-bipartite/

題解

有點(diǎn)像簡化版的地圖著色問題。

每走一步，顏色翻轉(zhuǎn)一下，并且染色。

當(dāng)遇到已經(jīng)染過色的節(jié)點(diǎn)時(shí)，

• 如果顏色正確，則停止此路徑
• 如果顏色錯(cuò)誤，則返回 false

DFS完成之后，返回 true。

另外，由于本題不保證是連通圖，所以對(duì)于非連通圖來說，可以將兩個(gè)連通分量獨(dú)立考察。

詳見草稿：

class Solution {int N;public boolean isBipartite(int[][] graph) {N = graph.length;int[] color = new int[N];for (int i = 0; i < N; i++) { // 不保證是連通圖if (color[i] == 0 && !dfs(graph, color, i, 1)) return false;}return true;}public boolean dfs(int[][] graph, int[] color, int i, int flag) {if (color[i] == 0) { // 未上色color[i] = flag;for (int j : graph[i]) {if (!dfs(graph, color, j, -flag)) return false;}return true;} else { // 已上色return color[i] == flag;}} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 785. Is Graph Bipartite? | 785. 判断二分图（DFS，地图着色）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。