Eulerian path (Hierholzer's algorithm)

O(E)

Chain edges so each arrival is the next departure, using every edge exactly once. A plain greedy walk can strand unused edges at a dead end, so Hierholzer's algorithm walks forward until stuck, records the dead end, and backs up to close the rest.

Signals

use every edge exactly oncereconstruct an itinerary from ticketsone-stroke drawing / draw without lifting the penwalk every road/domino exactly onceflights or dominoes must chain into one trip

Template

function eulerianPath(tickets, start) {
    const adj = {};
    for (const [from, to] of tickets) {
        (adj[from] ||= []).push(to);
    }
    for (const from in adj) adj[from].sort().reverse(); // pop smallest first
    const route = [];
    const stack = [start];
    while (stack.length) {
        const node = stack[stack.length - 1];
        if (adj[node] && adj[node].length) {
            stack.push(adj[node].pop());
        } else {
            route.push(stack.pop()); // dead end: record and back up
        }
    }
    return route.reverse();
}

Looks similar, isn't

Graph BFS / DFS: An Eulerian path must use every EDGE exactly once (Hierholzer's algorithm), while BFS/DFS visits every NODE once and does not care how many times an edge gets used.

E up to ~1e5 tickets/edges, must use every edge exactly once -> O(E): Hierholzer's post-order backtracking visits each edge once.

Learn this pattern