Morg0th's blog

Help with graph bipartite check
By Morg0th, 9 months ago, In English

bool isBipartite = true;

void dfs(int node, int color) { vis[node] = color;

for(auto it: adj[node])
{
    if(vis[it] == 0)
    {
       dfs(it, 3 - color);
    }
    if(vis[it] == vis[node])
    {
       isBipartite = false;
       return;
    }
}

}

can someone tell me what is wrong with this implementation i was doin building teams problem on cses

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Morg0th (previous revision, new revision, compare).

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your function looks correct to me. I think you assumed that the graph will have only $$$1$$$ connected component, which is wrong.

Also, it would be better if you shared your entire code, the problem can be anywhere after all.

→ Reply