Семинар 19.02 Подгруппа 106-2

Для допуска к следующей домашней работе необходимо до семинара в следующий вторник решить задачу:

Дан ориентированный граф. Проверить, является ли граф сильно связным.

Дополнительные задачи:

(*) Дан неориентированный граф. Написать алгоритм раскраски этого графа в два цвета (белый, красный). Результатом алгоритма должен быть массив, i-ый элемент которого равен Red или White (значения enum-а), что означает, что i-ая вершина покрашена в данный цвет.

Если так раскрасить граф нельзя, то алгоритм должен об этом сообщить.

(*) Дана матрица A из 0 и 1, представляющая собой лабиринт.

Если A[i][j] == 0, значит эта клетка свободна, в противном случае на этой клетке расположена стена. Из каждой клетки можно идти наверх, вниз, вправо или влево, если в выбранном направлении есть соседняя клетка, и она свободна.

Даны координаты точки Старт и точки Финиш. Нужно найти наименьшее число шагов, которые нужно сделать, чтобы дойти от точки Старт до точки Финиш или вывести "NO", если такого пути нет.

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

Решенные задачи необходимо прислать на ревью на адрес review.cs.hse.106.2@gmail.com