785. Is Graph Bipartite?
Leetcode Depth-first Search Breath-first Search GraphGiven an undirected graph
, return true
if and only if it is bipartite.
Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form: graph[i]
is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i]
does not contain i, and it doesn't contain any element twice.
Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation:
The graph looks like this:
0----1
| |
| |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.
Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation:
The graph looks like this:
0----1
| \ |
| \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.
Note:
- graph will have length in range [1, 100].
graph[i]
will contain integers in range [0, graph.length - 1].graph[i]
will not contain i or duplicate values.- The graph is undirected: if any element j is in
graph[i]
, then i will be ingraph[j]
.
分析¶
判断二分图。详细分析和解答在Algorithms 4th这本书中。
private boolean bipartitable;
public boolean isBipartite(int[][] graph) {
bipartitable = true;
boolean[] marked = new boolean[graph.length];
boolean[] color = new boolean[graph.length];
for (int v = 0; v < graph.length; v++)
if (bipartitable && !marked[v])
dfs(graph, color, marked, v);
return bipartitable;
}
private void dfs(int[][] graph, boolean[] color, boolean[] marked, int v) {
marked[v] = true;
for (int w : graph[v]){
if (!bipartitable) return;
else if (!marked[w]) {
color[w] = !color[v];
dfs(graph, color, marked, w);
}
else if (color[w] == color[v]) bipartitable = false;
}
}