力扣labuladong——一刷day79

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同，你能做到吗？ 这就是图的「双色问题」，其实这个问题就等同于二分图的判定问题，如果你能够成功地将图染色，那么这幅图就是一幅二分图，反之则不是：

一、力扣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;}}}}}
}