// DFS sobre un camino de n nodos, primero con pila explícita y luego con recursión.
//   build/deep_recursion n
#include <cstdlib>
#include <iostream>
#include <vector>

#include "digraph.h"

namespace {

// noinline: si el compilador la mezcla consigo misma, ya no se mide un marco por nodo.
__attribute__((noinline)) void visit(const Digraph& g, std::vector<bool>& marked, int u, int& finished) {
    marked[u] = true;
    for (int v : g[u]) {
        if (!marked[v]) visit(g, marked, v, finished);
    }
    finished++;
}

}  // namespace

int main(int argc, char** argv) {
    int n = argc > 1 ? std::atoi(argv[1]) : 1000000;
    Digraph path(static_cast<std::size_t>(n));
    for (int i = 0; i + 1 < n; i++) path[i].push_back(i + 1);

    DfsTimes t = dfs_iterative(path);
    std::cout << "con pila explícita: terminaron " << t.finish_order.size() << " nodos" << std::endl;

    std::vector<bool> marked(static_cast<std::size_t>(n), false);
    int finished = 0;
    visit(path, marked, 0, finished);
    std::cout << "con recursión: terminaron " << finished << " nodos" << std::endl;
}