Can a figure be drawn in one stroke, without lifting the pencil and without going over the same line twice? That is the question of whether a graph has an Eulerian path – a path that goes through every edge exactly once. The answer depends only on the degrees of the vertices, and the path itself is found by Hierholzer's algorithm.
When does it exist?
For an undirected graph in which all the edges are in one component:
| The number of vertices of odd degree | Result |
| 0 | there is an Eulerian cycle (the path returns to the starting vertex) – it starts from any vertex |
| 2 | there is an Eulerian path – it starts in one and ends in the other vertex of odd degree |
| more than 2 | it does not exist |
Why: every time we pass through a vertex, we use one incoming and one outgoing edge, so the inner vertices of the path must have an even degree. Only the start and the end can be odd.
For a directed graph: a cycle exists if for every vertex the number of incoming edges equals the number of outgoing ones; a path exists if one vertex has one more outgoing edge (the start), one has one more incoming edge (the end), and all the others are balanced.
The famous problem of the Seven Bridges of Königsberg has no solution because all four parts of the city have an odd degree.
Hierholzer's algorithm
We start from the starting vertex and go along unused edges until we get stuck. When a vertex has no more unused edges, it goes into the result and we step back – from there we may start a new "round" that is inserted into the path. The result is obtained in reverse order. Every edge is used once, so the complexity is O(n + m).
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> graph(n + 1); // (neighbour, the index of the edge)
vector<int> degree(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back({v, i});
graph[v].push_back({u, i});
degree[u]++;
degree[v]++;
}
// the start: a vertex of odd degree, if there is one; otherwise any vertex with an edge
int start = 1, oddCount = 0;
for (int v = 1; v <= n; v++) if (degree[v] > 0) { start = v; break; }
for (int v = 1; v <= n; v++)
if (degree[v] % 2 == 1) {
if (oddCount == 0) start = v;
oddCount++;
}
if (oddCount != 0 && oddCount != 2) {
cout << "DOES NOT EXIST" << endl;
return 0;
}
vector<bool> used(m, false);
vector<size_t> nextEdge(n + 1, 0); // from which edge we continue looking through the vertex's list
vector<int> stack = {start}, path;
while (!stack.empty()) {
int v = stack.back();
while (nextEdge[v] < graph[v].size() && used[graph[v][nextEdge[v]].second]) nextEdge[v]++;
if (nextEdge[v] == graph[v].size()) { // there are no more edges from v
path.push_back(v);
stack.pop_back();
} else {
auto [u, id] = graph[v][nextEdge[v]];
used[id] = true; // we cross the edge v-u
stack.push_back(u);
}
}
if ((int)path.size() != m + 1) { // not all the edges are in the same component
cout << "DOES NOT EXIST" << endl;
return 0;
}
reverse(path.begin(), path.end());
for (size_t i = 0; i < path.size(); i++) cout << path[i] << (i + 1 < path.size() ? " " : "\n");
return 0;
}
Example
Input
4 5
1 2
2 3
3 4
4 1
1 3
The vertices 1 and 3 have an odd degree (3), so the path starts in 1 and ends in 3, and it uses each of the 5 edges exactly once.
The algorithm is written with its own stack instead of recursion, because a path can have a million edges. The array nextEdge keeps how far we have got in the list of neighbours, so that the same (already used) edges are not checked again.
Note: an older version of this lesson described Fleury's algorithm. It is easier to understand, but at every step it checks whether an edge is a bridge, so it runs in O(m²) – too slow for competitions.