這道題花了不少時間，一開始沒有找對方法，以為直接周遊就完了。吃了大虧後，查了不少資料才知道要用染色(覆寫）算法來做——（有貪心算法和回溯算法兩種）此處我用的是回溯算法。
class Solution {
private Map<Integer , List<Integer>> graph = new HashMap<>(); // 圖存放的資料結構
private int[] color; // 每個節點的顔色
public boolean possibleBipartition(int N, int[][] dislikes) {
color = new int[N + 1];
Arrays.fill(color , - 1);
for (int i = 1;i <= N;i ++) {
graph.put(i , new ArrayList<>());
}
for (int[] edge : dislikes) { // 将圖存入Map
int from = edge[0] , to = edge[1];
graph.get(from).add(to);
graph.get(to).add(from);
}
for (int i = 1;i <= N;i ++) { // 未判斷的節點進行判斷
if (color[i] < 0) {
color[i] = 0;
if (!dfs(i)) {
return false;
}
}
}
return true;
}
private boolean dfs(int current) {
for (int next : graph.get(current)) {
if (color[next] < 0) {
color[next] = 1 - color[current]; //第一圈為1 第二圈為0 第三圈為1 依次類推(主要是為了判斷相鄰的兩個層會不會染色沖突)
if (!dfs(next)) { // 判斷 下一節點染色是否成功 ，失敗則傳回false
return false;
}
} else if (color[next] == color[current]) {
return false; //發現Vi 與 Vi-1 節點顔色相同
}
}
return true;
}
}
思路：本題類似于經典的染色算法，使用DFS（深度周遊）思路解題（不知的這個的自行百度，類似走迷宮的思想），首先将限制條件轉換為一個圖，将color[] 賦予初始值-1，color的長度為可以使用顔色的數量。
（本做法首先要了解：題目給出的N相當于，給出了N個節點，每個節點一個顔色，是以共有N個節點，N個顔色。我們是在此前提下，判斷 “不允許分組”構成的圖，判斷相鄰的兩個節點是否不同顔色）
DFS思路：
- 染色的過程是第一圈，第二圈，第三圈......以此類推進行染色判定
- 周遊所有節點的過程，對其進行染色标記，第一圈為 0 ，第二圈為 1-0，第三圈為1-（1-0）=0 ， 第四圈為 1-0 其實是相鄰的兩圈進行判斷，若Q1 = Q2 則說明在N個顔色的條件下，無法滿足對限制條件圖進行染色判定。
- 進行深度周遊時，若節點未進行染色判定，進行染色判定，直到到達最後一個節點，沒有下一個節點時傳回true，（途中染色判定失敗直接傳回）。
當所有節點都進行染色判定後，途中沒有失敗時，說明條件可以進行二分算法。