Spoj BUGLIFE Solution

#include<bits/stdc++.h>

#define White 1

#define Black 2

#define N 2005

using namespace std;

int a[N][N], c[N], node, edge, white, black;

bool check(int start)

{

    c[start] = White;

    queue<int>q;

    q.push(start);

    while(!q.empty())

    {

        int x = q.front();

        q.pop();

        if(a[x][x] == 1)

            return false;

        for(int i=1; i<=node; i++)

        {

            if(a[x][i] == 1 && c[i] == 0)

            {

                if(c[x] == White)

                    c[i] = Black;

                else if(c[x] == Black)

                    c[i] = White;

                q.push(i);

            }

            if(a[x][i] == 1 && c[x] == c[i])

                return false;

        }

    }

    return true;

}

bool Bipartite()

{

    for(int i=1; i<=node; i++)

    {

        if(c[i] == 0 && check(i) == false)

return false;

    }

    return true;

}

void clear1()

{

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

{

c[i] = 0;

for(int j=0;j<=node;j++)

a[i][j] = 0;

}

}

int main()

{

    int t, j = 1;

    cin >> t;

    while(t--)

    {

        cin >> node >> edge;

        int n1, n2;

clear1();

        for(int i=1; i<=edge; i++)

        {

            cin >> n1 >> n2;

            a[n1][n2] = 1;

            a[n2][n1] = 1;

        }

        cout << "Scenario #" << j++ << ":\n";

        if(Bipartite() == true)

            cout << "No suspicious bugs found!" << "\n";

        else

            cout << "Suspicious bugs found!" << "\n";

    }

    return 0;

}