Bipartite Checking (DFS) | Competitive Programming

BFS and DFS Variation

(b)  (Bipartite Checking or Bi-coloring):

Basics:

(1)   http://www.shafaetsplanet.com/planetcoding/?p=604.  (Last paragraph)

(2)   https://www.geeksforgeeks.org/bipartite-graph/

Problems:

(1)   10004 – Bicoloring (UVa).

(2)   BICOLOR – Bicolor (SPOJ).

(3)   Bipartite Graph (Geeksforgeeks).

///Bicoloring2.cpp (DFS)

int color[2020];

bool dfs(int u, int c) // color array initially -1 and c=0

{

    if(color[u]==c) return true;

    else if(color[u]==1-c) return false;

    color[u]=c;

    bool ret=true;

    for(int i=0;i<g[u].size();i++)

        ret&=dfs(g[u][i],1-c);

    return ret;

}