cnc强力磁盘 东莞网站建设,crm管理系统在线使用,建官网公司地址,网址ip域名解析世界上的事情,最忌讳的就是个十全十美,你看那天上的月亮,一旦圆满了,马上就要亏厌;树上的果子,一旦熟透了,马上就要坠落。凡事总要稍留欠缺,才能持恒。 ——莫言 visited数组是在如果有环的情况下#xff0c;防止在图中一直绕圈设置的#xff0c;类似于剪枝操作#xff0c;走… 世界上的事情,最忌讳的就是个十全十美,你看那天上的月亮,一旦圆满了,马上就要亏厌;树上的果子,一旦熟透了,马上就要坠落。凡事总要稍留欠缺,才能持恒。 ——莫言 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 i0;isz;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];ListInteger[] graph generateGraph(n,dislikes);for(int i0;in;i){traverse(graph,i,1);}return isBi;}void traverse(ListInteger[] 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);}}}ListInteger[] generateGraph(int n, int[][] dislikes){ListInteger[] graph new LinkedList[n];for(int i0;in;i){graph[i] new LinkedList();}for(int i0;idislikes.length;i){graph[dislikes[i][0]-1].add(dislikes[i][1]-1);graph[dislikes[i][1]-1].add(dislikes[i][0]-1);}return graph;}
}
