Muh DFS template

dfs.cpp

#include <vector>
#include <utility>

using Graph = std::vector<std::vector<int>>;

enum class Visited { WHITE, GREY, BLACK };

void DFSVisit(size_t start, const Graph& graph, std::vector<Visited>& colormap);

void TraverseGraphInDfsOrder(const Graph& graph) {
    std::vector<Visited> colormap(graph.size());
    for (size_t i = 0; i < graph.size(); ++i) {
        if (colormap[i] == Visited::WHITE) {
            DFSVisit(i, graph, colormap);
        }
    }
}

void DFSVisit(size_t start, const Graph& graph, std::vector<Visited>& colormap) {
    colormap[start] = Visited::GREY;
    std::vector<std::pair<size_t, size_t>> dfs_stack;
    dfs_stack.emplace_back(start, 0);

    while (!dfs_stack.empty()) {
        auto [this_vertice, next] = dfs_stack.back();
        for (size_t i = next; i < graph.at(this_vertice).size(); ++i) {
            auto next_ver = graph.at(this_vertice).at(i);
            ++dfs_stack.back().second;
            if (colormap.at(next_ver) == Visited::WHITE) {
                colormap[next_ver] = Visited::GREY;
                dfs_stack.emplace_back(next_ver, 0);
                break;
            }
        }
        if (next >= graph.at(this_vertice).size()) {
            auto leaving = dfs_stack.back().first;
            colormap[leaving] = Visited::BLACK;
            dfs_stack.pop_back();
        }
    }
}