| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
Здравствуйте! Решал задачу на нахождения цикла в ориентированом графе. Проблема в том, что мой код вылетает на больших тестах. Помогите разобраться в чем проблема.
Cам код.
У меня вылетает на тесте, если есть цикл в последовательности: 1, 2, 3, 4...N, 1; N = 100000;
Заранее Спасибо!!!
Переполнение стека рекурсий?
Вот именно я не знаю))
Попробуй увеличить размер стека при компиляций.
Ну, попробуй бфс-ом решить.
Можно подробнее?
Скорее всего действительно проблема с переполнением стэка. Немного полезных команд при работе с GCC (работают и под MinGW, и под Linux):
g++ -ggdb a.cpp -o a(добавлен ключ-ggdb) — включить отладочную информацию о номерах строк в исполняемый файл, на время выполнения не влияет вообще.gdb ./a— запустить программу под отладчиком. После этого можно вводить разные команды, пошагово выполнять, ставить breakpoints и тому подобное. У меня обычно сессия ограничивается тремя командами:run— запустить выполнение. Обычно после этого приложение падает.where— вывести стэк вызовов, в самом верху будет строка, в которой произошла последняя ошибка, фатальная.quit— выйти из gdb.Чтобы проверить на переполнение стэка, можно увеличить его размер при локальном тестировании. Под Windows надо добавить еще один параметр компилятору:
-Wl,--stack=256000000(ставит стэк в 256 МБ, без пробелов). Под Linux размер стэка — это параметр пользователя (а не исполняемого файла), поэтому перед запуском приложения надо выполнить командуulimit -s 256000(тоже 256 МБ). Если после этого программа не падает — проблема в переполнении стэка. Либо пытаться что-то соптимизировать, либо писать стэк руками и писать dfs нерекурсивно, либо использовать другой нерекурсивный алгоритм.Возможно, было бы полезно заодно ознакомиться с http://codeforces.me/blog/entry/5166