785. Is Graph Bipartite?
Jeff posted on (updated on )
Question: https://leetcode.com/problems/is-graph-bipartite/
Post: https://leetcode.com/problems/is-graph-bipartite/discuss/1065679/java-bfs-assign-2-color
class Solution {
public boolean helper(int[][]graph, int[] color, int src) {
Queue<Integer> queue = new LinkedList<>();
// enqueue
color[src] = 0;
queue.offer(src);
while (queue.size() > 0) {
int head = queue.poll();
// find neighbor
for (int neighbor: graph[head]) {
// if color doesn't match
if (color[neighbor] == color[head]) {
return false;
}
// skip visited
if (color[neighbor] != -1) {
continue;
}
// enqueue
color[neighbor] = 1 - color[head];
queue.offer(neighbor);
}
}
return true;
}
public boolean isBipartite(int[][] graph) {
// 0 or 1
int[] color = new int[graph.length];
Arrays.fill(color, -1);
for (int i = 0; i < color.length; i++) {
if (color[i] != -1) {
continue;
}
boolean isGraphBipartite = helper(graph, color, i);
if (!isGraphBipartite) {
return false;
}
}
return true;
}
}