ACM UVA (10004)

/*
 *******************************************************************************
 *
 * Filename: 10004.cpp
 *
 * Author: Ye Xiaofeng , yexfeng # gmail.com
 *
 *******************************************************************************
 */

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <list>
#include <vector>

#define RED 0x10
#define BLK 0x11

using namespace std;

class Graph
{
protected:
    int vertex_num;
    int edge_num;
public:
    virtual void insertEdge(int v1, int v2) = 0;
    virtual void show() = 0;
    virtual int degree(int v) = 0;
    virtual int isPathExisted(int va, int vb) = 0;
    virtual int isEulerCircuitExisted(int v1, int v2) = 0;
};

class AdjListGraph : public Graph
{
protected:
    vector < list<int> > adjlist;
public:
    AdjListGraph();
    ~AdjListGraph();
    AdjListGraph(int v_num);
    void show();
    int degree(int v){};
    void insertEdge(int v1, int v2);
    int isPathExisted(int va, int vb){};
    int isEulerCircuitExisted(int v1, int v2){};
};

AdjListGraph :: AdjListGraph()
{
    vertex_num = 0;
    edge_num = 0;
}

AdjListGraph :: AdjListGraph(int v_num)
{
    int i;
    list<int> *edge_list;

    for (i = 0; i < v_num; i++) {
        edge_list = new list<int>;
        adjlist.push_back(*edge_list);
    }
    vertex_num = v_num;
    edge_num = 0;
}

/*
 * Insert an edge which connects v1 and v2.
 */
void AdjListGraph::insertEdge(int v1, int v2)
{
    if (v1 > vertex_num || v2 > vertex_num) {
        return;
    }
    adjlist[v1].push_back(v2);
    adjlist[v2].push_back(v1);
}

void AdjListGraph::show()
{
    list<int>::const_iterator pos;
    for (int i = 0; i < vertex_num; i++) {
        for (pos = adjlist[i].begin(); pos != adjlist[i].end(); pos++) {
            cout << i << "-" << *pos << endl;
        }
    }
}

AdjListGraph::~AdjListGraph()
{
    adjlist.clear();
}

class MyGraph : public AdjListGraph
{
public:
    MyGraph(int v_num);
    bool checkBicolored();
};

MyGraph :: MyGraph(int v_num) : AdjListGraph(v_num)
{
}

bool MyGraph :: checkBicolored()
{
    int left = vertex_num;
    int pos;
    vector<int>::const_iterator unvisited_cursor;
    list<int>::const_iterator connected_cursor;
    vector<int> unvisited;
    vector<int> unvisited_tmp;
    int *vertexColor = (int *)new int[vertex_num];

    memset(vertexColor, 0, vertex_num * sizeof(int));

    vertexColor[0] = BLK;
    unvisited.push_back(0);
    do {
        unvisited_tmp.clear();
        for (unvisited_cursor = unvisited.begin();
             unvisited_cursor != unvisited.end(); unvisited_cursor++) {
            for (connected_cursor = adjlist[*unvisited_cursor].begin();
                 connected_cursor != adjlist[*unvisited_cursor].end(); connected_cursor++) {
                 if (vertexColor[*connected_cursor] == vertexColor[*unvisited_cursor]) {
                     return false;
                 } else if (vertexColor[*connected_cursor] == 0) {
                     vertexColor[*connected_cursor] = BLK + RED - vertexColor[*unvisited_cursor];
                     unvisited_tmp.push_back(*connected_cursor);
                 }
            }
        }
        unvisited.clear();
        unvisited = unvisited_tmp;
    } while (unvisited.size() != 0);

    return true;

}

int main(int argc, char **argv)
{
    MyGraph *gr;
    int vertex_num = 0;
    int edge_num = 0;
    int v1, v2;

    cin >> vertex_num;
    while (vertex_num != 0) {
        cin >> edge_num;
        gr = new MyGraph(vertex_num);
        for (int i = 0; i < edge_num; i++) {
            cin >> v1 >> v2;
            gr->insertEdge(v1, v2);
        }
        if (gr->checkBicolored()) {
            cout << "BICOLORABLE." << endl;
        } else {
            cout << "NOT BICOLORABLE." << endl;
        }
        delete gr;
        cin >> vertex_num;
    }
}