| 1 | class Solution { |
| 2 | // depth first search |
| 3 | public boolean color(int src, int graph[][], int color[]){ |
| 4 | Queue<Integer> queue = new LinkedList<>(); |
| 5 | queue.offer(src); |
| 6 | color[src] = 0; |
| 7 | while(!queue.isEmpty()){ |
| 8 | int node = queue.poll(); |
| 9 | for(int neighbour : graph[node]){ |
| 10 | if(color[neighbour]==-1){ |
| 11 | color[neighbour] = 1 - color[node]; |
| 12 | queue.offer(neighbour); |
| 13 | }else if(color[neighbour] == color[node]){ |
| 14 | return false; |
| 15 | } |
| 16 | } |
| 17 | } |
| 18 | return true; |
| 19 | } |
| 20 | public boolean isBipartite(int[][] graph) { |
| 21 | int n = graph.length; |
| 22 | int color[] = new int[n]; |