---
title: "Hierholzer's Linear Algorithm"
summary: Build an Euler tour in O(n + m) with a stack, a pointer per vertex, and one ordering subtlety.
difficulty: core
tags: [euler, DFS, construction]
time: n + m
space: n + m
prereq: [euler/euler-existence, trees/dfs]
see: [euler/debruijn, trees/euler-tour]
---

The existence proof in @euler/euler-existence was constructive ("take a cycle, splice"), but splicing naively is quadratic. Hierholzer's insight: *do the splicing implicitly* — run a DFS-like walk that never reuses an edge, and emit vertices on the way back up.

```cpp hierholzer.cpp
int n; vector<vector<pair<int,int>>> g;      // (to, edge id)
vector<char> used(m);
vector<int> ptr(n), tour;                    // ptr = "next unused edge index"
bool euler(vector<int>& out, int s, bool directed) {
    vector<int> st{s};
    while (!st.empty()) {
        int u = st.back();
        while (ptr[u] < (int)g[u].size() && used[g[u][ptr[u]].second]) ptr[u]++;
        if (ptr[u] == (int)g[u].size()) {     // u is a dead end: commit it
            out.push_back(u); st.pop_back();
        } else {
            auto [v, id] = g[u][ptr[u]++];
            used[id] = 1;
            st.push_back(v);
        }
    }
    return (int)out.size() == m + 1;          // every edge consumed?
}
```

:::theorem title="Correctness"
If the vertex list produced (read in reverse) has length $m+1$, it is an Eulerian tour of the component; combined with the degree condition of @euler/euler-existence this decides and constructs simultaneously.
:::

:::proof
Each step either consumes a previously unused edge (so at most $m$ forward steps happen) or permanently removes a vertex from the stack. When $u$ is popped, all its edges are used: the loop above guarantees it. Hence the walk never gets "stuck early" at a vertex with unused edges, which is precisely the property that makes splicing unnecessary: whenever the recursion returns to a vertex, it has already absorbed the entire subcycle found inside. Reversing the emission order undoes the DFS post-order, and a post-order of a nested-cycle walk reversed is the cycle-splicing order — the two constructions produce the same tour. ∎
:::

:::note title="The one ordering subtlety"
Output must be **reversed** (or built with `push_front`). A pure "record $u$ when you first arrive" gives a walk that is *not* an Euler tour: it is the tour of the *spine* with the subcycles interleaved wrongly. Every wrong implementation of this algorithm I have seen is exactly this off-by-one in convention.
:::

## Recursive version (the one you should write)
```cpp hierholzer-rec.cpp
void dfs(int u) {
    for (int& i = ptr[u]; i < (int)g[u].size(); ) {
        auto [v, id] = g[u][i++];
        if (used[id]) continue;
        used[id] = 1;
        dfs(v);
    }
    tour.push_back(u);
}
// call dfs(s); then reverse(tour)
```
Depth $\le m$, so on a "path-like" multigraph with $m = 2 \times 10^5$ raise the stack limit or use the iterative form above. The `for (int& i = ptr[u]; …)` reference-into-array trick is the important part: without a per-vertex pointer, each recursion restarts scanning from index 0 and the algorithm silently becomes $O(m^2)$.

:::example title="De Bruijn / lock combinations are the same call"
"Shortest string containing every length-$k$ binary word as a substring" is an Eulerian-path problem on the graph of $(k-1)$-bit states — @euler/debruijn. Same code, different vertex labels.
:::

:::example title="Reconstructing a string from its k-mers"
Given all $n$ substrings of length $k$ of an unknown string, build vertices = the $(k-1)$-prefix/suffix, edges = the $k$-mers, find an Eulerian path. Uniqueness of the answer is equivalent to the path being forced at each step — a nice pair of ideas (existence test + reconstruction) in 30 lines.
:::

:::props title="Checklist before trusting your output"
- the graph must satisfy the degree conditions — assert it, don't assume,
- isolated vertices: exclude them from the "connected" test but keep them in $n$ if the answer counts vertices,
- parallel edges: index edges, never vertices, when marking `used`,
- for the *trail* (not circuit) variant, start at the odd vertex $s$ (or at any vertex with $\deg^{+} > \deg^{-}$ when directed),
- lexicographically smallest tour: run the same algorithm with `ptr` over a **sorted** adjacency list and a max-heap emission order (`std::priority_queue` instead of the stack, per vertex) — the classic "Reconstruct Itinerary" variant.
:::

:::problems
- [[CSES 1691]] Mail Delivery | https://cses.fi/problemset/task/1691 | core | directed circuit
- [[CSES 1693]] Teleporters Path | https://cses.fi/problemset/task/1693 | core | directed trail
:::

:::exercise title="Two constructions to write once, by hand"
1. On the multigraph with edges $\{1\!-\!2, 2\!-\!3, 3\!-\!1, 1\!-\!4, 4\!-\!1\}$, run Hierholzer with a sorted adjacency list and record the exact `tour` array before reversal. Check the reversal is what makes it a valid circuit.
2. Add one edge to the Königsberg graph so that an Eulerian *trail* (not tour) exists; prove two edges are needed for a *tour*.
:::