Bipartite Checking (BFS) | Competitive Programming

BFS and DFS Variation

(a)  (Bipartite Checking or Bi-coloring) General BFS approach

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

// bicoloring.cpp

// (Data Structure: graph, color)

vector<int>g[1000];

int color[1000];

bool bfs(int s)

{

    memset(color,-1,sizeof(color));

    queue<int>q;

    color[s]=0;

    q.push(s);

    while(!q.empty())

    {

        int u =q.front();

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

        {

            if(color[g[u][i]]==-1)

            {

                color[g[u][i]]=(color[u]==0)?1:0;

                q.push(g[u][i]);

            }

            else

            {

                if(color[g[u][i]]==color[u])

                    return false;

            }

        }

        q.pop();

    }

    return true;

}