刷题笔记26——图论二分图判定
世界上的事情,最忌讳的就是个十全十美,你看那天上的月亮,一旦圆满了,马上就要亏厌;树上的果子,一旦熟透了,马上就要坠落。凡事总要稍留欠缺,才能持恒。 ——莫言
-
visited数组是在如果有环的情况下，防止在图中一直绕圈设置的，类似于剪枝操作，走过了就没必要再走一遍
-
path是在探索过程中，记录此次的遍历路径，从而判断是否有环的
-
如果是判断的话，visited是无法判断的，path是可以判断的
-
二分图的题背会板子即可
785. 判断二分图:如果没访问就染色，访问过就判断染色是否匹配
class Solution {boolean[] visited;int[] color;boolean isB = true;public boolean isBipartite(int[][] graph) {int sz = graph.length;color = new int[sz];visited =new boolean[sz];for(int i=0;i<sz;i++){traverse(graph,i,1);}return isB;}void traverse(int[][] graph, int n, int col){if(visited[n]) return;visited[n] = true;color[n] = col;for(int node:graph[n]){if(visited[node]){if(color[node]!=(1-col)){isB = false;}}else{traverse(graph,node,1-col);}}}
}
886. 可能的二分法:有边的话就需要将两个节点分开，用二分图的思路
class Solution {// 遍历构图二分图boolean[] visited;int[] color;boolean isBi = true;public boolean possibleBipartition(int n, int[][] dislikes) {// 构造的是无向图visited = new boolean[n];color = new int[n];List<Integer>[] graph = generateGraph(n,dislikes);for(int i=0;i<n;i++){traverse(graph,i,1);}return isBi;}void traverse(List<Integer>[] graph,int n,int number){if(visited[n]) return;visited[n] = true;color[n] = number;for(int node:graph[n]){if(visited[node]){if(color[node]!=1-number){isBi = false;}}else{traverse(graph,node,1-number);}}}List<Integer>[] generateGraph(int n, int[][] dislikes){List<Integer>[] graph = new LinkedList[n];for(int i=0;i<n;i++){graph[i] = new LinkedList();}for(int i=0;i<dislikes.length;i++){graph[dislikes[i][0]-1].add(dislikes[i][1]-1);graph[dislikes[i][1]-1].add(dislikes[i][0]-1);}return graph;}
}