Given an undirected graph, returntrueif 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 indexesjfor which the edge between nodesiandjexists. Each node is an integer between0andgraph.length - 1. There are no self edges or parallel edges:graph[i]does not containi, 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 in graph[j].
分析
因为有不可达的离散点,所以DFS BFS都要FOR LOOP来检验那些不可达的点。
BFS
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] visited = new int[n];
for(int i = 0; i < n; i++){
if(visited[i] == 0){
Queue<Integer> q = new LinkedList<>();
visited[i] = 1;
q.offer(i);
while(!q.isEmpty()){
int cur = q.poll();
for(int nb : graph[cur]){
if(visited[nb] == 0){
visited[nb] = - visited[cur];
q.offer(nb);
}else if(visited[nb] == visited[cur]){
return false;
}
}
}
}
}
return true;
}
}
DFS
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] visited = new int[n];
for(int i = 0; i < n; i++){
if(visited[i] == 0 && !dfs(graph,visited,i,1)){
return false;
}
}
return true;
}
boolean dfs(int[][] graph, int[] visited, int p, int color){
if(visited[p] != 0){
return visited[p] == color;
}
visited[p] = color;
for(int nb : graph[p]){
//比较此处的和BFS, 这里直接判断邻居。BFS需要赋值,存入之类的
if(!dfs(graph,visited,nb,-color)){
return false;
}
}
return true;
}
}