// 1070: Hamiltonian Path — Backtracking
// Approach 1: Adjacency matrix backtracking (fixed start = 0)
fn hamiltonian_path(adj: &[Vec<i32>]) -> Option<Vec<usize>> {
let n = adj.len();
let mut path = vec![0usize; n];
let mut visited = vec![false; n];
path[0] = 0;
visited[0] = true;
fn solve(pos: usize, adj: &[Vec<i32>], path: &mut Vec<usize>, visited: &mut Vec<bool>) -> bool {
let n = adj.len();
if pos == n { return true; }
for v in 0..n {
if !visited[v] && adj[path[pos - 1]][v] == 1 {
path[pos] = v;
visited[v] = true;
if solve(pos + 1, adj, path, visited) { return true; }
visited[v] = false;
}
}
false
}
if solve(1, adj, &mut path, &mut visited) { Some(path) } else { None }
}
// Approach 2: Try all starting vertices
fn hamiltonian_path_any(adj: &[Vec<i32>]) -> Option<Vec<usize>> {
let n = adj.len();
for start in 0..n {
let mut path = vec![0usize; n];
let mut visited = vec![false; n];
path[0] = start;
visited[start] = true;
fn solve(pos: usize, adj: &[Vec<i32>], path: &mut Vec<usize>, visited: &mut Vec<bool>) -> bool {
let n = adj.len();
if pos == n { return true; }
for v in 0..n {
if !visited[v] && adj[path[pos - 1]][v] == 1 {
path[pos] = v;
visited[v] = true;
if solve(pos + 1, adj, path, visited) { return true; }
visited[v] = false;
}
}
false
}
if solve(1, adj, &mut path, &mut visited) {
return Some(path);
}
}
None
}
// Approach 3: Bitmask DP for Hamiltonian path existence (O(2^n * n^2))
fn hamiltonian_exists_dp(adj: &[Vec<i32>]) -> bool {
let n = adj.len();
if n == 0 { return true; }
// dp[mask][i] = can we reach node i having visited exactly the nodes in mask?
let mut dp = vec![vec![false; n]; 1 << n];
for i in 0..n {
dp[1 << i][i] = true;
}
for mask in 1..(1 << n) {
for u in 0..n {
if !dp[mask][u] { continue; }
if mask & (1 << u) == 0 { continue; }
for v in 0..n {
if mask & (1 << v) == 0 && adj[u][v] == 1 {
dp[mask | (1 << v)][v] = true;
}
}
}
}
let full = (1 << n) - 1;
(0..n).any(|i| dp[full][i])
}
fn main() {
let adj = vec![vec![0,1,1,1], vec![1,0,1,1], vec![1,1,0,1], vec![1,1,1,0]];
match hamiltonian_path(&adj) {
Some(path) => println!("Hamiltonian path: {:?}", path),
None => println!("No Hamiltonian path"),
}
println!("Exists (bitmask DP): {}", hamiltonian_exists_dp(&adj));
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_complete_graph() {
let adj = vec![vec![0,1,1,1], vec![1,0,1,1], vec![1,1,0,1], vec![1,1,1,0]];
let path = hamiltonian_path(&adj).unwrap();
assert_eq!(path.len(), 4);
}
#[test]
fn test_path_graph() {
let adj = vec![vec![0,1,0,0], vec![1,0,1,0], vec![0,1,0,1], vec![0,0,1,0]];
let path = hamiltonian_path(&adj).unwrap();
assert_eq!(path.len(), 4);
}
#[test]
fn test_any_start() {
let adj = vec![vec![0,1,1,1], vec![1,0,1,1], vec![1,1,0,1], vec![1,1,1,0]];
assert!(hamiltonian_path_any(&adj).is_some());
}
#[test]
fn test_bitmask_dp() {
let adj = vec![vec![0,1,1,1], vec![1,0,1,1], vec![1,1,0,1], vec![1,1,1,0]];
assert!(hamiltonian_exists_dp(&adj));
// Disconnected graph
let adj2 = vec![vec![0,0,0], vec![0,0,0], vec![0,0,0]];
assert!(!hamiltonian_exists_dp(&adj2));
}
}
(* 1070: Hamiltonian Path — Backtracking *)
(* Approach 1: Adjacency matrix backtracking *)
let hamiltonian_path adj =
let n = Array.length adj in
let path = Array.make n (-1) in
let visited = Array.make n false in
path.(0) <- 0;
visited.(0) <- true;
let rec solve pos =
if pos = n then true
else begin
let found = ref false in
for v = 0 to n - 1 do
if not !found && not visited.(v) && adj.(path.(pos - 1)).(v) = 1 then begin
path.(pos) <- v;
visited.(v) <- true;
if solve (pos + 1) then found := true
else begin
path.(pos) <- -1;
visited.(v) <- false
end
end
done;
!found
end
in
if solve 1 then Some (Array.to_list path) else None
(* Approach 2: Adjacency list *)
let hamiltonian_path_adj adj n =
let path = Array.make n (-1) in
let visited = Array.make n false in
path.(0) <- 0;
visited.(0) <- true;
let rec solve pos =
if pos = n then true
else begin
let found = ref false in
List.iter (fun v ->
if not !found && not visited.(v) then begin
path.(pos) <- v;
visited.(v) <- true;
if solve (pos + 1) then found := true
else begin
path.(pos) <- -1;
visited.(v) <- false
end
end
) adj.(path.(pos - 1));
!found
end
in
if solve 1 then Some (Array.to_list path) else None
(* Approach 3: Try all starting vertices *)
let hamiltonian_path_any adj =
let n = Array.length adj in
let path = Array.make n (-1) in
let visited = Array.make n false in
let rec solve pos =
if pos = n then true
else begin
let found = ref false in
for v = 0 to n - 1 do
if not !found && not visited.(v) && adj.(path.(pos - 1)).(v) = 1 then begin
path.(pos) <- v;
visited.(v) <- true;
if solve (pos + 1) then found := true
else begin
path.(pos) <- -1;
visited.(v) <- false
end
end
done;
!found
end
in
let result = ref None in
for start = 0 to n - 1 do
if !result = None then begin
Array.fill path 0 n (-1);
Array.fill visited 0 n false;
path.(0) <- start;
visited.(start) <- true;
if solve 1 then result := Some (Array.to_list path)
end
done;
!result
let () =
(* Complete graph K4 — trivially has Hamiltonian path *)
let adj = [|
[|0;1;1;1|];
[|1;0;1;1|];
[|1;1;0;1|];
[|1;1;1;0|]
|] in
(match hamiltonian_path adj with
| Some path -> assert (List.length path = 4)
| None -> assert false);
(* Path graph: 0-1-2-3 *)
let adj2 = [|
[|0;1;0;0|];
[|1;0;1;0|];
[|0;1;0;1|];
[|0;0;1;0|]
|] in
(match hamiltonian_path adj2 with
| Some path -> assert (List.length path = 4)
| None -> assert false);
(match hamiltonian_path_any adj with
| Some path -> assert (List.length path = 4)
| None -> assert false);
Printf.printf "✓ All tests passed\n"