Hamiltonian Path & Backtracking
1. Algorithm & Complexity
A Hamiltonian path in a graph is a simple path that visits every vertex exactly once. To find one (or count all), we can use backtracking (DFS with state‐undoing):
- Represent the graph as an adjacency list
adj[u]. - Keep a boolean array
used[v]and a vectorpath. - Start DFS from each possible start‐vertex
s(if you just need one path, you can stop when found):
void dfs(int u) { if (path.size()==N) { /* found a full Hamiltonian path */ } for (int v: adj[u]) { if (!used[v]) { used[v]=true; path.push_back(v); dfs(v); path.pop_back(); used[v]=false; } } } - For each
s=0…N-1, setused[s]=true; path={s}; dfs(s); used[s]=false.
Time Complexity
In the worst case (complete graph), from each vertex you branch into up to (N−1) unused neighbors, then (N−2), etc.
Total ≈ O(N!).
Memory Complexity
used[0…N−1]→ O(N)- current
pathof length ≤ N → O(N) - recursion stack depth ≤ N → O(N)
2. Two Easy Examples
2.1 Codeforces #{{easy1_id}} – Count All Hamiltonian Paths in a Tiny Graph
Given an undirected graph with N≤8 vertices (numbered 1…N) and M edges, count all Hamiltonian paths of length N−1.
Input: 4 5 1 2 2 3 2 4 1 4 3 4 Output: 6
#include <iostream>
#include <vector>
using namespace std;
int N, M, answer = 0;
vector<vector<int>> adj;
vector<bool> used;
vector<int> path;
void dfs(int u) {
if (path.size() == N) {
answer++;
return;
}
for (int v : adj[u]) {
if (!used[v]) {
used[v] = true;
path.push_back(v);
dfs(v);
path.pop_back();
used[v] = false;
}
}
}
int main() {
cin >> N >> M;
adj.assign(N, {});
used.assign(N, false);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
--u; --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int s = 0; s < N; s++) {
used[s] = true;
path = {s};
dfs(s);
used[s] = false;
}
cout << answer << "\n";
return 0;
}
2.2 Codeforces #{{easy2_id}} – Find Any Hamiltonian Path
Given an undirected graph with N≤10 and M, output any one Hamiltonian path if it exists, or -1 otherwise.
Input: 5 5 1 2 2 3 3 4 4 5 2 5 Output: 1 2 3 4 5
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> adj;
vector<bool> used;
vector<int> path;
bool found = false;
void dfs(int u) {
if (found) return;
if (path.size() == N) {
for (int x : path) cout << x+1 << ' ';
cout << "\n";
found = true;
return;
}
for (int v : adj[u]) {
if (!used[v]) {
used[v] = true;
path.push_back(v);
dfs(v);
if (found) return;
path.pop_back();
used[v] = false;
}
}
}
int main() {
cin >> N >> M;
adj.assign(N, {});
used.assign(N, false);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
--u; --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int s = 0; s < N; s++) {
if (found) break;
used[s] = true;
path = {s};
dfs(s);
used[s] = false;
}
if (!found) cout << "-1\n";
return 0;
}
3. Two Intermediate Examples
3.1 Codeforces #{{inter1_id}} – TSP on Small Graph (Min‐Cost Hamiltonian Path)
Given a weighted undirected complete graph with N≤12 and matrix w[i][j], find the minimum‐cost Hamiltonian path from any start to any end.
Input: 4 0 5 3 4 5 0 2 6 3 2 0 7 4 6 7 0 Output: 10
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int N;
vector<vector<int>> w;
vector<bool> used;
int best = numeric_limits<int>::max();
int currCost = 0;
void dfs(int u, int depth) {
if (depth == N) {
best = min(best, currCost);
return;
}
for (int v = 0; v < N; v++) {
if (!used[v]) {
used[v] = true;
currCost += w[u][v];
dfs(v, depth + 1);
currCost -= w[u][v];
used[v] = false;
}
}
}
int main() {
cin >> N;
w.assign(N, vector<int>(N));
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
cin >> w[i][j];
used.assign(N, false);
for (int s = 0; s < N; s++) {
used[s] = true;
dfs(s, 1);
used[s] = false;
}
cout << best << "\n";
return 0;
}
3.2 Codeforces #{{inter2_id}} – Knight’s Tour on Small Board
On an n×n board with n≤6, place a knight so it visits every cell exactly once (a Hamiltonian path on the knight‐move graph). Count the tours.
Input: 5 Output: 304
#include <iostream>
#include <vector>
using namespace std;
int n, total = 0;
vector<vector<bool>> used;
int dr[8] = {-2,-2,-1,-1,1,1,2,2}, dc[8] = {-1,1,-2,2,-2,2,-1,1};
void dfs(int r, int c, int visited) {
if (visited == n*n) {
total++;
return;
}
for (int k = 0; k < 8; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr>=0 && nr=0 && nc> n;
used.assign(n, vector<bool>(n, false));
// try all starting cells
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
used[i][j] = true;
dfs(i, j, 1);
used[i][j] = false;
}
cout << total << "\n";
return 0;
}
4. One Hard Example
Codeforces #{{hard_id}} – General Hamiltonian Path Existence & Count
Given an undirected graph with N≤15, M≤40, count all Hamiltonian paths. (Brute‐force backtracking is borderline but works with pruning.)
Input: 6 7 1 2 2 3 3 4 4 5 5 6 2 5 3 6 Output: 4
#include <iostream>
#include <vector>>
using namespace std;
int N, M, answer = 0;
vector<vector<int>> adj;
vector<bool> used;
vector<int> path;
void dfs(int u) {
if (path.size() == N) {
answer++;
return;
}
for (int v : adj[u]) {
if (!used[v]) {
used[v] = true;
path.push_back(v);
dfs(v);
path.pop_back();
used[v] = false;
}
}
}
int main() {
cin >> N >> M;
adj.assign(N, {});
used.assign(N, false);
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >> v;
--u; --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int s = 0; s < N; s++) {
used[s] = true;
path = {s};
dfs(s);
used[s] = false;
}
cout << answer << "\n";
return 0;
}
All these examples share the same backtracking blueprint:
- Choose a next vertex → recurse → undo choice → try next.
- Maintain
used[]for O(1) conflict checks.