Условие:
есть набор пар переходов вида:
1-> 2
1-> 3
2-> 4
4-> 1

Под циклом понимается наличие таких переходов, при которых переход осуществляется в себя же.
В данном примере это 1->2->4->1.

Метод последовательного анализа каждого элемента не подходит: неизвестно есть ли цикл у других элементов, т.е. если начинаем анализировать 1 которая переходит в 2, которая, в свою очередь, имеет цикл вида 2->3->2, то алгоритм зависнет.

Всю голову уже сломал - подскажите направление в котором стоит думать, или может быть кто-то сможет алгоритм на псевдоязыке набросать.

Крестики рисовать в каждой позиции. Перешли в 1 - пишем "Здесь был Вася!". Если при переходе в новую позицию какие-то вандалы стены расписали - значит мы тут уже были...

просто не ходи обратно, в ту "вершину" (первое число из пары), откуда только что пришел

А чем плохи ориентированные графы тут? Строим граф из переходов и ищем нужные циклы..

Ну как же?

А если графы?
Тупо набираем в Google "поиск циклов в графах" и тут же вываливается... Мне эта Google вывалила аж 9300 ссылок: и лекции, и алгоритмы, и математики, и программисты. Тут читать надо, а не голову ломать.

Возможна иная интерпретация, при которой ёрничество совершенно не уместно: автор топика просто не знает, что его вопрос изучается теорией графов.
В таком случае нужно не ёрничать, а просто подсказать.
Но такой подход не вяжется с названием темы, где ЯВНО указано: НЕ ПРО ГРАФЫ!


Это сообщение отредактировал(а) Sefko - 7.3.2009, 20:54

Задача легко дедуцируется на нахождение циклов в графах. Эта в свою очередь решается с помощью DFS. Но если условия таковы, что графы использовать нельзя, тогда пожалуй просто тупо зарезервируй битовый массив под числа. на каждую пару алгоритм такой:

visited[n] = {false}
check (a, b)
{
if (visited[b] == true) print b " is visited"
else
{
visited[a] = true;
visited[b] = true;
}
}