Euler trails

An Euler trail uses every edge exactly once. Hierholzer’s algorithm consumes edges and builds the route on backtracking.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. For an undirected graph, nonisolated vertices must be connected.
2. Exactly zero or two vertices may have odd degree. Start at an odd vertex if two exist.
3. Walk unused edges; when stuck, append the vertex and backtrack.
4. Reverse the collected vertices. The route must contain m+1 vertices.
5. used identifies edges rather than endpoint pairs. ptr skips consumed adjacency entries in linear total work. Backtracking appends vertices in reverse order; the final length check also rejects disconnected nonempty edge components.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<vector<pair<int,int>>>g(n+1);
    for(int id=0;id<m;id++){
        int a,b;
        cin>>a>>b;
        g[a].push_back({b,id});
        g[b].push_back({a,id});
    }
    int start=1;
    vector<int>odd;
    for(int vertex=1;vertex<=n;vertex++){
        if(!g[vertex].empty()){
            start=vertex;
        }
        if(g[vertex].size()%2==1){
            odd.push_back(vertex);
        }
    }
    if(odd.size()!=0&&odd.size()!=2){
        cout<<"NO TRAIL\n";
        return 0;
    }
    if(odd.size()==2){
        start=odd[0];
    }
    else{
        for(int vertex=1;vertex<=n;vertex++){
            if(!g[vertex].empty()){
                start=vertex;
                break;
            }
        }
    }
    // Undirected g stores (neighbor, unique edge id); start chosen by degrees.
    vector<bool>used(m);
    vector<int>ptr(n+1),trail;
    stack<int>st;
    st.push(start);
    while(!st.empty()){
        int v=st.top();
        while(ptr[v]<(int)g[v].size()&&used[g[v][ptr[v]].second]){
            ++ptr[v];
        }
        if(ptr[v]==(int)g[v].size()){
            trail.push_back(v);
            st.pop();
        }
        else{
            auto[u,id]=g[v][ptr[v]++];
            used[id]=true;
            st.push(u);
        }
    }
    reverse(trail.begin(),trail.end());
    // Reject unless degree conditions hold and trail.size()==m+1.
    if(trail.size()!=(size_t)m+1){
        cout<<"NO TRAIL\n";
        return 0;
    }
    for(int i=0;i<(int)trail.size();i++){
        if(i>0){
            cout<<' ';
        }
        cout<<trail[i];
    }
    cout<<'\n';
}

Complexity analysis

O(V + E) time and space.

Example input and output

Read n m and m undirected edges (n≥1). Print an Euler trail using every edge exactly once, or NO TRAIL. Parallel edges and self-loops are supported. For m=0 the one-vertex trail 1 is valid.

Input

3 3
1 2
2 3
3 1

Output

1 2 3 1

Every degree is even, so starting at 1 produces an Euler circuit. Each edge is consumed once by its ID.

Practical applications

Use Hierholzer for edge-covering routes, Euler circuits, and constructions that must use each connection exactly once.

Check your understanding

How many odd-degree vertices can an undirected Euler trail have?

Put it into practice

Find a route that crosses every road exactly once.