## Friday, December 26, 2014

### UVa Problem 10004 - Bicoloring

Problem:

Solution:

Testing if a graph is bipartite using BFS.

This is so far the problem I quickly done to AC - it tooks 10 minutes end to end from coding to submission.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=945

#include "UVa10004.h"

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int UVa10004()
{
while (true)
{
int number_of_nodes;
cin >> number_of_nodes;
if (number_of_nodes == 0)
{
break;
}
int number_of_edges;
cin >> number_of_edges;

for (int e = 0; e < number_of_edges; e++)
{
int src;
int dst;
cin >> src;
cin >> dst;
}

vector<int> colors;
colors.resize(number_of_nodes);
for (int i = 0; i < number_of_nodes; i++)
{
colors[i] = -1;
}

colors[0] = 0;
queue<int> bfs_queue;
bfs_queue.push(0);
bool valid = true;
while (bfs_queue.size() > 0 && valid)
{
int v = bfs_queue.front();
bfs_queue.pop();
{
int n = *ni;
if (colors[n] == -1)
{
colors[n] = 1 - colors[v];
bfs_queue.push(n);
}
else if (colors[n] != 1 - colors[v])
{
valid = false;
}
}
}

if (valid)
{
cout << "BICOLORABLE." << endl;
}
else
{
cout << "NOT BICOLORABLE." << endl;
}
}
return 0;
}