Семинар 19.02 Подгруппа 106-2
Для допуска к следующей домашней работе необходимо до семинара в следующий вторник решить задачу:
Дан ориентированный граф. Проверить, является ли граф сильно связным.
Дополнительные задачи:
(*) Дан неориентированный граф. Написать алгоритм раскраски этого графа в два цвета (белый, красный). Результатом алгоритма должен быть массив, i-ый элемент которого равен Red или White (значения enum-а), что означает, что i-ая вершина покрашена в данный цвет.
Если так раскрасить граф нельзя, то алгоритм должен об этом сообщить.
(*) Дана матрица A из 0 и 1, представляющая собой лабиринт.
Если A[i][j] == 0, значит эта клетка свободна, в противном случае на этой клетке расположена стена. Из каждой клетки можно идти наверх, вниз, вправо или влево, если в выбранном направлении есть соседняя клетка, и она свободна.
Даны координаты точки Старт и точки Финиш. Нужно найти наименьшее число шагов, которые нужно сделать, чтобы дойти от точки Старт до точки Финиш или вывести "NO", если такого пути нет.
В качестве альтернативы проверки сильной связности можно решить две дополнительные задачи.
Решенные задачи необходимо прислать на ревью на адрес review.cs.hse.106.2@gmail.com