甘肃制作网站,视频网站怎么做可以播放电视剧,小程序登录注册,怎么建立一个网站让百度搜到提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣785. 判断二分图二、力扣886. 可能的二分法 前言 给你一幅「图」#xff0c;请你用两种颜色将图中的所有顶点着色#xff0c;且使得任意一条边的两个… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、力扣785. 判断二分图二、力扣886. 可能的二分法 前言 给你一幅「图」请你用两种颜色将图中的所有顶点着色且使得任意一条边的两个端点的颜色都不相同你能做到吗 这就是图的「双色问题」其实这个问题就等同于二分图的判定问题如果你能够成功地将图染色那么这幅图就是一幅二分图反之则不是
一、力扣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];ListInteger[] graph builderGraph(dislikes, n);for(int i 0; i n; i ){if(!visited[i]){BFS(graph, i);}}return ok;}public ListInteger[] builderGraph(int[][] dislikes,int n){ListInteger[] 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(ListInteger[] graph, int v){if(!ok){return;}DequeInteger 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;}}}}}
}
