Нужно найти любой гамильнонов цикл (в данном случае он всегда существует, т.к. если n вершин, то каждая имеет N/2 дуг, выходящих из нее).
Есть хорошо работающий алгоритм (аля поиск в глубину), однако на некоторых тестах, вылетает за пределы времени (больше 7 секунд, ограничение на N<=1000).
Может быть есть какие-то усовершенстоввания?

ну тогда лучше посмотреть сам алгоритм, чтобы уже можно было смотреть на возможные пути оптимизации

n - число вершин, x- номер вершины с которой надо строить цикл (хотя это имеет разницу, только для вывода результата)
mas - матрица смежности, check[i] - посещена ли вершина или нет, inorder - порядок прохождения. Вообщем реализован обычный перебор.

хм... выделим из графа 4 вершины: a,b,c,d, пусть, они все связаны
так вот если мы будем начинать наш поиск пути, например из a, то мы будем просматривать все варианты:
a,b,c,d,<тут все варианты путей для остального графа>
a,c,b,d,<тут все варианты путей для остального графа>
это я правильно понял (для этого алгоритма)?

если да, то тут есть место для оптимизации:
дело в том, что когда мы приняли к рассмотрению путь, начинающийся с a,b,c,d, мы вполне можем отсечь пути, начинающиеся с a,c,b,d, потому что они дадут точно такой же результат (не важно, положительный или отрицательный)

вот только есть проблемка: тогда нужно запоминать, какие пути мы уже просмотрели, а для этого, понадобится большой объем памяти
благодаря отсечениям количество путей не будет что-то типа n! (да к тому же и граф не полносвязный), но все равно будет немалым количеством

для отсечения нам нужно будет отвечать на вопрос: являются ли два пути эквивалентными
если да - то нечего просматривать дальше второй, если первый уже был просмотрен
под эквивалентностью будем понимать такое:
если множества (т.е. без учета порядка) путей и их последние вершины совпадают - они эквивалентны, нет - так нет...
потому и для хранить пути нужно в виде множества+последняя вершина

для начала введем класс CPath для хранения и сравнения путей:
CPath(i) - путь, состоящий из одной i-й вершины
path+i - путь path, к которому добавлена i-я вершина
path1==path2 - пути эквивалентны
path.Contains(i) - проверяет, содержит ли путь i-ю вершину
path.Last - номер последней вершины в пути
path.Length - длина пути

тогда функцию надо будет переписать так:

Добавлено @ 04:27
кстати, можно каким-то образом ограничить исползование памяти:
1. можно тупо сделать ограничение на размер массива - тогда поиск будетидти быстро, покамассив не закончится, а потом начнет тормозить
2. можно ограничить длину путей, которые будут добавляться в массив (тогда, соответственно, и количество всевозможных таких путейбудет меньше), тогда попытки отсечения будут делаться на первых нескольких шагах, а потом - обычный перебор, по-моему, этот способ лучше первого, т.к. отчесение на первых шагах может сэкономить больше времени, нежели на последних
3. задать максимальный размер массива, а при его достижении как-то интеллектуально выбирать самый "уже бесполезный путь" и удалять его, вполне может быть, что подойдет, например, самый старый
третий путь - самый общий
если удалять всегда только новые элементы - получаем первый способ
если удалять всегда самые длинные элементы - получаем второй

примерно дея понятна

но нашла " немного" другой алгоритм решения, даннной задачи... прошел на ура все тесты.

было бы интересно его увидеть
(перечитал... создалось ощущение какой-то скептической окраски предложения... ничего такого не подразумевалось - просто интересно )

Алгоритм взят с кникжи Котова. Он основан на том, что из каждой вершины выходит имено N/2 дуг.