BUGLIFE-A Bug’s Life

A Bug’s Life

Given below code is for BUGLIFE spoj or A Bug's life spoj.

Explanation : Use simple bfs to find cycle of odd length , or check graph is bipartite or not.

#include <bits/stdc++.h>
using namespace std;
int G[2019][2019]={0,0};
int chec(int a);
int n;
int colorArr[2019];
int main()
{
    int t,m,x,y,i;
    scanf("%d",&t);
    for(int test = 1 ; test <= t ; test++)
    {
        memset(G,0,sizeof(G));
        int flag=0;
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            G[x][y]=1;
            G[y][x]=1;
        }
        int res;
        for ( i = 1; i <= n; i++)
        colorArr[i] = -1;

        for(i=1;i<=n;i++)
        {
            if(colorArr[i]== -1)
            {
                res=chec(i);
                if(res==0)
                {
                    flag=1;
                    break;
                }
            }
        }
        if(flag==1)
            printf("Scenario #%d:\nSuspicious bugs found!\n",test);
        else
            printf("Scenario #%d:\nNo suspicious bugs found!\n",test);
    }
    return 0;
}

int chec(int start)
{   
    colorArr[start] = 1;
 
    queue <int> q;
    q.push(start);
    while (!q.empty())
    {
       
        int i = q.front();
        q.pop();
 
       
        for (int j = 1; j <= n; j++)
        {
            if (G[i][j] && colorArr[j] == -1)
            {
       
                colorArr[j] = 1 - colorArr[i];
                q.push(j);
            }
            else if (G[i][j] && colorArr[j] == colorArr[i])
                return 0;
        }
    }
    return 1;
}