力扣labuladong一刷day45天二分图判定
2023-12-23 17:52:32
力扣labuladong一刷day45天二分图判定
一、785. 判断二分图
题目链接:https://leetcode.cn/problems/is-graph-bipartite/
思路:二分图指的是每一个节点与它相邻的节点归属不同类别,一共就两种类别。关系就如同一篇文章引用很多题目,一个题目被很多文章引用。解本题只需要遍历,然后在遍历的过程中判断,关键点在于节点间如何标识。递归方法的参数v是父节点,for循环出来的u是子节点,只需要让这两对保持不同即可
class Solution {
boolean flag = true;
boolean[] visited;
boolean[] colors;
public boolean isBipartite(int[][] graph) {
visited = new boolean[graph.length];
colors = new boolean[graph.length];
for (int i = 0; i < graph.length; i++) {
if (!visited[i]) {
traverse(graph,i);
}
}
return flag;
}
void traverse(int[][] graph, int v) {
if (!flag) {
return;
}
visited[v] = true;
for (int u : graph[v]) {
if (!visited[u]) {
colors[u] = !colors[v];
traverse(graph,u);
}else {
if (colors[u] == colors[v]) {
flag = false;
return;
}
}
}
}
}
二、886. 可能的二分法
题目链接:https://leetcode.cn/problems/possible-bipartition/
思路:和上一题类似,也是看看能否二分图,不过没给邻接表,自己构建一下邻接表,然后就是正常遍历判断是否是二分图
class Solution {
boolean flag = true;
boolean[] visited;
boolean[] colors;
public boolean possibleBipartition(int n, int[][] dislikes) {
List<Integer>[] graph = buildGraph(n, dislikes);
visited = new boolean[n];
colors = new boolean[n];
for (int i = 0; i < graph.length; i++) {
if (!visited[i]) {
traverse(graph, i);
}
}
return flag;
}
List<Integer>[] buildGraph(int n, int[][] dislikes) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] ints : dislikes) {
graph[ints[0]-1].add(ints[1]-1);
graph[ints[1]-1].add(ints[0]-1);
}
return graph;
}
void traverse(List<Integer>[] graph, int v) {
if (!flag) {
return;
}
visited[v] = true;
for (Integer u : graph[v]) {
if (!visited[u]) {
colors[u] = !colors[v];
traverse(graph, u);
}else {
if (colors[u] == colors[v]) {
flag = false;
return;
}
}
}
}
}
文章来源:https://blog.csdn.net/qq_43511039/article/details/135169918
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!