DFS
(graph/dfs.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/dfs.hpp"

Overview

dfs performs iterative depth-first search and returns the DFS forest rather than recursing through the call stack. It provides parent paths, depths, discovery and finish times, preorder, postorder, and component roots.

Callback overloads additionally invoke a callback once when each vertex is discovered. They still return the complete DfsResult, and callback order is exactly result.preorder.

Use DFS when traversal nesting or finish order matters. The returned path is a DFS-tree path and is not necessarily shortest; use bfs for unweighted shortest paths.

Graph Orientation and Roots

Edge direction is respected. The helper works on directed graphs as written and on undirected graphs built with add_edge. Inactive edges are ignored, and adjacency-list order determines which DFS tree is produced.

dfs(graph, source) traverses one source. The multi-source overload completely traverses each source in the supplied order, skipping sources already reached by an earlier tree. dfs(graph) constructs a complete forest, choosing the smallest still-unvisited vertex as each new root.

Callbacks must not mutate the graph. They may safely update captured state.

Callback Signature

The primary callback signature is:

callback(int vertex, int parent);

parent is the DFS-tree parent of vertex. It is -1 when vertex is a single source or a root of the complete forest. For convenience, a callback with signature callback(int vertex) is also accepted when parent information is not needed.

Result

Member or method	Exact type or signature	Meaning
`depth`	`std::vector<int>`	DFS-tree depth, or `-1` when unreachable.
`parent`	`std::vector<int>`	Parent vertex, or `-1` for roots and unreachable vertices.
`parent_edge`	`std::vector<int>`	Edge used to enter each non-root vertex, or `-1`.
`root`	`std::vector<int>`	Root of each reached vertex’s DFS tree, or `-1`.
`tin`, `tout`	`std::vector<int>`	One-based discovery and finish timestamps, or `-1`. Every timestamp is distinct.
`preorder`	`std::vector<int>`	Vertices in discovery order.
`postorder`	`std::vector<int>`	Vertices in finish order.
`roots`	`std::vector<int>`	DFS-tree roots in traversal order.
`reachable`	`bool reachable(int vertex) const`	Tests whether `vertex` was reached.
`component_count`	`int component_count() const`	Returns `roots.size()`.
`path`	`std::vector<int> path(int target) const`	Restores the root-to-`target` DFS-tree path.
`is_ancestor`	`bool is_ancestor(int ancestor, int vertex) const`	Tests ancestry through timestamp containment; returns false if either vertex is unreachable.

Functions

Function	Exact signature	Description	Complexity
`dfs`	`template <class T> DfsResult dfs(const Graph<T>& graph, int source)`	Traverses vertices reachable from one source.	$O(N + M)$ time and $O(N)$ memory
`dfs`	`template <class T> DfsResult dfs(const Graph<T>& graph, const std::vector<int>& sources)`	Traverses ordered source trees.	$O(N + M)$ time and $O(N)$ memory
`dfs`	`template <class T> DfsResult dfs(const Graph<T>& graph)`	Traverses the complete DFS forest.	$O(N + M)$ time and $O(N)$ memory
`dfs`	`template <class T, class Callback> DfsResult dfs(const Graph<T>& graph, int source, Callback&& callback)`	Single-source DFS with one callback per discovered vertex.	$O(N + M + RF)$ time and $O(N)$ memory
`dfs`	`template <class T, class Callback> DfsResult dfs(const Graph<T>& graph, const std::vector<int>& sources, Callback&& callback)`	Ordered multi-source DFS with discovery callbacks.	$O(N + M + RF)$ time and $O(N)$ memory
`dfs`	`template <class T, class Callback> DfsResult dfs(const Graph<T>& graph, Callback&& callback)`	Complete DFS forest with discovery callbacks.	$O(N + M + NF)$ time and $O(N)$ memory

Here, R is the number of reached vertices and F is the cost of one callback.

Example

#include "graph/dfs.hpp"
#include "graph/graph.hpp"

#include <cassert>
#include <vector>

int main() {
    m1une::graph::Graph<> graph(4);
    graph.add_edge(0, 1);
    graph.add_edge(1, 2);
    graph.add_edge(0, 3);

    std::vector<int> discovered;
    auto result = m1une::graph::dfs(
        graph,
        0,
        [&](int vertex, int parent) {
            discovered.push_back(vertex);
            if (vertex == 0) assert(parent == -1);
        }
    );
    assert(result.reachable(2));
    assert(result.is_ancestor(0, 2));
    assert(result.path(2).front() == 0);
    assert(discovered == result.preorder);
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_DFS_HPP
#define M1UNE_GRAPH_DFS_HPP 1

#include <algorithm>
#include <cassert>
#include <concepts>
#include <functional>
#include <utility>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct DfsResult {
    std::vector<int> depth;
    std::vector<int> parent;
    std::vector<int> parent_edge;
    std::vector<int> root;
    std::vector<int> tin;
    std::vector<int> tout;
    std::vector<int> preorder;
    std::vector<int> postorder;
    std::vector<int> roots;

    bool reachable(int vertex) const {
        assert(0 <= vertex && vertex < int(depth.size()));
        return depth[vertex] != -1;
    }

    int component_count() const {
        return int(roots.size());
    }

    std::vector<int> path(int target) const {
        assert(reachable(target));
        std::vector<int> result;
        for (int vertex = target; vertex != -1; vertex = parent[vertex]) {
            result.push_back(vertex);
        }
        std::reverse(result.begin(), result.end());
        return result;
    }

    bool is_ancestor(int ancestor, int vertex) const {
        assert(0 <= ancestor && ancestor < int(depth.size()));
        assert(0 <= vertex && vertex < int(depth.size()));
        if (!reachable(ancestor) || !reachable(vertex)) return false;
        return tin[ancestor] <= tin[vertex] && tout[vertex] <= tout[ancestor];
    }
};

namespace dfs_detail {

template <class Callback>
concept DfsCallback =
    std::invocable<Callback&, int, int> ||
    std::invocable<Callback&, int>;

template <DfsCallback Callback>
void invoke_callback(Callback& callback, int vertex, int parent) {
    if constexpr (std::invocable<Callback&, int, int>) {
        std::invoke(callback, vertex, parent);
    } else {
        std::invoke(callback, vertex);
    }
}

template <class T, class Callback>
DfsResult run_dfs(
    const Graph<T>& graph,
    const std::vector<int>& sources,
    bool complete_forest,
    Callback& callback
) {
    const int n = graph.size();
    DfsResult result;
    result.depth.assign(n, -1);
    result.parent.assign(n, -1);
    result.parent_edge.assign(n, -1);
    result.root.assign(n, -1);
    result.tin.assign(n, -1);
    result.tout.assign(n, -1);
    result.preorder.reserve(n);
    result.postorder.reserve(n);
    result.roots.reserve(n);

    struct Frame {
        int vertex;
        int next_edge;
    };
    std::vector<Frame> stack;
    stack.reserve(n);
    int timer = 0;

    auto traverse = [&](int source) {
        assert(0 <= source && source < n);
        if (result.reachable(source)) return;

        result.depth[source] = 0;
        result.root[source] = source;
        result.tin[source] = ++timer;
        result.preorder.push_back(source);
        result.roots.push_back(source);
        invoke_callback(callback, source, -1);
        stack.push_back(Frame{source, 0});

        while (!stack.empty()) {
            Frame& frame = stack.back();
            int vertex = frame.vertex;
            if (frame.next_edge == int(graph[vertex].size())) {
                result.tout[vertex] = ++timer;
                result.postorder.push_back(vertex);
                stack.pop_back();
                continue;
            }

            const Edge<T>& edge = graph[vertex][frame.next_edge++];
            if (!edge.alive || result.reachable(edge.to)) continue;
            result.depth[edge.to] = result.depth[vertex] + 1;
            result.parent[edge.to] = vertex;
            result.parent_edge[edge.to] = edge.id;
            result.root[edge.to] = result.root[vertex];
            result.tin[edge.to] = ++timer;
            result.preorder.push_back(edge.to);
            invoke_callback(callback, edge.to, vertex);
            stack.push_back(Frame{edge.to, 0});
        }
    };

    for (int source : sources) traverse(source);
    if (complete_forest) {
        for (int vertex = 0; vertex < n; vertex++) traverse(vertex);
    }
    return result;
}

}  // namespace dfs_detail

template <class T>
DfsResult dfs(const Graph<T>& graph, const std::vector<int>& sources) {
    auto callback = [](int) {};
    return dfs_detail::run_dfs(graph, sources, false, callback);
}

template <class T>
DfsResult dfs(const Graph<T>& graph, int source) {
    return dfs(graph, std::vector<int>{source});
}

template <class T>
DfsResult dfs(const Graph<T>& graph) {
    auto callback = [](int) {};
    return dfs_detail::run_dfs(
        graph,
        std::vector<int>(),
        true,
        callback
    );
}

template <class T, class Callback>
requires dfs_detail::DfsCallback<Callback>
DfsResult dfs(
    const Graph<T>& graph,
    const std::vector<int>& sources,
    Callback&& callback
) {
    return dfs_detail::run_dfs(graph, sources, false, callback);
}

template <class T, class Callback>
requires dfs_detail::DfsCallback<Callback>
DfsResult dfs(const Graph<T>& graph, int source, Callback&& callback) {
    return dfs(
        graph,
        std::vector<int>{source},
        std::forward<Callback>(callback)
    );
}

template <class T, class Callback>
requires dfs_detail::DfsCallback<Callback>
DfsResult dfs(const Graph<T>& graph, Callback&& callback) {
    return dfs_detail::run_dfs(
        graph,
        std::vector<int>(),
        true,
        callback
    );
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_DFS_HPP

#line 1 "graph/dfs.hpp"



#include <algorithm>
#include <cassert>
#include <concepts>
#include <functional>
#include <utility>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 12 "graph/dfs.hpp"

namespace m1une {
namespace graph {

struct DfsResult {
    std::vector<int> depth;
    std::vector<int> parent;
    std::vector<int> parent_edge;
    std::vector<int> root;
    std::vector<int> tin;
    std::vector<int> tout;
    std::vector<int> preorder;
    std::vector<int> postorder;
    std::vector<int> roots;

    bool reachable(int vertex) const {
        assert(0 <= vertex && vertex < int(depth.size()));
        return depth[vertex] != -1;
    }

    int component_count() const {
        return int(roots.size());
    }

    std::vector<int> path(int target) const {
        assert(reachable(target));
        std::vector<int> result;
        for (int vertex = target; vertex != -1; vertex = parent[vertex]) {
            result.push_back(vertex);
        }
        std::reverse(result.begin(), result.end());
        return result;
    }

    bool is_ancestor(int ancestor, int vertex) const {
        assert(0 <= ancestor && ancestor < int(depth.size()));
        assert(0 <= vertex && vertex < int(depth.size()));
        if (!reachable(ancestor) || !reachable(vertex)) return false;
        return tin[ancestor] <= tin[vertex] && tout[vertex] <= tout[ancestor];
    }
};

namespace dfs_detail {

template <class Callback>
concept DfsCallback =
    std::invocable<Callback&, int, int> ||
    std::invocable<Callback&, int>;

template <DfsCallback Callback>
void invoke_callback(Callback& callback, int vertex, int parent) {
    if constexpr (std::invocable<Callback&, int, int>) {
        std::invoke(callback, vertex, parent);
    } else {
        std::invoke(callback, vertex);
    }
}

template <class T, class Callback>
DfsResult run_dfs(
    const Graph<T>& graph,
    const std::vector<int>& sources,
    bool complete_forest,
    Callback& callback
) {
    const int n = graph.size();
    DfsResult result;
    result.depth.assign(n, -1);
    result.parent.assign(n, -1);
    result.parent_edge.assign(n, -1);
    result.root.assign(n, -1);
    result.tin.assign(n, -1);
    result.tout.assign(n, -1);
    result.preorder.reserve(n);
    result.postorder.reserve(n);
    result.roots.reserve(n);

    struct Frame {
        int vertex;
        int next_edge;
    };
    std::vector<Frame> stack;
    stack.reserve(n);
    int timer = 0;

    auto traverse = [&](int source) {
        assert(0 <= source && source < n);
        if (result.reachable(source)) return;

        result.depth[source] = 0;
        result.root[source] = source;
        result.tin[source] = ++timer;
        result.preorder.push_back(source);
        result.roots.push_back(source);
        invoke_callback(callback, source, -1);
        stack.push_back(Frame{source, 0});

        while (!stack.empty()) {
            Frame& frame = stack.back();
            int vertex = frame.vertex;
            if (frame.next_edge == int(graph[vertex].size())) {
                result.tout[vertex] = ++timer;
                result.postorder.push_back(vertex);
                stack.pop_back();
                continue;
            }

            const Edge<T>& edge = graph[vertex][frame.next_edge++];
            if (!edge.alive || result.reachable(edge.to)) continue;
            result.depth[edge.to] = result.depth[vertex] + 1;
            result.parent[edge.to] = vertex;
            result.parent_edge[edge.to] = edge.id;
            result.root[edge.to] = result.root[vertex];
            result.tin[edge.to] = ++timer;
            result.preorder.push_back(edge.to);
            invoke_callback(callback, edge.to, vertex);
            stack.push_back(Frame{edge.to, 0});
        }
    };

    for (int source : sources) traverse(source);
    if (complete_forest) {
        for (int vertex = 0; vertex < n; vertex++) traverse(vertex);
    }
    return result;
}

}  // namespace dfs_detail

template <class T>
DfsResult dfs(const Graph<T>& graph, const std::vector<int>& sources) {
    auto callback = [](int) {};
    return dfs_detail::run_dfs(graph, sources, false, callback);
}

template <class T>
DfsResult dfs(const Graph<T>& graph, int source) {
    return dfs(graph, std::vector<int>{source});
}

template <class T>
DfsResult dfs(const Graph<T>& graph) {
    auto callback = [](int) {};
    return dfs_detail::run_dfs(
        graph,
        std::vector<int>(),
        true,
        callback
    );
}

template <class T, class Callback>
requires dfs_detail::DfsCallback<Callback>
DfsResult dfs(
    const Graph<T>& graph,
    const std::vector<int>& sources,
    Callback&& callback
) {
    return dfs_detail::run_dfs(graph, sources, false, callback);
}

template <class T, class Callback>
requires dfs_detail::DfsCallback<Callback>
DfsResult dfs(const Graph<T>& graph, int source, Callback&& callback) {
    return dfs(
        graph,
        std::vector<int>{source},
        std::forward<Callback>(callback)
    );
}

template <class T, class Callback>
requires dfs_detail::DfsCallback<Callback>
DfsResult dfs(const Graph<T>& graph, Callback&& callback) {
    return dfs_detail::run_dfs(
        graph,
        std::vector<int>(),
        true,
        callback
    );
}

}  // namespace graph
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

DFS
(graph/dfs.hpp)

Overview

Graph Orientation and Roots

Callback Signature

Result

Functions

Example

Depends on

Required by

Verified with

Code

DFS (graph/dfs.hpp)

Overview

Graph Orientation and Roots

Callback Signature

Result

Functions

Example

Depends on

Required by

Verified with

Code

DFS
(graph/dfs.hpp)