UVa 10004 - Bicoloring

// aarifshuvo   ``CSEJU
// BisMillahir Rahmanir Rahim


///DFS SOLUTION

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

ll n,e,u,l,v;
vector<ll>adj[209];
int vis[209];
int col[209];

int dfs(int u)
{
    vis[u] = 1;

    REP(i,SZ(adj[u]))
    {
        int v = adj[u][i];

        if(!vis[v])

            col[v] = col[u]^1, dfs(v);

        else if(col[v]^col[u]==0) return 0;
    }

    return 1;
}


int main()
{
    while(scl(n) and n)
    {
        scl(l);

        REP(i,l) scll(u,v), adj[u].push_back(v), adj[v].push_back(u);

        if(dfs(0)) printf("BICOLORABLE.\n");
        else printf("NOT BICOLORABLE.\n");

        REP(i,209) adj[i].clear();
        memset(col,0,sizeof col);
        memset(vis,0,sizeof vis);
    }
    return 0;
}

/*

3
3
0 1
1 2
2 0
3
2
0 1
1 2
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8

*/

BFS SOLUTION: 

// aarifshuvo   ``CSEJU

// BisMillahir Rahmanir Rahim

#include <bits/stdc++.h>

#define ll long long

#define SZ(x) ((int)(x).size())

#define scl(x) scanf("%lld", &x)

#define scll(x,y) scanf("%lld %lld", &x, &y)

#define ALL(x) (x).begin(),(x).end()

#define REP(i,n) for(int i=0;i<n;i++)

#define REV(i,n) for(int i=n-1;i>=0;i--)

#define FOR(i,a,b) for(int i=a;i<=b;i++)

#define pri(a) cout<<a<<endl

#define prii(a,b) cout<<a<<" "<<b<<endl

using namespace std;

ll n,l,u,v;

vector<ll> adj[209];

ll col[209];

int bfs(int src)

{

    memset(col,-1,sizeof col);

    queue<ll> q;

    q.push(src);

    col[src]=1;

    while(!q.empty())

    {

        int u = q.front(); q.pop();

        REP(i,SZ(adj[u]))

        {

            int v = adj[u][i];

            if(col[v]==-1)      // if adjacent is undiscovered

            {

                if(col[u]==1) col[v]=2;

                else if(col[u]==2) col[v]=1;

                q.push(v);

            }

            else

            {

                if(col[u]==col[v]) return 0;

            }

        }

    }

    return 1;

}

int main()

{

    while(scl(n) and n)

    {

        scl(l);

        REP(i,l) scll(u,v), adj[u].push_back(v), adj[v].push_back(u);

        if(bfs(0)) printf("BICOLORABLE.\n");

        else printf("NOT BICOLORABLE.\n");

        REP(i,209) adj[i].clear();

    }

    return 0;

}