ACM (UVa) : 10004


#include <iostream>
using namespace std;

struct node {
    string s;
    int value;
} a [205];

int node_number;
bool matrix [205] [205];

void reset ()
{
    for ( int i = 0; i < 205; i++ ) {
        a [i].s = "white";
        a [i].value = 0;
    }

    for ( int i = 0; i < 205; i++ ) {
        for ( int j = 0; j < 205; j++ )
            matrix [i] [j] = false;
    }
}

int find () {

    for ( int i = 0; i < node_number; i++ ) {
        if ( a [i].s == "gray" )
            return i;
    }

    return -1;

}

int main ()
{
    while ( cin >> node_number && node_number ) {

        bool final_result = true;

        reset ();

        int edge;
        cin >> edge;

        while ( edge-- ) {

            int x;
            int y;

            cin >> x >> y;

            matrix [x] [y] = true;
        }

        a [0].value = 1;
        a [0].s = "gray";

        int index = find ();

        while ( index != -1 ) {

            if ( a [index].value == 1 ) {
                for ( int i = 0; i < node_number; i++ ) {
                    if ( matrix [index] [i] == true ) {

                        if ( a [i].value == 1 )
                            final_result = false;
                        else
                            a [i].value = 2;

                        if ( a [i].s == "white" )
                        a [i].s = "gray";
                    }
                }
            }

            else {

                for ( int i = 0; i < node_number; i++ ) {
                    if ( matrix [index] [i] == true ) {

                        if ( a [i].value == 2 )
                            final_result = false;
                        else
                            a [i].value = 1;

                        if ( a [i].s == "white" )
                        a [i].s = "gray";
                    }
                }

            }

            a [index].s = "black";
            index = find ();

        }

        if ( final_result )
        cout << "BICOLORABLE." << endl;
        else
        cout << "NOT BICOLORABLE." << endl;

    }

    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s