Рекурсивный DFS падает с stack overflow на цепочке из 10^6 вершин — как обойти?
Пишу обычный рекурсивный обход в глубину:
vector<int> g[N];
bool used[N];
void dfs(int v) {
used[v] = true;
for (int u : g[v]) if (!used[u]) dfs(u);
}
На большинстве тестов работает, но на тесте, где граф — это длинная цепочка (1-2-3-...-1000000), получаю Runtime Error (сегфолт). Локально воспроизводится. Это переполнение стека рекурсии? Как обойти, не теряя простоту?
2 ответа
Да, это именно переполнение системного стека. Глубина рекурсии равна длине цепочки (~10^6), а на каждый кадр уходит десятки-сотни байт, плюс итератор по g[v] хранится в кадре. Стандартный лимит стека — 1–8 МБ, его не хватает.
Два рабочих способа.
- Итеративный DFS на явном стеке. Кладём вершины в
std::stack, имитируем рекурсию. Важно помечатьusedв момент извлечения или добавления — следите, чтобы вершина не попала в стек дважды:
void dfs(int s) {
stack<int> st;
st.push(s);
used[s] = true;
while (!st.empty()) {
int v = st.top(); st.pop();
for (int u : g[v]) if (!used[u]) {
used[u] = true;
st.push(u);
}
}
}
Это чистый обход (порядок не совпадает с рекурсивным pre-order, но связность/компоненты считает верно). Сложность O(V+E), память O(V) на стек.
- Увеличить системный стек. На Codeforces часто запускают так:
// через отдельный поток с большим стеком
#include <thread>
int main() {
std::thread t(solve, /*args*/); // запускаем solve в потоке
t.join(); // со стеком, заданным платформой
}
или под GCC/Linux через setrlimit(RLIMIT_STACK, ...). Но переписать на явный стек надёжнее и переносимее.
Сложность алгоритма в обоих случаях остаётся O(V+E).
Добавлю частую грабли при итеративном DFS, если нужен именно порядок как у рекурсии (например, для tin/low или post-order). Тогда нельзя просто пихать соседей — нужно хранить в стеке состояние «на каком соседе остановились»:
stack<pair<int,int>> st; // {вершина, индекс следующего соседа}
st.push({s, 0}); used[s] = true;
while (!st.empty()) {
auto& [v, i] = st.top();
if (i < (int)g[v].size()) {
int u = g[v][i++];
if (!used[u]) { used[u] = true; st.push({u, 0}); }
} else {
// здесь post-order обработка v
st.pop();
}
}
Это точная эмуляция рекурсии: pre-order — при push, post-order — при pop. Незаменимо, когда переписываете рекурсивный Тарьян/мосты под итеративный из-за глубины.