Bipartite graphs and a question on its application

BIPARTITE GRAPHS

If in a graph, we can divide the vertices into two disjoint set such that no two vertices in the same set is adjacent.

All acyclic graphs are bipartitie.

All the closed walks or cycles in it are of even length.

Complete Bipartite Graphs

Graphs with all the vertices in one set joining all other in the other set.

Crown Graph

Complete graph with horizontal edges removed.

Question Time!

http://www.spoj.com/problems/BUGLIFE/

Question kehna kya chahta hai?

There are male and female bugs in an experiment. As the experiment only allows non homo bugs, given which bug has sex with which bug, we have to tell if there is a mysterious homo among them.

Concept

We use the concept of 2-color coloring here. Its pretty simple. Initially all the nodes are white. Take a node. Mark it as red. Now mark all the adjacent nodes as black.
If you are on a red node and see that there is another red node adjacent to it...HOMO. Similarly with black.
If all the nodes are colored without any problem, no homos in the house.

How to do it?

Maintain an array of the color of nodes. and an array of visited nodes.
White==1
Red ==2
Black==3
Take a source node.
Apply dfs and color the nodes alternately and mark the visited nodes.
If two adjacent have same color, return -1 else return 0.

Code:

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int ans,grid[2005][2005],check[2005],color[2005];


int dfs(int v,int n){
    if(!color[v]) color[v]=1;

    for(int i=1;i<=n;i++){
        if(grid[v][i]){
            //cout<<v<<" "<<i<<" "<<color[v]<<" "<<color[i]<<endl;
            if(!color[i]) {color[i]= color[v]==1?2:1;if(dfs(i,n)) return 1;}
            else
            if(color[i]==color[v]) return 1;
        }
    }
    return 0;
}

int solve(int n){
    memset(check,0,sizeof(check));
    for(int i=1;i<=n;i++){
            if(!color[i]) if(dfs(i,n)) return 1;
    }
    return 0;
}


int main() {
    int t,tt=1;
    cin>>t;
   
    while(t--){
        memset(grid,0,sizeof(grid));
        memset(color,0,sizeof(color));
        int num,in,a,b;
        cin>>num>>in;
       
        while(in--){
            cin>>a>>b;
            grid[a][b]=1;
        }
       
        cout<<"Scenario #"<<tt++<<":\n";
        if(solve(num))
            cout<<"Suspicious bugs found!";
        else
            cout<<"No suspicious bugs found!";
        cout<<"\n";
    }
    return 0;
}