Bicoloring/문보창

소감

2005/05/11 Accepted 0:00.002 64

평이한 문제. 이산수학이 생각난다. if...else 구문을 사용할때 모든 조건을 프로그램에서 포함하는지 주의깊게 코딩해야 한다.

코드

// no10004 - Bicoloring
#include <iostream>
using namespace std;

#define RED 1
#define BLACK 2
#define MAX_VERTEX 200

bool input(int edge[][2], int * nVertex, int * nInputLine);
bool isBicolorale(int edge[][2], int nVertex, int nInputLine);
bool paintColor(int count, int vertex, int * color);

int main()
{
	int nVertex;
	int nInputLine;
	int edge[MAX_VERTEX][2];
	while (input(edge, &nVertex, &nInputLine))
	{
		if (isBicolorale(edge, nVertex, nInputLine))
			cout << "BICOLORABLE.\n";
		else
			cout << "NOT BICOLORABLE.\n";
	}
	return 0;
}

bool isBicolorale(int edge[][2], int nVertex, int nInputLine)
{
	bool check[MAX_VERTEX] = {0,};		// using node = nInputLine
	int color[MAX_VERTEX] = {0,};		// using vertex = nVertex
	color[0] = BLACK;					// 0's Node = BLACK
	int count = 0;						// count = vertex number
	while (count != nVertex)
	{
		for (int i = 0; i < nInputLine; i++)
		{
			if (check[i] == false)		 // check 되지 않은 라인
			{
				if (count == edge[i][0]) //
				{
					if (paintColor(count, edge[i][1], color) == false)
						return false;
				}
				if (count == edge[i][1])
				{	
					if (paintColor(count, edge[i][0], color) == false)
						return false;
				}				
			}
		}
		count++;
	}
	return true;
}

bool paintColor(int count, int vertex, int * color)
{
	if (color[count] == BLACK)
	{
		if (color[vertex] == BLACK)
			return false;
		color[vertex] = RED;
	}
	else
	{
		if (color[vertex] == RED)
			return false;
		color[vertex] = BLACK;
	}
	return true;
}

bool input(int edge[][2], int * nVertex, int * nInputLine)
{
	cin >> *nVertex;
	if (*nVertex == 0)
		return false;
	cin >> *nInputLine;
	for (int i = 0; i < *nInputLine; i++)
		cin >> edge[i][0] >> edge[i][1];
	return true;
}

---

AOI Bicoloring