Блог пользователя TxCowboy

Автор TxCowboy, 10 лет назад, По-русски

Здравствуйте! Решал задачу на нахождения цикла в ориентированом графе. Проблема в том, что мой код вылетает на больших тестах. Помогите разобраться в чем проблема.

Cам код.

У меня вылетает на тесте, если есть цикл в последовательности: 1, 2, 3, 4...N, 1; N = 100000;

Заранее Спасибо!!!

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Переполнение стека рекурсий?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ну, попробуй бфс-ом решить.

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Скорее всего действительно проблема с переполнением стэка. Немного полезных команд при работе с GCC (работают и под MinGW, и под Linux):

  1. g++ -ggdb a.cpp -o a (добавлен ключ -ggdb) — включить отладочную информацию о номерах строк в исполняемый файл, на время выполнения не влияет вообще.
  2. gdb ./a — запустить программу под отладчиком. После этого можно вводить разные команды, пошагово выполнять, ставить breakpoints и тому подобное. У меня обычно сессия ограничивается тремя командами:
  3. run — запустить выполнение. Обычно после этого приложение падает.
  4. where — вывести стэк вызовов, в самом верху будет строка, в которой произошла последняя ошибка, фатальная.
  5. quit — выйти из gdb.

Чтобы проверить на переполнение стэка, можно увеличить его размер при локальном тестировании. Под Windows надо добавить еще один параметр компилятору: -Wl,--stack=256000000 (ставит стэк в 256 МБ, без пробелов). Под Linux размер стэка — это параметр пользователя (а не исполняемого файла), поэтому перед запуском приложения надо выполнить команду ulimit -s 256000 (тоже 256 МБ). Если после этого программа не падает — проблема в переполнении стэка. Либо пытаться что-то соптимизировать, либо писать стэк руками и писать dfs нерекурсивно, либо использовать другой нерекурсивный алгоритм.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Возможно, было бы полезно заодно ознакомиться с http://mirror.codeforces.com/blog/entry/5166