4002. Долой
списывание!
Во время контрольной работы
профессор Флойд заметил, что некоторые студенты обмениваются записками. Сначала
он хотел поставить им всем двойки, но в тот день профессор был добрым, а потому
решил разделить студентов на две группы: списывающих и дающих списывать, и
поставить двойки только первым.
У профессора записаны все пары
студентов, обменявшихся записками. Требуется определить, сможет ли он разделить
студентов на две группы так, чтобы любой обмен записками осуществлялся от
студента одной группы студенту другой группы.
Вход. В
первой строке находятся два числа n и
m – количество студентов и количество
пар студентов, обменивающихся записками (1 ≤ n ≤ 100, 0 ≤ m
≤ (n * (n – 1)) / 2). Далее в m строках
расположены описания пар студентов: два различных числа, соответствующие
номерам студентов, обменивающимися записками (нумерация студентов идёт
с 1). Каждая пара студентов перечислена не более одного раза.
Выход. Вывести
ответ на задачу профессора Флойда. Если можно разделить студентов на две
группы, выведите "YES", иначе выведите "NO".
|
Пример
входа |
Пример
выхода |
|
3 2 1 2 2 3 |
YES |
РЕШЕНИЕ
поиск в
глубину
Анализ алгоритма
В задаче
требуется выяснить, является ли заданный граф двухцветным. То есть можно ли его
вершины покрасить двумя цветами так чтобы любое ребро соединяло вершины разных
цветов.
Двухцветность в
графе проверяется при помощи поиска в глубину. Отметим, что входной граф может быть несвязным.
Пример
Граф приведенный
в примере имеет вид:
Реализация алгоритма
Объявим матрицу
смежности g и массив
использованных вершин used.
#define MAX 110
int g[MAX][MAX],
used[MAX];
Функция dfs совершает поиск в глубину из вершины v. Вершину v красим цветом color.
void dfs(int v, int color)
{
Если граф не двуцветный (Error = 1), то продолжать поиск в глубину нет смысла.
if
(Error) return;
Присваиваем цвет color вершине v.
used[v] = color;
Перебираем вершины i, ищем
куда можно пойти из v в i.
for (int i =
1; i <= n; i++)
Если существует ребро из v в i.
if (g[v][i])
Если вершина i еще не
просмотрена, то продолжаем из нее поиск в глубину.
if
(!used[i]) dfs(i, 3 - color); else
Если из v в i существует обратное ребро, а
вершины v и i покрашены в одинаковый цвет, то граф не двухцветный.
Устанавливаем Error =
1.
if
(used[v] == used[i]) Error = 1;
}
Основная часть программы. Читаем список ребер графа, строим матрицу смежности.
scanf("%d %d",
&n, &m);
memset(g, 0, sizeof(m));
memset(used, 0, sizeof(used));
for (i = 0; i < m; i++)
{
scanf("%d
%d", &a, &b);
g[a][b] =
g[b][a] = 1;
}
Запускаем поиск в глубину, корень
красим цветом 1. Граф может быть несвязный. Error = 0 означает что граф двухцветный, Error = 1 означает что нет.
Error = 0;
for (i = 1; i <= n; i++)
if
(!used[i]) dfs(i, 1);
В зависимости от значения переменной Error выводим ответ.
if (Error) printf("NO\n"); else
printf("YES\n");