public boolean isBipartite(int[][] graph) {

if (graph.length == 0) return true;

int N = graph.length;

int[] visited = new int[N];

for (int i=0; i<N; i++) {

if (visited[i] == 0 && !helper(graph, i, visited, 1)) return false;

}

return true;

}

private boolean helper(int[][] graph, int curr, int[] visited, int pre) {

if (visited[curr] != 0) return visited[curr] == pre;

visited[curr] = pre;

for (int next: graph[curr]) {

if (visited[next] == pre) return false;

if (visited[next] == 0) {

if (!helper(graph, next, visited, -pre)) return false;

}

}

return true;

}

public boolean isBipartite2(int[][] graph) {

if (graph.length == 0) return true;

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.add(i);

while (!q.isEmpty()) {

int curr = q.poll();

for (int next: graph[curr]) {

if (visited[next] == 0) {

visited[next] = - visited[curr];

q.add(next);

} else {

if (visited[next] == visited[curr]) return false;

}

}

}

}

}

return true;

}

/**

public boolean isBipartite3(int[][] graph) {

int n= graph.length;

int[] parent= new int[n];

for(int i=0; i<n; i++){

parent[i]=i;

}

for(int i=0; i<n; i++){

for(int j=1; j<graph[i].length; j++){

parent[findParent(parent,graph[i][j])]=findParent(parent,graph[i][0]);

}

}

for(int i=0; i<n; i++){

if(graph[i].length>0){

if(findParent(parent,i)==findParent(parent,graph[i][0])) return false;

}

}

return true;

}

private int findParent(int[]parent, int p){

if(parent[p]==p) return p;

parent[p]=findParent(parent, parent[p]);

return parent[p];

}