class Solution {
public boolean isBipartite(int[][] graph) {
// 和一个node直接连接的node一定不可能和它同组
if (graph == null || graph.length == 0) {
return true;
}
Map<Integer, Integer> visited = new HashMap<>();
for (int i = 0; i < graph.length; i++) {
if (!bfs(i, visited, graph)) {
return false;
}
}
return true;
}
private boolean bfs(int i, Map<Integer, Integer> visited, int[][] graph) {
if (visited.containsKey(i)) {
return true;
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
visited.put(i, 0);
while (!queue.isEmpty()) {
int cur = queue.poll();
int curGroup = visited.get(cur);
int neiGroup = curGroup == 0 ? 1 : 0;
for (int j = 0; j < graph[cur].length; j++) {
if (!visited.containsKey(graph[cur][j])) {
visited.put(graph[cur][j], neiGroup);
queue.offer(graph[cur][j]);
} else {
if (visited.get(graph[cur][j]) != neiGroup) {
return false;
}
}
}
}
return true;
}
}