Why this matters when you build with AI
Route problems show up in real products: a delivery route that must cover every street, a plotter that must draw every line once, a maintenance walk through every corridor of a building. A tool asked for "a route through all edges" can return an answer that looks right and is not. A greedy walk stops at the first dead end. A search that visits rooms skips corridors. A path is printed in the wrong direction for one-way streets. A recursive function works on 1000 corridors and crashes on 200000.
Every one of these prints a list of numbers, so the output looks like a result. What catches them is a check that does not depend on the algorithm. The output must have m + 1 room numbers for m corridors, each pair of neighbours must be joined by an unused corridor, and every corridor must be used at the end. This lesson builds a correct version, checks it against a slow search, and shows what the wrong versions print in "Common mistakes".
A prompt that states the task, the limits and the checks you want:
Write C++17 code that reads an undirected multigraph with up to 200000 rooms and
200000 corridors. Self-loops (a corridor from a room to itself) and repeated corridors
are allowed. Print a walk that starts at room s and uses every corridor exactly once,
or -1 if no such walk exists. Do not use recursion. Before the search, check the
degrees. After the search, check that the walk has m + 1 rooms. Say which rooms can
be the last room of the walk.A good answer does three things. It counts the degree of each room (a self-loop adds 2), it runs an explicit stack instead of recursion, and it marks corridors as used by their number, not marks rooms. Check the answer by reading the parity test and the final length check. If the answer never looks at the degrees, or marks rooms as used, do not trust it, even when the sample passes.
Terms used
- A walk is a list of rooms where each step follows a corridor. A trail is a walk that never uses the same corridor twice.
- An Euler trail uses every edge exactly once. An Euler circuit is an Euler trail that starts and ends in the same room. The name comes from Leonhard Euler's work on the seven bridges of Königsberg.
- The degree of a room in an undirected graph is the number of corridor ends that touch it. A self-loop touches its room at two ends, so it adds 2.
- In a directed graph, the out-degree of a room is the number of one-way streets that leave it, and the in-degree is the number that enter it.
- Connected here means that all corridors lie in one piece. Rooms with no corridors do not matter.
- An adjacency list stores, for each room, the corridors that leave it.
- A stack is a list where you add and remove items only at the end. The algorithm below keeps the current walk on a stack.
- Hierholzer's algorithm builds an Euler trail or circuit. It was published by Carl Hierholzer in 1873, in the paper listed under "What is known and what I checked".
The idea: walk until stuck, then splice
Take a small building with rooms 1 to 6 and seven corridors: 1-6, 1-2, 2-3, 3-1, 1-4, 4-5 and 5-1. Room 1 has degree 5, room 6 has degree 1, and rooms 2, 3, 4 and 5 have degree 2. Two rooms have odd degree, so a walk can exist if it starts at one of them. Room 6 is a dead end with one corridor, so a walk that starts at room 1 must end at room 6.
Try the simplest idea first. Start at room 1 and keep taking a corridor you have not used. If the first corridor you take goes to room 6, you are stuck after one step with six corridors unused. A greedy walk always ends at the first dead end, so it is the first mistake this lesson covers. Running it on this building gives a walk of length 1 out of 7 corridors (the real output is in "Common mistakes").
Hierholzer's fix keeps the walk on a stack, which holds the rooms of the current walk from bottom to top. Repeat these steps:
- Look at the room on top of the stack. If it has an unused corridor, use it, and push the room at the other end.
- If the room on top has no unused corridor, pop it and write it to the output.
When this ends, the output lists the walk backwards. Reverse it.
Run this on the building, taking corridors in the order they were typed. Room 1 pushes room 6 first. Room 6 is stuck, so 6 is written. Back on room 1, the next corridor leads to room 2, then 3, then back to room 1, then to 4, then 5, then back to room 1. The last 1 is stuck, so it is written, then 5, 4, the middle 1, 3, 2 and the first 1. The output is 6 1 5 4 1 3 2 1. Reversed, it is 1 2 3 1 4 5 1 6, which uses each corridor once.
The two triangles at room 1 were spliced into the walk in the order the stack found them. Each time a room on the stack still has unused corridors, the algorithm makes a loop there and places it inside the walk. That is why the method does not need to choose corridors carefully.
When a walk exists
Undirected graph. A walk that uses every corridor exactly once and starts at room s exists if and only if two things hold:
- All corridors are in one connected piece, and room s touches that piece (unless there are no corridors at all).
- Either no room has odd degree, or exactly two rooms have odd degree and s is one of them.
Why odd degrees? Each time a walk passes through a room in the middle, it uses one corridor to come in and one to leave, so the room's degree is paired up. Only the first and the last room of the walk can have an unpaired corridor end. So the number of odd rooms is 0 (a circuit, which ends where it starts) or 2 (a path, which ends at the other odd room). The parity test is the necessary part. Hierholzer's algorithm is the part that builds the walk when the test passes.
Directed graph. A walk that uses every one-way street exactly once and starts at room s exists if and only if all streets lie in one connected piece and the out-degree minus the in-degree is:
- 0 for every room (a circuit; room s must have at least one street), or
- +1 for exactly one room, which must be s, and -1 for exactly one room, with 0 everywhere else (a path from s to the room with -1).
Any room with a different difference rules out a walk. The directed program below checks exactly these conditions.
Worked example: corridor patrol
Problem. The first line has n, m and s: n rooms numbered 1 to n, m corridors, and the start room s. Each of the next m lines has two rooms, a corridor between them. Print the rooms of a walk that starts at s and uses every corridor exactly once, as m + 1 numbers separated by spaces. Print -1 if there is no such walk. Limits: 1 to 200000 for n and m.
Input for the building above, with the patrol starting at room 1:
6 7 1
1 6
1 2
2 3
3 1
1 4
4 5
5 1Output of the program, as run here:
1 2 3 1 4 5 1 6Other walks exist for this input, so a checker must accept any valid walk, not only this one. If the patrol starts at room 2 instead, the program prints -1, because room 2 has even degree and the walk has to start at one of the two odd rooms, 1 or 6.
The program:
// corridor.cpp: walk every corridor exactly once, starting at room s.
// Input: n m s, then m lines "u v" (undirected corridors).
// Output: the room sequence of a walk with m + 1 numbers, or -1.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, s;
cin >> n >> m >> s;
vector<vector<pair<int, int>>> adj(n + 1); // (neighbour, corridor id)
vector<int> deg(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back({v, i});
adj[v].push_back({u, i});
deg[u]++;
deg[v]++;
}
// Parity check: 0 odd rooms means a circuit, 2 odd rooms means a path
// that must start at one of them.
int odd = 0;
for (int v = 1; v <= n; v++) odd += deg[v] & 1;
bool parity_ok = (odd == 0) || (odd == 2 && (deg[s] & 1));
if (!parity_ok || (m > 0 && deg[s] == 0)) {
cout << -1 << "\n";
return 0;
}
// Iterative Hierholzer: walk until stuck, output the stuck vertex,
// then continue from the vertex below it on the stack.
vector<int> ptr(n + 1, 0);
vector<char> used(m, 0);
vector<int> stk{s}, walk;
while (!stk.empty()) {
int v = stk.back();
while (ptr[v] < (int)adj[v].size() && used[adj[v][ptr[v]].second]) ptr[v]++;
if (ptr[v] < (int)adj[v].size()) {
auto [u, id] = adj[v][ptr[v]];
used[id] = 1;
stk.push_back(u);
} else {
walk.push_back(v);
stk.pop_back();
}
}
reverse(walk.begin(), walk.end());
// If some corridor was not reached (the graph is split in two), the
// walk is too short.
if ((int)walk.size() != m + 1) {
cout << -1 << "\n";
return 0;
}
for (size_t i = 0; i < walk.size(); i++)
cout << walk[i] << (i + 1 < walk.size() ? ' ' : '\n');
return 0;
}Read the code in three parts. The degree count and parity test reject most impossible inputs before any search. The loop is the splice from the previous section. The used array has one entry per corridor, and the pointer ptr[v] moves past a corridor once it is used, so each corridor is taken once in total. The last check is the length check: a graph with two separate pieces, where the start room is in one of them, produces a walk that is too short, and this catches it.
I compiled this with g++ 15.2.0 and -std=c++17 -O2, then tested it against a brute force search on 1500 random graphs with up to 5 rooms and 7 corridors (self-loops and repeated corridors included). The brute force tries every order of corridors. The program agreed on all of them: it printed -1 exactly when no walk existed, and every walk it printed was valid.
The directed case
For one-way streets, each room keeps a list of the streets that leave it, and the pointer moves past a street when it is taken. There is no used array, because each street appears only once in the list of its starting room. The parity test becomes the balance test from the previous section.
Input for a small one-way network, starting at room 3:
4 5 3
1 2
2 3
3 1
3 4
4 2// oneway.cpp: directed version. Walk every one-way street exactly once, from s.
// Input: n m s, then m lines "a b" (street from a to b).
// Output: the room sequence (m + 1 numbers), or -1.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, s;
cin >> n >> m >> s;
vector<vector<int>> out(n + 1);
vector<int> diff(n + 1, 0); // out-degree minus in-degree
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
out[a].push_back(b);
diff[a]++;
diff[b]--;
}
// A walk exists from s when at most one room has diff +1 (it must be s),
// at most one has diff -1, and no room is off by more than 1.
int plus = 0;
bool ok = true;
for (int v = 1; v <= n; v++) {
if (diff[v] == 1) plus++;
else if (diff[v] != 0 && diff[v] != -1) ok = false;
}
if (plus > 1) ok = false;
if (plus == 1 && diff[s] != 1) ok = false;
if (plus == 0 && m > 0 && out[s].empty()) ok = false;
if (!ok) {
cout << -1 << "\n";
return 0;
}
// Same splice loop as the undirected case. Each street is used once
// because the pointer moves past it when it is taken.
vector<int> ptr(n + 1, 0), stk{s}, walk;
while (!stk.empty()) {
int v = stk.back();
if (ptr[v] < (int)out[v].size()) {
stk.push_back(out[v][ptr[v]++]);
} else {
walk.push_back(v);
stk.pop_back();
}
}
// The pop order is the walk backwards for directed edges, so reverse it.
reverse(walk.begin(), walk.end());
if ((int)walk.size() != m + 1) {
cout << -1 << "\n";
return 0;
}
for (size_t i = 0; i < walk.size(); i++)
cout << walk[i] << (i + 1 < walk.size() ? ' ' : '\n');
return 0;
}Output for the input above:
3 1 2 3 4 2The walk goes 3 to 1, 1 to 2, 2 to 3, 3 to 4 and 4 to 2, which are the five streets. Room 3 has out-degree 2 and in-degree 1, so its difference is +1, and room 2 has difference -1. Starting at room 1 gives -1, because room 1 is balanced and not the start of the path.
The reverse step matters here. Without it, the pop order is 2 4 3 2 1 3 (real output of a short Python version of the same loop, run on this input), which begins at room 2 and then goes from 2 to 4, a street that does not exist.
Tree tours: flattening a tree into ranges
A rooted tree has one root, and every other vertex has one parent. A depth-first search (DFS) enters a vertex, visits its children one after another, and leaves. If you write down the step at which each vertex is entered (its entry time, tin) and the largest entry time inside its subtree (its exit time, tout), then the subtree of v is exactly the set of vertices with entry times between tin[v] and tout[v]. The subtree becomes one interval in an array.
Three facts follow, and the program uses all of them:
- The subtree of v is the array range
[tin[v], tout[v]]. A subtree sum is then a range sum, which prefix sums answer in O(1) time after an O(n) build. - u is an ancestor of v (or u equals v) exactly when
tin[u] <= tin[v] <= tout[u]. This is an O(1) test. - The exit time is the entry time of the last vertex in the subtree. When a DFS pops v, every vertex below v has been entered, so
timer - 1is the right value.
Example tree, with root 1, children listed in the input order: edges 1-2, 1-3, 2-4, 2-5, 3-6, 6-7. The values are 5, 3, 8, 1, 4, 7, 2 for rooms 1 to 7. The table below comes from a 25-line script that performs the same DFS (real output; the program itself does not print the table):
vertex tin tout
1 0 6
2 1 3
4 2 2
5 3 3
3 4 6
6 5 6
7 6 6
flattened order: 1 2 4 5 3 6 7The subtree of room 2 is the positions 1 to 3, which hold rooms 2, 4 and 5. Their values are 3, 1 and 4, so the sum is 8. The subtree of room 3 is positions 4 to 6, which hold rooms 3, 6 and 7.
The problem: the first line has n and q, then the n values, then n - 1 edges, then q queries. A query 1 v asks for the sum of the values in the subtree of v. A query 2 u v asks whether u is an ancestor of v, printing YES or NO.
// tree_tour.cpp: flatten a rooted tree (root 1) into an Euler tour.
// Input: n q, then n values a_1..a_n, then n-1 edges "u v",
// then q queries: "1 v" = sum of a over the subtree of v,
// "2 u v" = is u an ancestor of v (u counts as its own ancestor)?
// Output: one line per query.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<long long> a(n + 1);
for (int v = 1; v <= n; v++) cin >> a[v];
vector<vector<int>> adj(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Iterative DFS. tin[v] is the step when v is entered, tout[v] the
// largest tin inside v's subtree. So the subtree of v is [tin[v], tout[v]].
vector<int> tin(n + 1), tout(n + 1), parent(n + 1, 0), it(n + 1, 0), order;
vector<int> stk{1};
int timer = 0;
tin[1] = timer++;
order.push_back(1);
while (!stk.empty()) {
int v = stk.back();
if (it[v] < (int)adj[v].size()) {
int u = adj[v][it[v]++];
if (u == parent[v]) continue;
parent[u] = v;
tin[u] = timer++;
order.push_back(u);
stk.push_back(u);
} else {
tout[v] = timer - 1;
stk.pop_back();
}
}
// Prefix sums over the flattened array: pre[p] = sum of the first p values.
vector<long long> pre(n + 1, 0);
for (int p = 0; p < n; p++) pre[p + 1] = pre[p] + a[order[p]];
while (q--) {
int type;
cin >> type;
if (type == 1) {
int v;
cin >> v;
cout << pre[tout[v] + 1] - pre[tin[v]] << "\n";
} else {
int u, v;
cin >> u >> v;
bool anc = tin[u] <= tin[v] && tin[v] <= tout[u];
cout << (anc ? "YES" : "NO") << "\n";
}
}
return 0;
}Input (the example tree, five queries) and real output:
7 5
5 3 8 1 4 7 2
1 2
1 3
2 4
2 5
3 6
6 7
1 1
1 2
1 3
2 1 6
2 4 630
8
17
YES
NOThe whole tree sums to 30. Room 1 is an ancestor of room 6, but room 4 is not an ancestor of room 6, because 4 is a leaf under 2. The loop uses long long for sums, because a path of 200000 values up to 10^9 can exceed the range of a 32-bit integer. I compiled this with the same flags and tested it on 800 random trees, with values that can be negative, and every answer matched. The brute force walked parent links from one room to the root.
This is a different tour from the one in the LCA lesson, which lists each vertex again after each visit to a child so that it has 2n - 1 entries. The version here lists each vertex once, which is enough for subtree ranges. The heavy-light lesson uses the same entry times, but it visits the heavy child first.
Complexity
- Degree count and parity test: O(n + m) time.
- Hierholzer's loop: O(n + m) time. Each corridor is taken once. Each room's pointer only moves forward, so the total pointer movement is at most the total length of the adjacency lists, which is 2m for undirected corridors.
- Memory: O(n + m), for the adjacency lists, the used flags and the stack. The stack can hold up to m + 1 rooms.
- Tree tour: O(n) to build, O(1) per ancestor query, O(1) per subtree sum after the O(n) prefix sums. With changing values, the same ranges work with a Fenwick tree or a segment tree, at O(log n) per operation (covered in the heavy-light lesson).
I did not measure these programs' running time. The bounds come from counting the work in the loops. The programs were run only on small inputs and on the random tests described above.
Common mistakes
These are the mistakes this lesson's checks catch. Each one was run here, except where the text says otherwise.
- The greedy walk. A walk that takes the first unused corridor and never splices stops at a dead end. Running it on the building example (corridors in the order 1-6, 1-2, 2-3, 3-1, 1-4, 4-5, 5-1, from room 1) printed:
greedy walk: 1 6 | length 1 of 7The symptom is a walk with fewer than m + 1 rooms. The final length check in corridor.cpp is the guard against this.
-
Skipping the parity test. The splice loop always produces a list of corridors that were used, but if the degrees do not allow a walk, the list is not a walk. For the star with centre 1 and leaves 2, 3, 4 and 5 (four odd rooms), I removed the parity check from a copy of the program and ran it. It printed
1 5 4 3 2, while the real program prints-1. The length is 5, which passes the length check, but 5 and 4 are not joined by a corridor. Only a validator that checks each pair catches this, so the parity test has to stay. -
Forgetting to reverse the output. For one-way streets, the pop order is the walk backwards. Printing it without reversing gave
2 4 3 2 1 3on the directed example, which starts at the wrong room and uses a street that does not exist. -
Recursion on long paths. A recursive DFS on a path of 100000 rooms ran without error here. The same program on a path of 1000000 rooms stopped with exit code 139 (a segmentation fault, meaning the program touched memory outside its stack). This machine has an 8192 KB stack limit (
ulimit -sprints 8192). Your machine may have a different limit, so the limit is not the point. The point is that the iterative version does not depend on it. -
Degree of a self-loop. A corridor from room 3 to room 3 adds 2 to the degree of room 3, not 1, because both of its ends touch room 3. Counting it once would flip the parity of room 3. This item was not run here. The programs above add one to
deg[u]and one todeg[v], which gives 2 for a loop, and the random tests include loops.
Checklist to keep
- Count degrees before searching. A self-loop adds 2.
- Undirected: 0 odd rooms (circuit) or exactly 2 (path from one of them).
- Directed: out-degree minus in-degree is 0 everywhere, or +1 at the start and -1 at the end.
- Mark corridors as used by their number, not rooms.
- Use an explicit stack. Do not use recursion for 200000 rooms.
- Reverse the pop order before printing.
- Check that the output has m + 1 rooms, and check each pair against the corridor list before trusting the result.
Hands-on exercise
Do this on your own machine. Make a folder, save the undirected program as corridor.cpp, compile it with g++ -std=c++17 -O2 -o corridor corridor.cpp, and run it on the example. You should see 1 2 3 1 4 5 1 6.
Then write a checker. The brute force below tries every order of corridors. It is slow, but it is simple enough to trust. The validator checks a printed walk: it starts at the start room, has m + 1 rooms, and each step uses a corridor that is still unused.
def brute_exists(s, edges, directed):
"""Backtracking over edge orders: is there a walk from s using every edge once?"""
m = len(edges)
used = [False] * m
def dfs(v, cnt):
if cnt == m:
return True
for i, (a, b) in enumerate(edges):
if used[i]:
continue
if directed:
if a != v:
continue
w = b
else:
if a != v and b != v:
continue
w = b if a == v else a
used[i] = True
if dfs(w, cnt + 1):
return True
used[i] = False
return False
return dfs(s, 0)
def valid_walk(walk, s, edges, directed):
if walk[0] != s or len(walk) != len(edges) + 1:
return False
used = [False] * len(edges)
for x, y in zip(walk, walk[1:]):
found = False
for i, (a, b) in enumerate(edges):
if used[i]:
continue
if directed:
ok = (a, b) == (x, y)
else:
ok = (a, b) == (x, y) or (a, b) == (y, x)
if ok:
used[i] = True
found = True
break
if not found:
return False
return all(used)Use this prompt to get a generator and the loop that calls the program:
Write a Python script that makes 500 random undirected graphs with 1 to 5 rooms and
0 to 7 corridors. Corridors may be self-loops or repeated. For each graph and a
random start room, write the input in the format of corridor.cpp, run ./corridor
with a timeout, and compare with brute_exists. If the program prints a walk, check it
with valid_walk. If the brute force says no walk exists but the program printed a walk,
or the reverse, print the input and stop. Print a count at the end.A good answer uses subprocess.run with timeout=, never trusts -1 without the brute force agreeing, and prints the failing input in the form you would paste into the program. A weak answer only checks that the output has the right length, which misses the greedy and the missing-parity mistakes above.
Run the same loop on oneway.cpp with directed=True. Expect no mismatch lines. The count of graphs that had a walk depends on the random seed, so your count will differ from the one in this lesson's tests.
Practice problems
Practice 1. Corridors 1-2, 2-3, 3-4, 4-1 and 2-4 (n = 4, m = 5). Does a walk that uses every corridor exist from room 1? From room 2? Hint: count the odd rooms first.
Show the answer
Degrees: room 1 has 2, room 2 has 3, room 3 has 2, room 4 has 3. The odd rooms are 2 and 4. A walk from room 1 does not exist, because room 1 is not odd and there are two odd rooms. A walk from room 2 exists, and the program prints 2 1 4 3 2 4 for the start 2. Checked by the program.
Practice 2. One-way streets 1 to 2, 2 to 1, 2 to 3, 3 to 2 and 3 to 4 (n = 4, m = 5). From which rooms can a walk start? Hint: compute out-degree minus in-degree for each room.
Show the answer
Room 1 has 1 out and 1 in, so 0. Room 2 has 2 out and 2 in, so 0. Room 3 has 2 out and 1 in, so +1. Room 4 has 0 out and 1 in, so -1. The only start is room 3. The program prints 3 2 1 2 3 4 for start 3 and -1 for start 1.
Practice 3. The example tree from the tree-tour section. What is the sum of the subtree of room 6, and is room 3 an ancestor of room 7? Hint: the flattened order is 1 2 4 5 3 6 7, so the subtree of 6 is the positions after 6.
Show the answer
The subtree of room 6 is rooms 6 and 7, with values 7 and 2, so the sum is 9. Room 3 is an ancestor of room 7, so the answer is YES. Both match the program: 2 3 7 prints YES and 1 6 prints 9.
Practice 4. Find an input with 3 rooms and 3 corridors where every room has even degree, but the program prints -1. Hint: a loop that is not connected to the rest.
Show the answer
Use 3 3 1 with corridors 1-2, 2-1 and 3-3. Rooms 1 and 2 each have degree 2, and room 3 has degree 2 from its loop, so there are no odd rooms. The walk from room 1 goes 1 to 2 and back to 1, which is 3 rooms and 2 corridors, not 4 rooms. The length check then prints -1, because the loop at room 3 cannot be reached. The program prints -1.
Summary
Euler walks use every edge once, and the odd-degree count (or the balance of one-way streets) says when they exist. Hierholzer's algorithm builds one with a stack in O(n + m) time: walk until stuck, write the room, and splice in the loops. Flattening a tree with entry and exit times turns each subtree into an interval, which makes subtree sums and ancestor checks simple. Test both against a brute force on small inputs, because the wrong versions still print numbers.
What is known and what I checked
- Known: the Euler conditions and the splicing method. The method was published by Carl Hierholzer in "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren", Mathematische Annalen, 1873 (volume 6, pages 30 to 32).
- Checked here: the three programs compiled with g++ 15.2.0,
-std=c++17 -O2, and were compared with brute force on 1500 random undirected graphs, 1500 random directed graphs and 800 random trees (self-loops and repeated corridors included). The outputs printed in this lesson come from runs of these programs. The pitfall outputs come from short variants of the same code, and the stack depth test came from a separate 10-line program. - Not checked: running time on large inputs. The bounds above are counts of steps, not measurements.