Олимпиадная задача по информатике

Здравствуйте. Попалась интересная задача по информатике, но никак не могу подступиться к задача(. Знаю то, что скорее всего задача на графы, вот только я с ними никогда не работал.

Даны n шестерёнок, некоторые из них соединены между собой. Две сцепленные шестерёнки
могут вращаться только в разных направлениях. Вам необходимо выяснить, может ли вращаться
вся система шестерёнок, и если может, указать наименьшее количество шестерёнок, которые нужно
заставить вращаться

Формат входных данных
В первой строке записаны два целых числа: n — количество шестерёнок и m — количество
сцеплений между ними. В каждой из следующих m строк записаны
два различных числа i и j, которые определяют номера сцепленных шестерёнок. Все шестерёнки
пронумерованы целыми числами от 1 до n.

Формат выходных данных
В первой строке запишите одно число k — наименьшее количество шестерёнок, которые нужно
заставить вращаться. В следующей строке k целых чисел — номера этих шестерёнок. Если решений
несколько, выведите любое из них. Если запустить все шестерёнки невозможно, выведите -1.

Ввод:
6 3
4 5
2 1
3 2
Вывод:
3
1 4 6
----------------
Ввод:
4 3
1 2
2 4
4 1
Вывод:
-1

0

Не очень понятен вывод первого примера. Шестеренки 1, 2, 3 и 6 сцеплены, соответственно запуская шестеренку 1, мы запускаем и все прочие, а значит вывод должен быть "1 4"

А так это простейшая задача на графы, приводите входные данные к виду дерева, путешествуете по дереву, начиная с любого элемента, попутно присваивая встречающимся элементам количество сделанных шагов, если очередной элемент уже пронумерован, то разница между текущим шагом и записанным ранее должна быть четной, чтобы соблюдалось условие задачи, если она нечетная, значит вращаться она не может. Если цепочка пройдена до конца, берем первый непройденный элемент и повторяем действие. Количество таких итераций и будет ответом, хотя как написал выше, логика почему 1 4 6 а не 1 4 мне не ясна.

0

renat_dmitriev, ответ должен быть - "те шестерёнки, на которые нужно поставить двигатель", так понятнее?
ставим двигатель на шестерёнку 1 - питаются 1 2 3
ставим двигатель на шестерёнку 4 - питаются 4 5
ставим двигатель на шестерёнку 6 - питаются 6
все запитали
ответ 1 4 6

0

Kuzia domovenok, Почему 3 питается от 2, а 6 не питается от 3?

0

renat_dmitriev, потому что во входных данных есть строчка 3 2 и нет строчки 6 3

Добавлено через 42 секунды

Сообщение от Commodore44 В первой строке записаны два целых числа: n — количество шестерёнок и m — количество сцеплений между ними. В каждой из следующих m строк записаны...

следующих, !!!, не в первой

1

Kuzia domovenok, Ах, сорри, не внимателен был.

0

Надо разбить граф на компоненты связности. Их число - это число К из условия. Если среди компонент найдется хотя бы одна, содержащая цикл нечётной длины - ответ -1.

2

Стоит, наверное, также учитывать: если пары сцепленных шестерёнок таковы:

1 2
2 3
3 1,

то система работать не будет. Не будет крутиться ни туда, ни сюда.

0

aaamibor, эта задача не на физику. Вообще, кто изучал механику машин, должен знать, что для того чтобы даже две шестерни вращались в зацеплении должны так-то довольно хитрые условия выполняться по всяким эвольхрентам, не говоря уже правильному соотношению передаточных чисел числу зубьев в системах из более двух колёс.
Конкретно данная задача опускает всю физику/механику, а значит и не надо учитывать направления движения.

0

Kuzia domovenok, тогда зачем в задаче было вот это?

Две сцепленные шестерёнки могут вращаться только в разных направлениях.

Либо мы даже таких тонкостей не упоминаем, либо разбираем физику хотя бы в таких масштабах.

0

aaamibor, от физики тут ничего. Та фраза нужна только от защиты от хитрых глупых ответов типа "с проскальзыванием, с отломом зубьев куда хочешь вращай".

А сама задача собственно сводится к нескольким:
1. определить сколько независимых систем шестерёнок есть. Наверное, проще всего решать это последовательным заполнением массивов "независимые системы"
2. определить если хотя бы одна система, которую невозможно раскрутить (т.е. проверить если ли там циклы с нечётным числом шестерней)
3. посчитать, сколько надо добавить шестерней (Надо подумать. Возможно, хватит банального "кол-во_независимых-1"

Только это всё настолько условно, что в жизни работать не будет)) Вот если бы количество зубьев давалось...

0

Сообщение от Дмитррр определить сколько независимых систем шестерёнок есть. Наверное, проще всего решать это последовательным заполнением массивов "независимые системы"

Компоненты связности

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

Двудольный граф

Сообщение от Дмитррр Возможно, хватит банального "кол-во_независимых-1"

Ровно кол-во_независимых

0

Дмитррр,

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

Воооооот. Примерно это я и хотел сказать своим примером.

Сообщение от aaamibor 1 2 2 3 3 1

Цикл с тремя шестерёнками. Крутиться не будет ни в какую сторону.

0