10004. Раскраска двумя цветами

Имеется связный неориентированный граф. Определить, можно ли покрасить его вершины двумя цветами так, чтобы никакие две соседние вершины не были покрашены одним цветом.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество вершин n (1 < n < 200) в графе. Вторая строка содержит количество ребер l. Каждая из следующих l строк содержит два числа – номера вершин графа, соединенные ребром. Вершины графа нумеруются числами от 0 до n – 1. Последняя строка содержит n = 0 и не обрабатывается.

Выход. Для каждого теста вывести строку “BICOLORABLE.”, если вершины графа можно раскрасить требуемым образом, и “NOT BICOLORABLE.” иначе.

Пример входа

3

3

0 1

1 2

2 0

9

8

0 1

0 2

0 3

0 4

0 5

0 6

0 7

0 8

0

Пример выхода

NOT BICOLORABLE.

BICOLORABLE.

РЕШЕНИЕ

поиск в глубину

Анализ алгоритма

Для решения задачи воспользуемся поиском в глубину. Изначально вершины не просмотрены, пометим их все цветом 0. По мере прохождения по вершинам будем красить их в два цвета: 1 и 2. Если текущая вершина имеет цвет i (i = 1, 2), то следующую вершину, в которую мы попадаем при поиске в глубину, красим в цвет 3 – i. При этом проверяем, чтобы две соседние вершины не были покрашены в одинаковый цвет.

Реализация алгоритма

Матрицу смежности графа храним в массиве g размера MAX = 200. Массив mark содержит информацию о цвете вершины. Глобальная переменная Error отвечает за правильность раскраски: как только найдутся две соседние вершины, покрашенные одинаково, переменная примет значение 1.

#define MAX 200

int g[MAX][MAX], mark[MAX], Error;

Процедура dfs выполняет поиск в глубину. Ей передаются два параметра: текущая вершина v и ее цвет color. Если уже встретился случай невозможности требуемой раскраски (Error = 1), то выйти из процедуры. Помечаем вершину v цветом color. Ищем непросмотренную вершину i, в которую можно пойти продолжив поиск в глубину. При этом если соседняя вершина i уже была просмотрена, проверяем условие окрашенности вершин v и i в разные цвета. Если указанные вершины покрашены в одинаковый цвет, устанавливаем Error = 1.

void dfs(int v,int color)

{

int i;

if (Error) return;

mark[v] = color;

for(i = 0; i < n; i++)

if (g[v][i])

if (!mark[i]) dfs(i,3-color); else

if (mark[v] == mark[i]) Error = 1;

}

Основной цикл программы. Читаем число вершин графа n и количество ребер l. Обнуляем матрицу смежности и массив mark.

while(scanf("%d %d",&n,&l), n)

{

memset(g,0,sizeof(g));

memset(mark,0,sizeof(mark));

Читаем данные графа.

for(i = 0; i < l; i++)

{

scanf("%d %d",&a,&b);

g[a][b] = g[b][a] = 1;

}

Обнуляем значение переменной Error, запускаем процедуру поиска в глубину с нулевой вершины.

Error = 0; dfs(0,1);

В зависимости от значения переменной Error выводим результат.

if (Error) printf("NOT BICOLORABLE.\n");

else printf("BICOLORABLE.\n");

}