Euler Circuits and Paths
The Konigsberg bridge problem asked a simple question in 1736: can you cross every bridge exactly once and return home? Euler proved you can't. Three centuries later, the same question shows up on CSES. The difference is you need to print the walk, not just say whether it exists.
The Existence Conditions
An Euler circuit visits every edge exactly once and returns to the starting node. An Euler path visits every edge exactly once but may end at a different node.
For undirected graphs:
- Euler circuit exists iff every vertex has even degree and the graph is connected (ignoring isolated nodes).
- Euler path exists iff exactly 2 vertices have odd degree. Those two vertices must be the start and end.
For directed graphs:
- Euler circuit exists iff every vertex has in-degree equal to out-degree, and the graph is strongly connected.
- Euler path exists iff exactly one vertex has out-degree = in-degree + 1 (start), exactly one has in-degree = out-degree + 1 (end), and all others are balanced.
Key insight. The conditions are purely about degrees. You don't need to search for the path to know whether one exists. Check degrees first. If the conditions fail, stop immediately.
Why Degree Conditions Work
Think about what happens when a trail passes through a vertex. It enters on one edge and leaves on another. Each pass-through consumes two edges. If a vertex has even degree, all its edges pair up perfectly. If it has odd degree, one edge is left unpaired -- that vertex must be a start or end.
A circuit has no start or end distinct from each other, so zero odd-degree vertices. A path has exactly two: the start and the end.
Hierholzer's Algorithm
Knowing a circuit exists is one thing. Finding it is another. A greedy walk that follows unused edges will get stuck -- it might miss side branches. Hierholzer's fix: when you get stuck, backtrack and splice in detours.
Algorithm (iterative with a stack):
- Push the start node onto a stack.
- While the stack is non-empty: if the top node has unused edges, follow one (mark it used, push the neighbor). Otherwise, pop the node into the result list.
- Reverse the result list.
For undirected graphs, each edge has an index. Mark the edge used from both sides when you traverse it. For directed graphs, simply advance a pointer through each node's adjacency list.
// Directed Euler circuit
vector<int> hierholzer(int start, int n, vector<vector<int>>& adj) {
vector<int> idx(n, 0);
stack<int> stk;
vector<int> circuit;
stk.push(start);
while (!stk.empty()) {
int u = stk.top();
if (idx[u] < (int)adj[u].size()) {
stk.push(adj[u][idx[u]++]);
} else {
circuit.push_back(u);
stk.pop();
}
}
reverse(circuit.begin(), circuit.end());
return circuit;
}
Gotcha. For undirected graphs, you must track which edges are used, not which nodes are visited. Two nodes might share multiple edges (multigraph). Using a
usedEdge[]array indexed by edge ID is the cleanest approach.
Full Trace
Consider this undirected graph with 4 nodes and 6 edges:
Actually, let's use a simpler example. Nodes: {0, 1, 2, 3}. Edges: 0-1 (e0), 1-2 (e1), 2-0 (e2), 0-3 (e3), 3-1 (e4). Every vertex has even degree? Degrees: 0 has 3, 1 has 3, 2 has 2, 3 has 2. Nodes 0 and 1 have odd degree, so no circuit exists. But an Euler path exists from 0 to 1 (or 1 to 0).
Let's trace from start = 0:
| Step | Stack | Action | Used Edges |
|---|---|---|---|
| 1 | [0] | 0 has edge e0 to 1. Push 1. Mark e0. | {e0} |
| 2 | [0, 1] | 1 has edge e1 to 2. Push 2. Mark e1. | {e0, e1} |
| 3 | [0, 1, 2] | 2 has edge e2 to 0. Push 0. Mark e2. | {e0, e1, e2} |
| 4 | [0, 1, 2, 0] | 0 has edge e3 to 3. Push 3. Mark e3. | {e0, e1, e2, e3} |
| 5 | [0, 1, 2, 0, 3] | 3 has edge e4 to 1. Push 1. Mark e4. | {e0, e1, e2, e3, e4} |
| 6 | [0, 1, 2, 0, 3, 1] | 1 has no unused edges. Pop 1 into result. | all used |
| 7 | [0, 1, 2, 0, 3] | 3 has no unused edges. Pop 3 into result. | |
| 8 | [0, 1, 2, 0] | 0 has no unused edges. Pop 0 into result. | |
| 9 | [0, 1, 2] | 2 has no unused edges. Pop 2 into result. | |
| 10 | [0, 1] | 1 has no unused edges. Pop 1 into result. | |
| 11 | [0] | 0 has no unused edges. Pop 0 into result. |
Result (before reverse): [1, 3, 0, 2, 1, 0]. After reverse: 0 → 1 → 2 → 0 → 3 → 1. Every edge used exactly once.
CSES Mail Delivery
Problem. You are a mailman. Given an undirected graph of \(N\) intersections and \(M\) streets, find a route that uses every street exactly once and returns to intersection 1. Print the route, or "IMPOSSIBLE".
This is a textbook Euler circuit problem on an undirected graph.
Checks before running Hierholzer's:
- Every node with edges must have even degree.
- All edges must belong to one connected component (check using DFS/BFS from node 1, ignoring isolated nodes).
If either check fails, print "IMPOSSIBLE".
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<vector<pair<int,int>>> adj(n + 1);
vector<bool> usedEdge(m, false);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
adj[a].push_back({b, i});
adj[b].push_back({a, i});
}
// Check degrees
for (int i = 1; i <= n; i++) {
if (adj[i].size() % 2 != 0) {
puts("IMPOSSIBLE");
return 0;
}
}
// Hierholzer
vector<int> idx(n + 1, 0);
stack<int> stk;
vector<int> circuit;
stk.push(1);
while (!stk.empty()) {
int u = stk.top();
if (idx[u] < (int)adj[u].size()) {
auto [v, eid] = adj[u][idx[u]++];
if (!usedEdge[eid]) {
usedEdge[eid] = true;
stk.push(v);
}
} else {
circuit.push_back(u);
stk.pop();
}
}
if ((int)circuit.size() != m + 1) {
puts("IMPOSSIBLE");
return 0;
}
reverse(circuit.begin(), circuit.end());
for (int i = 0; i < (int)circuit.size(); i++) {
printf("%d%c", circuit[i], " \n"[i + 1 == (int)circuit.size()]);
}
}
Gotcha. The circuit must contain exactly \(M + 1\) nodes (start node appears at both ends). If it doesn't, the graph wasn't connected -- some edges were never reached.
CSES Teleporters Path
Problem. Given a directed graph of \(N\) nodes and \(M\) teleporters, find a path from node 1 to node \(N\) that uses every teleporter exactly once.
This is a directed Euler path from 1 to \(N\).
Conditions for a directed Euler path from \(s\) to \(t\):
- out-degree(\(s\)) = in-degree(\(s\)) + 1
- in-degree(\(t\)) = out-degree(\(t\)) + 1
- All other nodes: in-degree = out-degree
If the conditions hold, run Hierholzer's starting from node 1. The directed version doesn't need edge IDs since each directed edge is consumed exactly once by advancing the pointer.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<vector<int>> adj(n + 1);
vector<int> in_deg(n + 1, 0), out_deg(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
adj[a].push_back(b);
out_deg[a]++;
in_deg[b]++;
}
// Check conditions
if (out_deg[1] != in_deg[1] + 1 || in_deg[n] != out_deg[n] + 1) {
puts("IMPOSSIBLE");
return 0;
}
for (int i = 2; i < n; i++) {
if (in_deg[i] != out_deg[i]) {
puts("IMPOSSIBLE");
return 0;
}
}
// Hierholzer
vector<int> idx(n + 1, 0);
stack<int> stk;
vector<int> path;
stk.push(1);
while (!stk.empty()) {
int u = stk.top();
if (idx[u] < (int)adj[u].size()) {
stk.push(adj[u][idx[u]++]);
} else {
path.push_back(u);
stk.pop();
}
}
reverse(path.begin(), path.end());
if ((int)path.size() != m + 1) {
puts("IMPOSSIBLE");
return 0;
}
for (int i = 0; i < (int)path.size(); i++) {
printf("%d%c", path[i], " \n"[i + 1 == (int)path.size()]);
}
}
Time and Space Complexity
Hierholzer's algorithm visits every edge exactly once. Each edge causes at most one push and one pop. Total time: \(O(V + E)\). Space: \(O(V + E)\) for adjacency list and stack.
This is optimal -- you must read all edges to output a path using all of them.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES Mail Delivery | cses.fi/problemset/task/1691 | Medium |
| CSES Teleporters Path | cses.fi/problemset/task/1693 | Medium |