UVA - 10004 - Bicoloring.cpp

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
#define MAX 200

using namespace std;
typedef long long int lng;

int main()
{
    lng n, l, x, y, len, maxLevel;

    while(true)
    {
        scanf("%lld", &n);
        if (!n) break;      /// If n is zero, break
        scanf("%lld", &l);

        vector<lng> g[n];   /// The list graph
        queue<lng> q;       /// Declare queue here to make it empty
        lng level[n];
        memset(level, -1, sizeof level);

        /// Take input
        for (lng i = 0; i<l; i++)
        {
            scanf("%lld %lld", &x, &y);

            /// As its bi-directional graph
            g[x].push_back(y);
            g[y].push_back(x);
        }

        /// Scaffold
        q.push(0);
        level[0] = maxLevel = 0;

        /// Calculate levels
        while(!q.empty())
        {
            x = q.front(); q.pop();
            len = g[x].size();

            for (y = 0; y<len; y++)
            {
                if (level[g[x][y]] == -1) {
                    level[g[x][y]] = level[x] + 1;
                    q.push(g[x][y]);

                    /// Update maxLevel
                    if(level[g[x][y]] > maxLevel) maxLevel = level[g[x][y]];
                }
            }
        }

        bool possible = true;
        for (lng i = 0; i<n; i++)
        {
            len = g[i].size();
            for (lng j = 0; j<len; j++)
            {
                /// If adjacent nodes have same level
                if (level[i] == level[g[i][j]]) {
                    possible = false;
                    break;
                }
            }
        }

        if (possible) puts("BICOLORABLE.");
        else puts("NOT BICOLORABLE.");
    }
}