Euler Circuit / Path (Hierholzer)

O(n + m)

Walk that uses every EDGE exactly once (contrast Hamiltonian: every vertex, which is NP-hard). A circuit exists in an undirected graph iff every vertex has even degree and all edges sit in one component; a path allows exactly two odd-degree vertices (start and end). Hierholzer builds it in linear time; the per-vertex ptr is what keeps it linear, never rescanning used edges. Both impossibility conditions surface as the two failure returns.

// use it on

CSES: Mail Delivery ↗

Print an Eulerian circuit from post office 1, or IMPOSSIBLE. The template's two failure returns (odd degree, disconnected edges) are exactly the IMPOSSIBLE cases.

// the code

// Eulerian circuit in an undirected graph; edges as {a, b} pairs.
// Returns the vertex sequence (m+1 long), or {} if none exists.
vector<int> euler_circuit(int n, vector<array<int, 2>>& edges, int start = 0) {
    vector<vector<pair<int, int>>> adj(n);  // (neighbor, edge id)
    for (int i = 0; i < (int)edges.size(); i++) {
        adj[edges[i][0]].push_back({edges[i][1], i});
        adj[edges[i][1]].push_back({edges[i][0], i});
    }
    for (int v = 0; v < n; v++)
        if (adj[v].size() % 2) return {};  // odd degree: no circuit
    vector<int> ptr(n, 0), path, st = {start};
    vector<bool> used(edges.size(), false);
    while (!st.empty()) {
        int v = st.back();
        while (ptr[v] < (int)adj[v].size() && used[adj[v][ptr[v]].second]) ptr[v]++;
        if (ptr[v] == (int)adj[v].size()) {
            path.push_back(v);
            st.pop_back();
        } else {
            auto [to, id] = adj[v][ptr[v]];
            used[id] = true;
            st.push_back(to);
        }
    }
    if (path.size() != edges.size() + 1) return {};  // edges disconnected
    return path;
}
// Euler PATH instead: exactly two odd-degree vertices; start at one of them.
// Directed version: need indegree == outdegree everywhere (for a path: one
// vertex with out-in = 1 as start, one with in-out = 1 as end).