javagraphbreadth-first-searchbipartite

Detecting Bipartite graph solution in java fails in a testcase in a problem on leetcode


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;
}

}


Solution

  • 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.