Thursday 1 January 2015

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();
}

}

No comments:

Post a Comment