在 leetcode 上的一个问题的测试用例中检测 java 中的二分图解决方案失败

Question

这是我使用 bfs 检测二分图的解决方案。它通过了一个案例，但未通过 leetcode 上的一个测试案例。问题：https://leetcode.com/problems/is-graph-bipartite 测试用例是：[[1,2,3],[0,2],[0,1,3],[0,2]]。谁能告诉我怎么了？

这是我的代码：

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

}

Answer 1

一个角色可以改变一切:)

我相信这条线：

for(Integer it:graph[node])

应该是：

for(Integer it:graph[nde])

有了这个，您的代码似乎可以工作，至少在问题页面中提供的两个测试用例上是这样。

在 leetcode 上的一个问题的测试用例中检测 java 中的二分图解决方案失败

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

java

graph

breadth-first-search

bipartite