Шестерёнки

Задание

N шестеpенок пpонумеpованы от 0 до N (N<=10). Задана матрица соединений паp шестеpенoк в виде C[i,j]=1, если шестеpня с номеpом i находится в зацеплении с шестеpней j, где 1<=i<j<=N . Можно ли повеpнуть шестеpню с заданным номеpом? Если да, то найти количество шестеpен, пpишедших в движение.

Решение     [вверх]

Будем обозначать вращение по часовой стрелке нулем, против единицей. Сначала припишем шестерне с заданным номером число нуль. На следующем шаге всем шестерням, сцепленным с заданной, будут приписаны числа 1 (они будут вращаться в противоположную шестерне 1 сторону). Далее всем шестерням, находящимся в зацеплении с занумерованными на предыдущем шаге, припишем значения 0 и и.т.д.

Процесс будем повторять до тех пор, пока либо на очередном шаге ни одной шестерне не будет приписано новое значение, и тогда шестерню с заданным номером удастся повернуть, и число рассмотренных шестеренок и есть искомое число пришедших в движение, либо на каком-то шаге пометка шестерни изменяется с 1 на 0 или с 0 на 1, и тогда система в движение не придет.

Значение направления поворота шестерёнке будем хранить в массиве rotate. Для обхода шестерёнок и присвоения значений массиву rotate будем использовать поиск в ширину.

Формальное описание

Gears()
1. Создать матрицу смежности для графа.
2. Прочитать номер стартовой шестерёнки.
3. Произвести поиск в ширину со стартовой вершины (пп.3.1-3.5):
   3.1. Инициализировать значения массива направлений значениями -1.
   3.2. Задать направление вращения стартовой вершины нулём.
   3.3. Добавить стартовую вершину в очередь.
   3.4. Пока очередь не пуста и не произошло замены вращения шестерёнки,
        повторять пп. 3.4.1-3.4.5:
        3.4.1. Получить текущую вершину из очереди.
        3.4.2. Найти все инцедентные вершины.
        3.4.3. Если для найденной вершины не было установлено направление
               вращения, то установить вращение отличное от направления
               предыдущей шестерёнки и добавить вершину в очередь.
        3.4.4. Если найденная вершина имеет такое же направление вращение,
               как и предыдущая, то считать, что произошла замена вращения
               шестерёнки.
        3.4.5. Удалить вершину из очереди.
4. Если замены не произошло, то считать, что система шестерёнок будет 
   вращаться и найти количество вращающихся шестерёнок; 
   иначе считать, что система вращаться не будет.   

Пример графа из двух компонент связности для задачи "Шестерёнки".

Если запустить любую шестерёнку из первой компоненты (№0-№6), то система будет вращаться, причём шестерёнки с однаковым направлением вращения обозначены одним цветом. Если запустить любую шестерёнку из второй компоенты связности (№7-№11), то истема вращаться не будет, так как шестерёнки 8 и 9 будут иметь одинаковые направления вращения.