#Problem

#⭐️⭐️⭐️⭐️

Is Graph Bipartite ?

#Solution

BFS 涂色问题!

#Note

颜色如果用1和2来表示的话, 有个小trick可以用. 给当前结点涂颜色只要 3 - color[parent], 如果parent是1,那么当前结点就是2, and vice versa.

#Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public boolean isBipartite(int[][] graph) {
final int n = graph.length;
final int[] visited = new int[n];
final Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
visited[i] = 1;
queue.add(i);
while (!queue.isEmpty()) {
final int curr = queue.poll();
for (final int adj : graph[curr]) {
if (visited[adj] == visited[curr]) {
return false;
} else if (visited[adj] == 0) {
visited[adj] = 3 - visited[curr];
queue.add(adj);
}
}
}
}
}
return true;
}
}

Comments