提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
前言
给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？ 这就是图的「双色问题」，其实这个问题就等同于二分图的判定问题，如果你能够成功地将图染色，那么这幅图就是一幅二分图，反之则不是：
一、力扣785. 判断二分图
class Solution {
boolean ok = true;
boolean[] visited;
boolean[] color;
public boolean isBipartite(int[][] graph) {
int n = graph.length;
visited = new boolean[n];
color = new boolean[n];
for(int i = 0; i < n; i ++){
if(!visited[i]){
traverse(graph, i);
}
}
return ok;
}
public void traverse(int[][] graph, int v){
if(!ok){
return;
}
visited[v] = true;
for(int e : graph[v]){
if(!visited[e]){
color[e] = !color[v];
traverse(graph,e);
}else{
if(color[e] == color[v]){
ok = false;
return;
}
}
}
}
}
二、力扣886. 可能的二分法
class Solution {
boolean ok = true;
boolean[] visited;
boolean[] color;
public boolean possibleBipartition(int n, int[][] dislikes) {
visited = new boolean[n];
color = new boolean[n];
List<Integer>[] graph = builderGraph(dislikes, n);
for(int i = 0; i < n; i ++){
if(!visited[i]){
BFS(graph, i);
}
}
return ok;
}
public List<Integer>[] builderGraph(int[][] dislikes,int n){
List<Integer>[] graph = new LinkedList[n];
for(int i = 0; i < n ; i ++){
graph[i] = new LinkedList<>();
}
for(int[] arr : dislikes){
int to = arr[0]-1;
int from = arr[1]-1;
graph[to].add(from);
graph[from].add(to);
}
return graph;
}
public void BFS(List<Integer>[] graph, int v){
if(!ok){
return;
}
Deque<Integer> deq = new LinkedList<>();
deq.offerLast(v);
visited[v] = true;
while(!deq.isEmpty()){
int cur = deq.pollFirst();
for(int e : graph[cur]){
if(!visited[e]){
visited[e] = true;
color[e] = !color[cur];
deq.offerLast(e);
}else{
if(color[e] == color[cur]){
ok = false;
return;
}
}
}
}
}
}
