一、題目大意
存在一個 無向圖 ，圖中有 n 個節點，其中每個節點都有一個介于 0 到 n - 1 之間的唯一編號，給你一個二維陣列 graph ，其中 graph[u] 是一個節點陣列，由節點 u 的鄰接節點組成，形式上，對于 graph[u] 中的每個 v ，都存在一條位于節點 u 和節點 v 之間的無向邊，該無向圖同時具有以下屬性：
- 不存在自環（graph[u] 不包含 u），
- 不存在平行邊（graph[u] 不包含重復值），
- 如果 v 在 graph[u] 內，那么 u 也應該在 graph[v] 內（該圖是無向圖）
- 這個圖可能不是連通圖，也就是說兩個節點 u 和 v 之間可能不存在一條連通彼此的路徑，
二分圖 定義：如果能將一個圖的節點集合分割成兩個獨立的子集 A 和 B ，并使圖中的每一條邊的兩個節點一個來自 A 集合，一個來自 B 集合，就將這個圖稱為 二分圖 ，
如果圖是二分圖，回傳 true ；否則，回傳 false ，
示例 1：
輸入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
輸出：false
解釋：不能將節點分割成兩個獨立的子集，以使每條邊都連通一個子集中的一個節點與另一個子集中的一個節點，
示例 2：
輸入：graph = [[1,3],[0,2],[1,3],[0,2]]
輸出：true
解釋：可以將節點分成兩組: {0, 2} 和 {1, 3} ，
提示：
-
graph.length == n
-
1 <= n <= 100
-
0 <= graph[u].length < n
-
0 <= graph[u][i] <= n - 1
-
graph[u] 不會包含 u
-
graph[u] 的所有值 互不相同
-
如果 graph[u] 包含 v，那么 graph[v] 也會包含 u
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/is-graph-bipartite
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
利用佇列和廣度優先搜索，我們可以對未染色的節點進行染色，并且檢查是否有顏色相同的相鄰節點存在，在代碼中我們用0表示未檢查的節點，用1和2表示兩種不同的顏色
三、解題方法
3.1 Java實作
public class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
if (n == 0) {
return true;
}
int[] color = new int[graph.length];
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
q.push(i);
color[i] = 1;
}
while (!q.isEmpty()) {
int node = q.pop();
for (int j : graph[node]) {
if (color[j] == 0) {
q.push(j);
color[j] = color[node] == 2 ? 1 : 2;
} else if (color[node] == color[j]) {
return false;
}
}
}
}
return true;
}
}
四、總結小記
- 2022/10/11 下面開啟圖的行程；讀到一段話挺有感觸的：站在生命的高度看待生活，站在結局的角度看待開始
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/513679.html
標籤：其他