bipartite graph (BUGS LIFE) SPOJ

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

usual mistake treated the vertices in the code starting from 0 but not modifying the input which is generally of the form where numbering starts from 1.
so that needs to taken care of in graph (ALWAYS)

#include<stdio.h>
#include<vector>
#include<queue>
 int N,flag;
using namespace std;
int visited[2000+5];
vector<int> g[2000];
int bpg(int v)
{
    visited[v]=1;
    queue<int> q;
    q.push(v);
   // int flag=0;
    while(!q.empty())
    {
        int y=q.front();
        q.pop();
        for(int i=0;i<g[y].size();i++)
        {
            int r=g[y][i];
            if(!visited[r])
            {   q.push(r);
                if(visited[y]==1)
                {

                    visited[r]=2;
                }
                else if(visited[y]==2)
                    visited[r]=1;


            }
            else
            {
                if(visited[r]==visited[y])
                {
                    flag=1;
                    break;
                }
            }

        }
        if(flag==1)
            break;
    }
}

int main()
{
   //freopen("kr.in","r",stdin);
int t,m,n ,i,a,b;
int ee=0;
scanf("%d",&t);
while(t--)
{   flag=0;
ee++;
    scanf("%d %d",&m,&n);
    //vector<int > g[m];
    for( i=0;i<n;i++)
    {
        scanf("%d %d",&a,&b);
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);

        // remember if it doesnt work make it undirected

    }
    N=m;
    for(i=0;i<2000;i++)
    {
        visited[i]=0;
    }
    for( i=0;i<m;i++)
    {
        if(!visited[i])
        {
            bpg(i);
        }
    }
    printf("Scenario #%d:\n",ee);
    if(flag==1)
        printf("Suspicious bugs found!\n");
    else
        printf("No suspicious bugs found!\n");
    for( i=0;i<2000;i++)
        g[i].clear();
}

}

Simple bfs and dfs

// N-> total nodes , graph[N][N] adjacency matrix

int bfs(int start,int end)

{

    list <int > q ;

    q.push_back(y);

    int visited[N],frontt;

    visited[start]=1;

    memset(vi,0,N*sizeof(int));

    

    while(!q.empty())

    {

          frontt=q.front();

          

          q.pop_front();

          for(int i=0;i<N;i++)

          { 

                   if(graph[frontt][i] && !visited[i])

                   {

                         visited[i]=1;

                         //graph[srart][i]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i

                        if(i==end)

                                return 1;

                        q.push_back(i);

                  }

           }

      }

return 0;

}

int dfs(int start,int end)

{

    list <int > st ;

    st.push_back(y);

    int visited[N],Top;

    visited[start]=1;

    memset(vi,0,N*sizeof(int));

    

    while(!st.empty())

    {

          Top=st.back();

          

          st.pop_back();

          for(int i=0;i<N;i++)

          { 

                   if(graph[Top][i] && !visited[i])

                   {

                         visited[i]=1;

                         //graph[srart][i]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i

                        if(i==end)

                                return 1;

                        st.push_back(i);

                  }

           }

      }

return 0;

}



Some tweaks for adjacency  list

If there are N nodes
Input form
N->total number of nodes
then N lines with x and as first element (showing its connected to x elements)


scanf("%d",&N);
vector <int>  graph [N];
for(int i=0;i<N;i++)
{
    scanf("%d",&x);
    for(int j=0;j<N;i++)
    {
        scanf("%d",&e);
        v[j].push_back(e);
    }
}

Code modifications in dfs (similar for bfs)

int dfs(int start,int end)

{

    list <int > st ;

    st.push_back(y);

    int visited[N],Top;

    visited[start]=1;

    memset(vi,0,N*sizeof(int));

    

    while(!st.empty())

    {

          Top=st.back();

          

          st.pop_back();
          vector <int>:: iterator iii;

          for(int iii=graph[Top].begin();iii!=graph[Top].end();iii++)

          { 

                   if(graph[Top][i] && !visited[i])

                   {

                         visited[*iii]=1;

                         //graph[srart][*iii]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i

                        if(*iii==end)

                                return 1;

                        st.push_back(*iii);

                  }

           }

      }

return 0;

}