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