Оптимизировать алгоритм

[Sonic86]

Возможно я туплю, но что-то не могу ничего придумать.
Дано $n$ точек с номерами от 1 до $n$. Каждой точке поставлено в соответствие еще 2 точки - предыдущая и следующая, так что все множество точек разбивается на множество циклов произвольной длины (гарантируется, что длина цикла не меньше 3-х точек). Надо найти алгоритм последовательного вывода циклов с последовательным выводом точек в каждом цикле.
Сейчас у меня алгоритм $O(n^2)$. Можно ли сделать быстрее? Скорость $O(n \ln n)$ вполне бы меня удовлетворила.
Пытался делать по аналогии с сортировкой массива, но не получается.

[venco]

Дык, простой обход массива, с запоминанием встреченных точек - $O(n)$ плюс $O(n)$ памяти.

[Sonic86]

О! Действительно! Спасибо!

-- Чт ноя 18, 2010 15:56:57 --

Нет, не понял.
Я Вас понял так: для данного массива создаем новый двумерный массив, в каждый столбец которого пишутся точки своего цикла Рассматриваем текущую точку. Пробегаемся по столбцам нового массива по концам уже найденных цепочек. Если на каком-то шаге точка подходит к началу/концу данной цепочки - дописываем ее в начало/конец этой цепочки. Если ни на каком шаге точка не подошла, то заводим новый столбец в двумерном массиве.
Но тогда получается, что мы на самом деле не можем различить точку нового цикла и далекую точку старого цикла.
Например, если дано $n$ вершин и они организованы в цикл $1-2-...-n-1$, а в исходном массиве записаны как $1,3,5,...2,4,6,...$, то мы так в конце построим не одну итоговую цепочку, а несколько.

Что я не понял?

[TOTAL]

В ящиках с номерами от $1$ до $n$ лежат числа. Берём число из первого непустого ящика и записываем его, за ним следующее и т.д. (до окончания цикла). Снова берём число из первого непустого ящика и т.д. С самого начала храним (и обновляем) номер первого непустого ящика, последнего непустого ящика, следующего непустого ящика (это для каждого непустого ящика).

[Sonic86]

TOTAL писал(а):

В ящиках с номерами от $1$ до $n$ лежат числа. Берём число из первого непустого ящика и записываем его, за ним следующее и т.д. (до окончания цикла). Снова берём число из первого непустого ящика и т.д. С самого начала храним (и обновляем) номер первого непустого ящика, последнего непустого ящика, следующего непустого ящика (это для каждого непустого ящика).

Ага! Если я правильно Вас понял, то у меня так и работает. Но это как раз в худшем случае $O(n^2)$. Т.е. если эти $n$ точек организованы в, скажем, $\frac{n}{5}$ циклов длиной 5, причем точки каждого цикла равномерно распределены по данному массиву, то нам будет необходимо пройти по $n$ точек, чтобы вытащить каждый цикл, т.е. всего $O(n \cdot \frac{n}{5})=O(n^2)$ (ну там даже если пустые элементы игнорировать все равно получится $O(n^2)$).
Правильно я понял?

-- Чт ноя 18, 2010 16:37:18 --

venco, TOTAL М.б. я какой-то момент упустил? (Скажите, проект и так горит...)

-- Чт ноя 18, 2010 16:51:39 --

Может быть так сделать: рассматриваем входящие точки как куски циклов длины 1, для которых известны точки, которые можно подсоединить к их концам. Создаем новый пустой массив кусков циклов. Проходим по старому массиву, для каждого куска цикла старого массива пробегаемся по новому массиву и проверяем - подходит этот кусок хотя бы к одному куску из нового массива, если подходит - то соединяем куски, иначе - пишем его в новый столбец нового массива. После прохода по старому массиву новый массив будет представлять из себя тоже массив кусков циклов, только кусков будет меньше и они будут длиннее. Записываем теперь новый массив в старый, а новый очищаем и повторяем итерации до тех пор пока не образуются полные циклы. И получается еще, что если на каком-то шаге образовался полный цикл, то его можно вывести и не рассматривать...
М.б. так будет быстрее работать ? Правда писанины будет много и геморроя тоже...

[TOTAL]

Sonic86 в сообщении #376971 писал(а):

то нам будет необходимо пройти по $n$ точек, чтобы вытащить каждый цикл

Не по всем, т.к. номер следующегоо ящика из цикла известен.

[venco]

Sonic86, пробегаете цикл один раз. Встретив новую точку, от неё пробегаете внутренний цикл, помечая всё на ходу. Каждая точка встретится максимум 2 раза, один раз во внешнем цикле, и максимум один раз во внутреннем.

[Евгений Машеров]

0. Вспомогательная память - битовый вектор соответственно числу точек, начальное значение 0.
1. Внешний цикл. Находим нулевой элемент вектора. Печатаем "начало нового цикла". Передаём номер найденного элемента во внутренний цикл. Если все элементы ненулевые - конец работы.
2. Внутренний цикл. Начинаем с переданного элемента. Выводим его.
Переходим к следующему. Если он помечен 1, то заканчиваем внутренний цикл. Иначе помечаем его 1 и выводим номер.

[arseniiv]

Евгений Машеров в сообщении #377083 писал(а):

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

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

[Sonic86]

venco, TOTAL
Прошу прощенья, я затупил, я слишком упростил задачу, у меня-то тут вершины пронумерованы не $1,2,...,n$, а $m_1,m_2,...m_n$ и поэтому когда номера $1,2,...,n$, то Вы можете говорить, что

TOTAL писал(а):

Не по всем, т.к. номер следующегоо ящика из цикла известен.

venco писал(а):

Встретив новую точку, от неё пробегаете внутренний цикл, помечая всё на ходу.

а я говорил, что ищу за $O(n)$. Ну я теперь номера $m_1,m_2,...m_n$ отсортировал и ищу за $O(\ln n)$, так что теперь все работает быстро.
Спасибо большое!