Euler Path & Circuit

Quick Revisit

• USE WHEN: Must traverse every edge exactly once (reconstruct word chains, draw without lifting pen, de Bruijn sequences)
• INVARIANT: Euler circuit ⟺ every vertex has even degree (undirected) or in-degree = out-degree (directed)
• TIME: O(V + E) | SPACE: O(V + E)
• CLASSIC BUG: Not deleting/marking used edges (causes revisits), or choosing wrong start vertex for Euler path vs circuit
• PRACTICE: 05-ladder-graphs

Traverse every edge of a graph exactly once. Hierholzer's algorithm finds Euler paths and circuits in $O(V+E)$, turning an otherwise factorial search into a linear-time DFS with sub-tour splicing.

Difficulty: [Intermediate]Prerequisites: DFS. (Bridges and articulation points are not required for Hierholzer; they only matter for Fleury's algorithm or for advanced variants. See Bridges & Articulation Points once you reach Chapter 6.) CF Rating Range: 1600-2100

---

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Mastery Corner
• Further Reading

---

Intuition

You have an undirected graph with 5 nodes and 8 edges:

    0 ------- 1
    | \     / |
    |   \ /   |
    |   / \   |
    | /     \ |
    2 ------- 3
        |
        4

Edges: $(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),(2,4),(3,4)$ -- that is 8 edges total.

Question: can you walk along every edge exactly once and return to the start?

Naive approach -- try every edge ordering. You pick a start vertex, then at each step choose an unused edge. This is a search over all permutations of edges. For $E=8$, that is $8!=40320$ orderings to check. Most fail partway, but pruning doesn't change the worst case. For $E=20$, the search space is $20!\approx 2.4\times {10}^{18}$.

We are brute-forcing edge orderings, and almost every ordering is a dead end. There has to be a better way.

An Euler circuit exists iff degree conditions are satisfied and every vertex with at least one edge lies in the same connected component. Hierholzer's algorithm finds it by walking until stuck, then splicing in sub-tours from vertices that still have unused edges — all in $O(V+E)$.

The four cases beginners conflate:

Graph	Looking for a...	Local condition	Connectivity (over non-isolated vertices)
Undirected	Circuit	Every vertex has even degree	Connected
Undirected	Path	Exactly two vertices have odd degree (path's endpoints)	Connected
Directed	Circuit	$\text{in}(v)=\text{out}(v)$ for every $v$	Underlying graph connected
Directed	Path	One vertex with $\text{out}-\text{in}=+1$ (start), one with $-1$ (end), rest balanced	Underlying graph connected

Two important footnotes:

• The connectivity clause is over the vertices that have at least one edge. Isolated vertices are irrelevant.
• A circuit always exists iff the corresponding "exactly 0 odd / all balanced" condition holds. A path is the slight relaxation that adds the endpoints.

Analogy: drawing a complex figure without lifting your pen. You start tracing. When you get stuck (back at your starting point with no unused edges), you look at your path for a vertex that still has unused edges. You "lift" the pen there, draw a new loop from that vertex, then splice it into your existing path. Repeat until every edge is used.

Where the analogy breaks: you never actually lift the pen from the paper -- the splicing merges the sub-tour inline so the final path is one continuous trace.

Visual Walkthrough

We use a simpler graph to trace Hierholzer's clearly -- 4 vertices, 6 edges (all even degree, so an Euler circuit exists):

    0 -------- 1
    | \      / |
    |   \  /   |
    |    \/    |
    |    /\    |
    |  /    \  |
    | /      \ |
    2 -------- 3

Edges: $(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)$. Every vertex has degree 4 (even).

Hierholzer's uses a stack for DFS and a result list built in reverse.

Step 1. Push vertex 0 onto the stack. Pick edge $(0,1)$. Mark it used. Move to 1.

  Stack: [0, 1]     Result: []     Used: {0-1}

Step 2. From 1, pick edge $(1,2)$. Mark used. Move to 2.

  Stack: [0, 1, 2]  Result: []     Used: {0-1, 1-2}

Step 3. From 2, pick edge $(2,0)$. Mark used. Move to 0.

  Stack: [0, 1, 2, 0]  Result: []  Used: {0-1, 1-2, 0-2}

Step 4. From 0, pick edge $(0,3)$. Mark used. Move to 3.

  Stack: [0, 1, 2, 0, 3]  Result: []  Used: {0-1, 1-2, 0-2, 0-3}

Step 5. From 3, pick edge $(3,1)$. Mark used. Move to 1.

  Stack: [0, 1, 2, 0, 3, 1]  Result: []  Used: {0-1, 1-2, 0-2, 0-3, 1-3}

Step 6. From 1, no unused edges remain at 1. Stuck! Pop 1 from stack, append to result.

  Stack: [0, 1, 2, 0, 3]  Result: [1]

Step 7. Top of stack is 3. Edge $(3,2)$ is still unused. Pick it. Move to 2.

  Stack: [0, 1, 2, 0, 3, 2]  Result: [1]  Used: {all 6}

Step 8. From 2, no unused edges. Pop 2. Then pop 3 (no edges). Then pop 0, 2, 1, 0 -- all have no unused edges. Each gets appended to result.

  Stack: []  Result: [1, 2, 3, 0, 2, 1, 0]

Step 9. Reverse the result: $[0,1,2,0,3,2,1]$. This is the Euler circuit.

  Verify (6 edges, each used once):
    0->1  (edge 0-1)  *
    1->2  (edge 1-2)  *
    2->0  (edge 0-2)  *
    0->3  (edge 0-3)  *
    3->2  (edge 2-3)  *
    2->1  (edge 1-3)  *
  All 6 edges covered. Circuit complete.

Brute force: $6!=720$ orderings. Hierholzer: 9 steps visiting each edge twice (once to traverse, once to confirm exhaustion) -- $O(V+E)$.

The Invariant

+------------------------------------------------------------------+
| INVARIANT: The circuit stack holds a valid trail (no edge         |
| repeated). When we backtrack from a vertex with no remaining      |
| unused edges, that vertex is appended to the answer. The result,  |
| reversed, is a valid Euler circuit/path using every edge once.    |
+------------------------------------------------------------------+

Why does backtracking produce the right order? When a vertex has no unused edges left, all sub-tours from that vertex are already fully explored and their vertices already pushed to the result. Appending this vertex "closes" the sub-tour. Reversing at the end reconstructs the forward traversal order.

Look at Step 6 above -- vertex 1 has no unused edges. Both edges $(1,2)$ and $(1,3)$ were consumed earlier, and $(0,1)$ was the entry edge. The sub-tour through 1 is complete, so 1 is safe to place into the result.

What the Code Won't Teach You

Degree parity is the structural heart of Euler paths. Every time you enter a vertex, you must leave it. Even degree means you can always leave. Odd degree vertices break this balance -- they must be the start or end of the path. This is why exactly 0 or 2 odd-degree vertices are required (undirected).

Hierholzer's core idea is cycle-splicing, not "just DFS". A naive DFS walks until it gets stuck, producing only a partial trail. Hierholzer's insight: when you get stuck at the start vertex, some intermediate vertex still has unused edges. You restart from there, find another cycle, and splice it into the first. The stack-based implementation automates this:

  Cycle-splicing in action:

  Graph:  0 --- 1        1) DFS finds partial cycle:
          |     |           0 -> 1 -> 2 -> 3 -> 0
          3 --- 2 --- 4     (but edges 2-4, 4-6, 6-5, 5-2 unused!)
                |     |
                5 --- 6  2) Backtrack to vertex 2 (has unused edges).

                          3) DFS from 2 finds sub-tour:
                             2 -> 4 -> 6 -> 5 -> 2

                          4) Splice into original:
                             0 -> 1 -> [2 -> 4 -> 6 -> 5 -> 2] -> 3 -> 0
                                      ^^^^^^^^^^^^^^^^^
                                        spliced sub-tour

Euler != Hamiltonian -- the #1 misidentification. Euler = traverse every edge exactly once. Hamiltonian = visit every vertex exactly once. Euler paths are found in $O(V+E)$ via Hierholzer. Hamiltonian paths are NP-hard. If a problem says "visit every city exactly once" -- that is Hamiltonian, not Euler. If it says "cross every bridge exactly once" -- that is Euler.

When to Reach for This

Trigger phrases in problem statements:

• "traverse every edge exactly once" -- Euler path/circuit directly.
• "Euler path", "Euler circuit", "Eulerian" -- named directly.
• "Chinese postman problem" -- find minimum-weight walk covering all edges; reduce to Euler circuit by duplicating edges.
• "de Bruijn sequence" -- the de Bruijn graph has an Euler circuit that gives the sequence.
• "reconstruct a sequence from overlapping fragments" -- often de Bruijn / Euler path.
• "draw without lifting the pen" -- classic Euler circuit phrasing.

Counter-examples -- when this is NOT the right tool:

• "Visit every vertex exactly once" -- that is the Hamiltonian path, which is NP-hard. Euler = edges, Hamilton = vertices.
• "Minimum edges to traverse all edges" (with revisits allowed) -- this is the Chinese postman, which first checks Euler existence, then adds edges to fix odd-degree vertices. Not raw Hierholzer.
• Graph has more than 2 odd-degree vertices (undirected) -- no Euler path exists. Don't waste time trying.

Hierholzer State Snapshots

Consider this graph with two cycles sharing vertex 2 (all even degrees -> Euler circuit):

    0 --- 1        Edges (8 total):
    |     |        e0: 0-1  e1: 1-2  e2: 2-3  e3: 3-0
    3 --- 2 --- 4  e4: 2-4  e5: 4-6  e6: 6-5  e7: 5-2
          |     |
          5 --- 6  Degrees: 0->2  1->2  2->4  3->2  4->2  5->2  6->2

Snapshot 1 -- Mid-traversal (first cycle consumed, sub-tour pending):

  Step: DFS walked 0->1->2->3->0. Vertex 0 has no unused edges -> pop.
        Then vertex 3 has no unused edges -> pop.
        Now at vertex 2, which still has unused edges (e4, e7).

  Stack: [ 0, 1, 2 ]          Result (so far): [ 0, 3 ]
                 ^-- current                       reversed later

  Edge state:
    0 -X- 1       X = used
    |     |       . = unused
    3 -X- 2 ... 4
          |     |
          5 ... 6

Snapshot 2 -- The "stuck" moment (pop to result = splicing):

  After exploring from 2: stack grew to [0, 1, 2, 4, 6, 5, 2].
  Now vertex 2 (top) has no unused edges -> pop to result.

  Stack: [ 0, 1, 2, 4, 6, 5, 2 ]     Result: [ 0, 3 ]
                               ^-- no unused edges!

  Pop sequence:  2->5->6->4->2->1->0  all go to result.
  Final result:  [ 0, 3, 2, 5, 6, 4, 2, 1, 0 ]
  Reversed:        0->1->2->4->6->5->2->3->0  <- valid Euler circuit OK

  The reversal "splices" the sub-tour (2->4->6->5->2) into the
  middle of the first cycle (0->1->2->3->0) automatically.

Snapshot 3 -- Degree parity check (Euler path example):

  Different graph -- 5 nodes, 6 edges:

    A ------- B         Degree table:
    |  \      |         +--------+--------+----------+
    |    \    |         | Vertex | Degree | Parity   |
    D      \  |         +--------+--------+----------+
    |       \ |         |   A    |   3    | ODD  <-   |
    E ------- C         |   B    |   2    | even     |
                        |   C    |   3    | ODD  <-   |
  Edges: A-B, A-C,     |   D    |   2    | even     |
         A-D, B-C,     |   E    |   2    | even     |
         C-E, D-E      +--------+--------+----------+

  Exactly 2 odd-degree vertices (A and C).
  -> Euler PATH exists from A to C (or C to A).
  -> No Euler CIRCUIT (would need 0 odd-degree vertices).
  -> Start Hierholzer from A or C.

Extended Trace: 6-Node Directed Graph (Every Step)

This trace shows Hierholzer on a directed graph with 6 nodes and 8 edges -- large enough to demonstrate sub-tour splicing clearly. Compare with the simpler trace in DFS basics for how standard DFS differs from Hierholzer's backtrack-to-result approach.

  Directed graph -- 6 nodes, 8 edges:

     0 ------> 1            Degree table:
     |         |            +------+-----+----+----------+
     |         |            | Node | Out | In | Out - In |
     v         v            +------+-----+----+----------+
     3 <------ 2            |  0   |  2  |  1 |   +1  S  |
    / \        ^            |  1   |  1  |  1 |    0     |
   v   v       |            |  2   |  1  |  2 |   -1  E  |
  4 -> 5 ----> 3            |  3   |  2  |  2 |    0     |
                            |  4   |  1  |  1 |    0     |
  Edges:                    |  5   |  1  |  1 |    0     |
  e0: 0->1  e1: 1->2       +------+-----+----+----------+
  e2: 2->0  e3: 0->3       S = start (out-in = +1)
  e4: 3->4  e5: 4->5       E = end   (out-in = -1)
  e6: 5->3  e7: 3->2

  adj[0]=[1,3]  adj[1]=[2]  adj[2]=[0]
  adj[3]=[4,2]  adj[4]=[5]  adj[5]=[3]

Phase 1 -- Forward DFS (pushing to stack):

Step 1. Start at 0. Push 0, advance to adj[0][0] = 1.

  Stack: [0, 1]   Result: []   ptr: [1,0,0,0,0,0]

     0 ======> 1         ===  used edge
     |         |         ---  unused edge
     |         |
     v         v
     3 <------ 2
    / \        ^
   v   v       |
  4 -> 5 ----> 3

Step 2. At 1. Advance to adj[1][0] = 2.

  Stack: [0, 1, 2]   Result: []   ptr: [1,1,0,0,0,0]

     0 ======> 1
     |         |
     |         |
     v         v
     3 <====== 2
    / \        ^
   v   v       |
  4 -> 5 ----> 3

Step 3. At 2. Advance to adj[2][0] = 0.

  Stack: [0, 1, 2, 0]   Result: []   ptr: [1,1,1,0,0,0]

     0 ======> 1
     ^         |
     ||        |
     v         v
     3 <====== 2
    / \        ^
   v   v       |
  4 -> 5 ----> 3

Step 4. At 0 again. ptr[0]=1, advance to adj[0][1] = 3.

  Stack: [0, 1, 2, 0, 3]   Result: []   ptr: [2,1,1,0,0,0]

     0 ======> 1
     ^  \      |
     ||  \     |
     v    v    v
     3 <====== 2
    / \        ^
   v   v       |
  4 -> 5 ----> 3

Step 5. At 3. Advance to adj[3][0] = 4.

  Stack: [0, 1, 2, 0, 3, 4]   Result: []   ptr: [2,1,1,1,0,0]

Step 6. At 4. Advance to adj[4][0] = 5.

  Stack: [0, 1, 2, 0, 3, 4, 5]   Result: []   ptr: [2,1,1,1,1,0]

Step 7. At 5. Advance to adj[5][0] = 3.

  Stack: [0, 1, 2, 0, 3, 4, 5, 3]   Result: []   ptr: [2,1,1,1,1,1]

Step 8. At 3 again. ptr[3]=1, advance to adj[3][1] = 2.

  Stack: [0, 1, 2, 0, 3, 4, 5, 3, 2]   Result: []   ptr: [2,1,1,2,1,1]

     All 8 edges now consumed. Graph fully traversed:

     0 ======> 1
     ^  \      |
     ||  \     |
     v    v    v
     3 <====== 2
    / \        ^
   v   v       |
  4 -> 5 ====> 3

Phase 2 -- Backtrack (popping to result):

Every vertex on the stack now has ptr[v] == adj[v].size(). They all pop directly to result.

Step 9. v=2, no edges left. Pop to result.

  Stack: [0, 1, 2, 0, 3, 4, 5, 3]   Result: [2]

Step 10. v=3, no edges left. Pop.

  Stack: [0, 1, 2, 0, 3, 4, 5]   Result: [2, 3]

Step 11. v=5, no edges left. Pop.

  Stack: [0, 1, 2, 0, 3, 4]   Result: [2, 3, 5]

Step 12. v=4, no edges left. Pop.

  Stack: [0, 1, 2, 0, 3]   Result: [2, 3, 5, 4]

Step 13. v=3, no edges left. Pop.

  Stack: [0, 1, 2, 0]   Result: [2, 3, 5, 4, 3]

Step 14. v=0, no edges left. Pop.

  Stack: [0, 1, 2]   Result: [2, 3, 5, 4, 3, 0]

Step 15. v=2, no edges left. Pop.

  Stack: [0, 1]   Result: [2, 3, 5, 4, 3, 0, 2]

Step 16. v=1, no edges left. Pop.

  Stack: [0]   Result: [2, 3, 5, 4, 3, 0, 2, 1]

Step 17. v=0, no edges left. Pop.

  Stack: []   Result: [2, 3, 5, 4, 3, 0, 2, 1, 0]

Final. Reverse result: 0 -> 1 -> 2 -> 0 -> 3 -> 4 -> 5 -> 3 -> 2

  Verification (8 edges, each used once):
    0->1  (e0) *    0->3  (e3) *    4->5  (e5) *    3->2  (e7) *
    1->2  (e1) *    3->4  (e4) *    5->3  (e6) *    2->0  (e2) *
  All 8 edges covered. Path from 0 (start) to 2 (end). Correct!

Key observation: In this graph, the DFS consumed all edges before any vertex got stuck (no sub-tour splicing happened mid-traversal). This occurs when the graph structure funnels the DFS through all edges in one forward pass. Compare with the 8-edge two-cycle example in Hierholzer State Snapshots above, where splicing is visible.

---

C++ STL Reference

No STL function computes Euler paths directly. Building blocks:

Feature	Header	Usage	Notes
vector<vector<pair<int,int>>>	<vector>	Adjacency list: adj[v] = {(to, edge_id), ...}	Need edge IDs to mark used edges
vector<int> ptr	<vector>	Current-edge pointer per vertex	Avoids re-scanning used edges
stack<int>	<stack>	DFS stack for Hierholzer's	Or use vector<int> as stack
vector<bool> used	<vector>	Mark edges as used	Indexed by edge ID
reverse(v.begin(), v.end())	<algorithm>	Reverse the result list	Or build result with push_back and reverse at end

---

Implementation (Contest-Ready)

Version 1 -- Undirected Graph (Minimal)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    vector<vector<pair<int,int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--; v--;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    // Check existence: all even degree, or exactly 2 odd-degree vertices
    int odd = 0, start = 0;
    for (int i = 0; i < n; i++) {
        if ((int)adj[i].size() % 2 == 1) {
            odd++;
            start = i;
        }
    }
    if (odd != 0 && odd != 2) {
        puts("NO EULER PATH");
        return 0;
    }

    vector<bool> used(m, false);
    vector<int> ptr(n, 0); // current-edge pointer
    vector<int> stk, result;
    stk.push_back(start);

    while (!stk.empty()) {
        int v = stk.back();
        bool found = false;
        while (ptr[v] < (int)adj[v].size()) {
            auto [to, id] = adj[v][ptr[v]];
            ptr[v]++;
            if (!used[id]) {
                used[id] = true;
                stk.push_back(to);
                found = true;
                break;
            }
        }
        if (!found) {
            result.push_back(v);
            stk.pop_back();
        }
    }

    reverse(result.begin(), result.end());

    if ((int)result.size() != m + 1) {
        puts("DISCONNECTED");
        return 0;
    }

    for (int v : result)
        printf("%d ", v + 1);
    printf("\n");
}

Version 2 -- Directed Graph (Minimal)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    vector<vector<int>> adj(n);
    vector<int> in_deg(n, 0), out_deg(n, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--; v--;
        adj[u].push_back(v);
        out_deg[u]++;
        in_deg[v]++;
    }

    // Euler circuit: in[v] == out[v] for all v
    // Euler path:    exactly one v with out-in=1 (start),
    //                exactly one v with in-out=1 (end), rest equal
    int start_v = -1, end_v = -1;
    bool valid = true;
    for (int i = 0; i < n; i++) {
        int diff = out_deg[i] - in_deg[i];
        if (diff == 1) {
            if (start_v != -1) valid = false;
            start_v = i;
        } else if (diff == -1) {
            if (end_v != -1) valid = false;
            end_v = i;
        } else if (diff != 0) {
            valid = false;
        }
    }
    if (!valid) {
        puts("NO EULER PATH");
        return 0;
    }
    int start = (start_v != -1) ? start_v : 0;

    vector<int> ptr(n, 0);
    vector<int> stk, result;
    stk.push_back(start);

    while (!stk.empty()) {
        int v = stk.back();
        if (ptr[v] < (int)adj[v].size()) {
            stk.push_back(adj[v][ptr[v]++]);
        } else {
            result.push_back(v);
            stk.pop_back();
        }
    }

    reverse(result.begin(), result.end());

    if ((int)result.size() != m + 1) {
        puts("DISCONNECTED");
        return 0;
    }

    for (int v : result)
        printf("%d ", v + 1);
    printf("\n");
}

Version 3 -- Undirected (Explained)

Same logic as Version 1, with inline commentary on every key decision.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    // adj[v] = {(neighbor, edge_id), ...}
    // Edge IDs are essential: undirected edges live in TWO adj lists,
    // and used[id] marks both directions at once.
    vector<vector<pair<int,int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v; scanf("%d%d", &u, &v); u--; v--;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    // Existence: 0 odd-degree vertices => circuit; 2 => path; else impossible.
    int odd = 0, start = 0;
    for (int i = 0; i < n; i++)
        if ((int)adj[i].size() % 2 == 1) { odd++; start = i; }
    if (odd != 0 && odd != 2) { puts("NO EULER PATH"); return 0; }
    if (odd == 0)
        for (int i = 0; i < n; i++)
            if (!adj[i].empty()) { start = i; break; }

    vector<bool> used(m, false);
    vector<int> ptr(n, 0); // ptr[v]: next index to try in adj[v]
    // Without ptr, we rescan from 0 each time => O(V*E). With ptr => O(V+E).

    vector<int> stk, result;
    stk.push_back(start);

    while (!stk.empty()) {
        int v = stk.back();
        bool found = false;
        while (ptr[v] < (int)adj[v].size()) {
            auto [to, id] = adj[v][ptr[v]++];
            if (!used[id]) {
                used[id] = true; // marks BOTH directions
                stk.push_back(to);
                found = true;
                break;
            }
        }
        if (!found) {
            // v has no unused edges => all sub-tours from v are done.
            // Append v to result (builds answer in reverse).
            result.push_back(v);
            stk.pop_back();
        }
    }

    reverse(result.begin(), result.end()); // reverse post-order => forward path

    // Must use exactly m edges => m+1 vertices in result.
    if ((int)result.size() != m + 1) { puts("DISCONNECTED"); return 0; }

    for (int v : result) printf("%d ", v + 1);
    printf("\n");
}

Version 4 -- Directed Graph (Explained)

Same logic as Version 2, with comprehensive inline commentary. Useful as a study template -- every line explains why, not just what. For graph representation fundamentals, see adjacency list basics.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    // Directed graph: adj[u] stores only outgoing neighbors.
    // No edge IDs needed -- each directed edge lives in exactly one list,
    // so the current-edge pointer alone prevents double-traversal.
    // (Contrast with undirected, where edge IDs are mandatory.)
    vector<vector<int>> adj(n);
    vector<int> in_deg(n, 0), out_deg(n, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--; v--;
        adj[u].push_back(v);
        out_deg[u]++;
        in_deg[v]++;
    }

    // --- EXISTENCE CHECK ---
    // Euler CIRCUIT (directed): in[v] == out[v] for every vertex.
    //   Every vertex can be entered and exited the same number of times.
    // Euler PATH (directed): exactly one vertex with out - in = +1 (start),
    //   exactly one with out - in = -1 (end), all others balanced.
    //   The start vertex has one extra "departure" and the end has one
    //   extra "arrival", forming a path instead of a circuit.
    int start_v = -1, end_v = -1;
    bool valid = true;
    for (int i = 0; i < n; i++) {
        int diff = out_deg[i] - in_deg[i];
        if (diff == 1) {
            // This vertex has one more outgoing edge than incoming.
            // It must be the unique start of an Euler path.
            if (start_v != -1) valid = false; // two starts => impossible
            start_v = i;
        } else if (diff == -1) {
            // One more incoming than outgoing => unique end vertex.
            if (end_v != -1) valid = false; // two ends => impossible
            end_v = i;
        } else if (diff != 0) {
            // |diff| >= 2 => no Euler path or circuit possible.
            valid = false;
        }
    }

    // If start_v and end_v are both -1, all vertices are balanced => circuit.
    // If exactly one of them is set, degree conditions are violated.
    if ((start_v == -1) != (end_v == -1)) valid = false;
    if (!valid) {
        puts("NO EULER PATH");
        return 0;
    }

    // Pick starting vertex:
    //   - For Euler path: the vertex with out - in = +1.
    //   - For Euler circuit: any vertex that has edges.
    //     (Node 0 might be isolated -- skip it.)
    int start = start_v;
    if (start == -1) {
        // Circuit case: find any vertex with outgoing edges.
        for (int i = 0; i < n; i++) {
            if (!adj[i].empty()) { start = i; break; }
        }
    }
    if (start == -1) {
        // No edges in the graph at all.
        puts("0");
        return 0;
    }

    // --- HIERHOLZER'S ALGORITHM ---
    // ptr[v] = index of the next untried edge in adj[v].
    // This is the "current-edge pointer" that makes the algorithm O(V+E).
    // Key invariant: once ptr[v] passes an edge, we never revisit it.
    vector<int> ptr(n, 0);
    vector<int> stk, result;
    stk.push_back(start);

    while (!stk.empty()) {
        int v = stk.back();
        if (ptr[v] < (int)adj[v].size()) {
            // v still has outgoing edges to explore.
            // Take the next one and advance the pointer.
            // Push the destination onto the stack (extend the trail).
            int to = adj[v][ptr[v]++];
            stk.push_back(to);
        } else {
            // v has no more outgoing edges.
            // This means all sub-tours reachable from v are complete.
            // Append v to result (builds the path in reverse order).
            // This is the "splicing" step -- when we later pop the vertex
            // that LED to v, it may still have unused edges, restarting
            // exploration and inserting a sub-tour before v in the result.
            result.push_back(v);
            stk.pop_back();
        }
    }

    // The result was built in reverse post-order.
    // Reversing gives the correct forward traversal order.
    reverse(result.begin(), result.end());

    // --- CONNECTIVITY CHECK ---
    // Degree conditions can hold locally while the graph is disconnected.
    // Example: two separate circuits each satisfy in==out, but together
    // they don't form a single Euler circuit.
    // If we used all m edges, result has exactly m+1 vertices.
    if ((int)result.size() != m + 1) {
        puts("DISCONNECTED");
        return 0;
    }

    for (int v : result)
        printf("%d ", v + 1);
    printf("\n");
}

---

Operations Reference

Operation	Time	Space
Build adjacency list	$O(V+E)$	$O(V+E)$
Degree check (existence)	$O(V)$	$O(V)$
Hierholzer's DFS (find path/circuit)	$O(V+E)$	$O(V+E)$
Reverse result	$O(V+E)$	$O(1)$ extra
Total	$O(V+E)$	$O(V+E)$

The current-edge pointer ptr[v] is the key to $O(V+E)$. Without it, re-scanning adjacency lists degrades to $O(V\cdot E)$.

---

Problem Patterns & Tricks

Pattern 1 -- Direct Euler circuit / path

Description: Given a graph, find a path or circuit traversing every edge exactly once. Pure Hierholzer. Check degree conditions first, then run the algorithm.

Example problems:

• CSES -- Mail Delivery (undirected Euler circuit)
• CSES -- Teleporters Path (directed Euler path)

Pattern 2 -- de Bruijn sequence

Description: Find a cyclic sequence of length $k^n$ over alphabet of size $k$ where every $n$-length string appears as a substring. Construct the de Bruijn graph: nodes are $(n-1)$-length strings, edges represent $n$-length strings. Each node has in-degree = out-degree = $k$, so an Euler circuit exists.

Example: binary de Bruijn sequence for n=3.
  Nodes: {00, 01, 10, 11}
  Edge "000": 00 -> 00    Edge "001": 00 -> 01
  Edge "010": 01 -> 10    Edge "011": 01 -> 11
  Edge "100": 10 -> 00    Edge "101": 10 -> 01
  Edge "110": 11 -> 10    Edge "111": 11 -> 11

The circuit spells out the de Bruijn sequence.

Example problems:

• CF 508D -- Tanya and Password (~1700)
• LC 753 -- Cracking the Safe

Pattern 3 -- Chinese postman problem

Description: Find the shortest closed walk that traverses every edge at least once. If an Euler circuit exists, that is the answer (total weight = sum of all edges). Otherwise, pair up the odd-degree vertices with minimum-weight matchings and duplicate those path edges to make all degrees even. Then find the Euler circuit on the augmented graph. The shortest-path computation between odd-degree pairs can use Dijkstra's algorithm for non-negative weights or Bellman-Ford when negative weights are present.

Example problems:

• CF 21D -- Clever -- find minimum-cost walk covering all edges.

Pattern 4 -- Reconstruct itinerary / sequence from pairs

Description: Given a list of directed edges (e.g., flight tickets from-to), reconstruct a valid itinerary using every ticket exactly once. This is a directed Euler path. Sort adjacency lists lexicographically if "smallest lexicographic order" is required.

// Lexicographic Euler path: sort adj lists, then Hierholzer.
for (int i = 0; i < n; i++)
    sort(adj[i].begin(), adj[i].end());

Example problems:

• CF 723E -- One-Way Reform (~2100)
• LC 332 -- Reconstruct Itinerary

Pattern 5 -- Lexicographic smallest Euler path

Description: Among all Euler circuits/paths, find the lexicographically smallest. Sort each adjacency list before running Hierholzer. The greedy DFS naturally picks the lex-smallest option.

Example problems:

• CF 508D -- Tanya and Password (~1700)

---

Contest Cheat Sheet

+----------------------------------------------------------------+
|  EULER PATH / CIRCUIT  --  CHEAT SHEET                         |
+----------------------------------------------------------------+
|  EXISTENCE (undirected):                                       |
|    Circuit: every vertex has even degree                       |
|    Path:    exactly 0 or 2 vertices have odd degree            |
|  EXISTENCE (directed):                                         |
|    Circuit: in[v] == out[v] for all v                          |
|    Path:    one v with out-in=1, one with in-out=1, rest equal |
+----------------------------------------------------------------+
|  HIERHOLZER (undirected, O(V+E)):                              |
|    vector<bool> used(m);  vector<int> ptr(n,0);                |
|    stk = {start};                                              |
|    while (!stk.empty()) {                                      |
|      v = stk.back();                                           |
|      if (find unused edge from v) { used[id]=1; push(to); }   |
|      else { result.push_back(v); stk.pop_back(); }            |
|    }                                                           |
|    reverse(result);  // done                                   |
+----------------------------------------------------------------+
|  DIRECTED: no used[] needed; just advance ptr[v].              |
|  LEX ORDER: sort adj lists first.                              |
+----------------------------------------------------------------+
|  TIME: O(V + E)         SPACE: O(V + E)                       |
+----------------------------------------------------------------+

---

Gotchas & Debugging

Forgetting the existence check

Always verify degree conditions before running Hierholzer. If the conditions are not met, the algorithm still runs but produces a trail that misses edges. A common WA source.

Undirected edge double-marking

Each undirected edge appears in two adjacency lists. You must use a global used[edge_id] flag. Tracking "used" per adjacency entry leaves the reverse direction available -- the edge gets traversed twice.

Disconnected components with edges

Degree conditions can pass locally while the graph is disconnected. After Hierholzer, verify result.size() == m + 1. If not, edges in unreachable components were missed.

Current-edge pointer is critical

Without ptr[v], re-scanning adjacency lists turns $O(V+E)$ into $O(V\cdot E)$. TLE on $E=5\times {10}^5$.

Start vertex selection

• Euler circuit: any vertex with edges.
• Euler path (undirected): one of the two odd-degree vertices.
• Euler path (directed): the vertex with $\text{out}-\text{in}=1$.

Wrong start vertex => partial trail missing edges.

Other gotchas

• Isolated vertices: degree-0 vertices do not affect Euler existence. Ignore them.
• Lexicographic order: sort each adjacency list before Hierholzer; greedy selection produces lex-smallest path.
• Stack overflow: use iterative Hierholzer (explicit stack). Recursive version overflows for $E>{10}^5$.

Debugging tips

• Print degree of every vertex. Count odd-degree vertices.
• After Hierholzer, check result.size() == m + 1.
• Verify no edge ID appears twice in the traversal.
• For directed graphs, print in/out-degree arrays side by side.

Mental Traps

Trap 1: "Connected graph + all even degrees -> just run DFS"

Why it bites: Vanilla DFS traverses edges eagerly and gets stuck at the start vertex with unused edges elsewhere. It does not backtrack to splice in sub-tours.

  Example (two cycles sharing vertex 2):

    0 --- 1        DFS from 0: 0->1->2->3->0  STUCK!
    |     |        Edges 2-4, 4-5, 5-2 never visited.
    3 --- 2 --- 4
           \   /   Hierholzer: when stuck at 0, backtrack
            \ /    to 2 (unused edges), find 2->4->5->2,
             5     splice: 0->1->[2->4->5->2]->3->0  OK

Fix: Use Hierholzer's algorithm (stack-based). When current vertex has no unused edges, pop it to the result -- this is the splicing mechanism.

Trap 2: "Euler circuit problems are rare in contests"

Why it bites: They appear in disguise. You don't see "find an Euler circuit" -- you see these instead:

  Disguised Euler problems:

  +-------------------+----------------------------------+
  | Problem Type      | Hidden Euler Structure           |
  +-------------------+----------------------------------+
  | Word chains       | Letters -> nodes, words -> edges   |
  |  "cat","top","pat"| c->a->t->o->p->a->t  (letter graph)   |
  +-------------------+----------------------------------+
  | de Bruijn sequence| k-mers -> nodes, (k+1)-mers ->    |
  |  all binary 3-mers|  edges in de Bruijn graph        |
  +-------------------+----------------------------------+
  | Pen-drawing puzzle| Intersections -> nodes,           |
  |  "no lifting pen" |  line segments -> edges           |
  +-------------------+----------------------------------+

Fix: When you see "use every X exactly once", ask: can I model X as edges in a graph? If yes, it is likely an Euler path/circuit problem.

---

Self-Test

• [ ] I can state Euler circuit/path existence conditions for both undirected and directed graphs
• [ ] I can describe Hierholzer's algorithm at a high level -- the stack-based cycle-splicing approach
• [ ] I can determine the correct starting vertex for an Euler path (odd-degree vertex for undirected)
• [ ] I can distinguish Euler from Hamiltonian -- one traverses edges, the other visits nodes; P vs NP-hard
• [ ] I can name one non-obvious problem that reduces to Euler path and describe the graph construction

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Mail Delivery	CSES	Easy	Undirected Euler circuit, direct Hierholzer
2	Teleporters Path	CSES	Easy	Directed Euler path
3	Tanya and Password	CF 508D	Medium	Build de Bruijn graph from 3-char strings, find Euler path
4	Nasta Rabbara	CF 21D	Medium	Euler path existence + construction in undirected graph
5	One-Way Reform	CF 723E	Medium-Hard	Orient undirected edges, maximize SCCs via Euler circuits
6	Words	SPOJ	Easy	Check Euler path existence in letter-transition graph
7	Cracking the Safe	LC 753	Medium-Hard	de Bruijn sequence via directed Euler circuit
8	Trails and Glades	CF 209C	Medium (~1800)	Add minimum edges to make Euler circuit exist
9	Neko and Flashback	CF 1152E	Hard (~2000)	Reconstruct permutation from min/max arrays -> Euler path on value graph
10	Two Paths	CF 36E	Hard (~2200)	Decompose graph into exactly two edge-disjoint Euler paths

---

12. Mastery Corner

💡 The Aha Moment: Euler paths exist precisely when degree parity allows entering and leaving every vertex -- even degree = balance, odd degree = forced start/end. The algorithm isn't searching; it's just following the only possible path.

🏠 Real-Life Analogy: Like a mail carrier who must walk every street on their route exactly once -- the route exists only if every intersection has an even number of streets (or exactly two intersections are "endpoints").

If I Had 5 Minutes

1. Check degree parity: 0 odd = circuit, 2 odd = path, else impossible
2. For directed: in==out for all (circuit) or exactly one +1/-1 pair (path)
3. Start from odd-degree vertex (undirected) or out-in=1 vertex (directed)
4. Hierholzer: DFS with current-edge pointer, pop-to-result when stuck
5. Verify result.size() == m + 1; otherwise graph is disconnected

Pattern Fingerprint

Constraint	Technique
"Traverse every edge exactly once"	Euler path/circuit (Hierholzer)
"Use every ticket/word/fragment once"	Model as directed Euler path
All k-length substrings of alphabet	de Bruijn graph -> Euler circuit
Minimum walk covering all edges	Chinese postman -> fix odd degrees -> Euler

Rating Progression

CF Rating	What You Should Handle
1200	Check if Euler path/circuit exists (degree counting only)
1500	Implement Hierholzer for undirected graphs
1800	Directed Euler path + lexicographic ordering
2100	de Bruijn sequences, Chinese postman reduction, edge-disjoint decomposition

Before You Code Checklist

• [ ] Counted odd-degree vertices (undirected) or checked in/out balance (directed)?
• [ ] Determined correct start vertex (odd-degree or out-in=1)?
• [ ] Using edge IDs for undirected (not just neighbor tracking)?
• [ ] Using current-edge pointer ptr[v] for O(V+E) instead of O(V*E)?
• [ ] Checking result.size() == m+1 to detect disconnected graphs?

What Would You Do If...?

1. The graph has 4 odd-degree vertices? -- No Euler path exists. For Chinese postman, you'd pair them optimally and duplicate shortest paths between pairs to make all degrees even.
2. You need the lexicographically smallest Euler path? -- Sort each adjacency list before running Hierholzer. The greedy DFS with sorted neighbors naturally produces lex-smallest.
3. The graph is directed and has one node with out-in=2? -- No Euler path. The difference must be exactly 1 for one start node and -1 for one end node.

Historical Origin

Leonhard Euler solved the Königsberg Bridge Problem in 1736, proving that no walk could cross all seven bridges exactly once -- because four vertices had odd degree. This is considered the birth of graph theory. Hierholzer published his constructive algorithm posthumously in 1873.

The Mistake That Teaches

Bug: "My Hierholzer code runs but misses edges in a valid Euler circuit." Root cause: Forgetting the current-edge pointer. Without ptr[v], the inner loop rescans already-used edges from index 0 every time we revisit vertex v. On a graph with two cycles sharing a vertex, the first cycle consumes some edges, but when we return to the shared vertex, we waste time rechecking used edges -- and worse, we may accidentally skip valid unused edges if the loop logic is wrong. Fix: Always maintain ptr[v] and advance it (never reset it) as you consume edges.

Mnemonic Anchor

"Even in, even out -- Euler walks about." (All vertices need even degree for a circuit; exactly two odd ones for a path.)

When NOT to Use This

• Visiting every VERTEX once -- that's Hamiltonian path (NP-hard), not Euler
• Shortest path covering all edges with revisits -- Chinese postman problem (needs edge duplication first)
• Graph has >2 odd-degree vertices -- no Euler path exists, period
• You need to visit edges multiple times -- Euler is exactly-once; consider other models

Debug This

Bug 1: What's wrong with this undirected Hierholzer?

vector<vector<int>> adj(n);
// ... build adj ...
vector<bool> vis(n, false);  // tracking VERTEX visited, not EDGE
stack<int> stk;
stk.push(0);
while (!stk.empty()) {
    int v = stk.top();
    if (!adj[v].empty()) {
        int u = adj[v].back(); adj[v].pop_back();
        stk.push(u);
    } else {
        result.push_back(v); stk.pop();
    }
}

Answer: For undirected graphs, removing an edge from adj[v] doesn't remove it from adj[u]. The same undirected edge gets traversed twice. Must use edge IDs with a used[id] array.

Bug 2: Why does this directed Euler path give wrong results sometimes?

int start = 0;  // always start from node 0
for (int i = 0; i < n; i++)
    if (out_deg[i] - in_deg[i] == 1) start = i;
// ... Hierholzer from start ...

Answer: If no vertex has out-in==1 (pure circuit case), start remains 0. But node 0 might be isolated (no edges). Should pick any node WITH edges: for (int i = 0; i < n; i++) if (!adj[i].empty()) { start = i; break; }.

Bug 3: This code TLEs on large graphs. Why?

while (!stk.empty()) {
    int v = stk.back();
    bool found = false;
    for (int i = 0; i < adj[v].size(); i++) {  // SCAN FROM 0 EVERY TIME
        auto [to, id] = adj[v][i];
        if (!used[id]) { used[id] = true; stk.push_back(to); found = true; break; }
    }
    if (!found) { result.push_back(v); stk.pop_back(); }
}

Answer: Missing the current-edge pointer ptr[v]. The inner loop starts from index 0 every time, re-scanning already-used edges. This makes the algorithm O(V*E) instead of O(V+E). Fix: use while (ptr[v] < adj[v].size()) and increment ptr[v].

---

Further Reading

• cp-algorithms -- Finding Euler Paths -- detailed reference with Hierholzer's proof.
• Wikipedia -- Eulerian Path -- historical context and Konigsberg bridge problem.
• For prerequisite DFS concepts, see: 03-dfs-and-tree-dfs.md
• For bridge-based analysis (related connectivity), see: 02-bridges-and-articulation-points.md
• For strongly connected components in directed Euler analysis, see: 04-scc-and-2sat.md

---