UVa 10004 - Bicoloring

///DFS SOLUTION

// aarifshuvo   ``CSEJU

#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;
}

----***---

///BFS SOLUTION:

//aarifshuvo   ``CSEJU

#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;
}