This is my solution for detecting bipartite graph using bfs .It passes one case but fails one testcase on leetcode. problem:https://leetcode.com/problems/is-graph-bipartite the testcase is:[[1,2,3],[0,2],[0,1,3],[0,2]]. Can anyone let me know what's wrong?
here is my code:
class Solution {
public boolean isBipartite(int graph[][]) {
//ArrayList<ArrayList<Integer>> adj=new ArrayList<>();
int color[]=new int[graph.length];
Arrays.fill(color,-1);
for(int i=0;i<graph.length;i++)
{
if(color[i]==-1)
{
if(!checkbipartite(i,graph,color))
return false;
}
}
return true;
}
public boolean checkbipartite(int node,int graph[][],int color[])
{
Queue<Integer> q=new LinkedList<>();
q.add(node);
color[node]=1;
while(!q.isEmpty())
{
Integer nde=q.poll();
for(Integer it:graph[node])
{
if(color[it]==-1)
{
color[it]=1-color[nde];
q.add(it);
}
else if(color[it]==color[nde])
return false;
}
}
return true;
}
}
One character can make all the difference :)
I believe this line:
for(Integer it:graph[node])
should be:
for(Integer it:graph[nde])
With this your code appears to work, at least on the two test cases provided in the problem page.