Chapter 5 · Euler Tours and Hamilton Cycles

Hierholzer's Linear Algorithm

Build an Euler tour in O(n + m) with a stack, a pointer per vertex, and one ordering subtlety.

core
time n + m
space n + m
2 snippets
euler
DFS
construction

Read first

The existence proof in Euler Tours: When They Exist 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.

cpphierholzer.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?
}

TheoremCorrectness

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 Tours: When They Exist 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. ∎

NoteThe 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)

cpphierholzer-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 ≤ m, so on a "path-like" multigraph with m = 2 × 10⁵ 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²).

ExampleDe 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 — De Bruijn Sequences. Same code, different vertex labels.

ExampleReconstructing 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.

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 for this page

CSES 1691Mail Deliverycoredirected circuit CSES 1693Teleporters Pathcoredirected trail

ExerciseTwo constructions to write once, by hand

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.
Add one edge to the Königsberg graph so that an Eulerian trail (not tour) exists; prove two edges are needed for a tour.