Một đường đi Hamilton là một đường đi trong đồ thị vô hướng đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Một Chu trình Hamilton là một đường đi Hamilton sau khi đi qua tất cả các đỉnh của đồ thị thì trở về đỉnh xuất phát.
Bài toán: Cho đơn đồ thị vô hướng liên thông gồm đỉnh và cạnh, các đỉnh được đánh số từ tới và các cạnh được đánh số từ tới . Hãy tìm một chu trình Hamilton trên .
Dữ liệu vào:
Dòng đầu chứa hai số nguyên và là số đỉnh và số cạnh của ;
dòng tiếp theo, mỗi dòng chứa một cặp số cho biết một cạnh nối hai đỉnh và trong .
Dữ liệu ra:
Gồm một dòng, nếu không tồn tại chu trình Hamilton thì ghi ra , ngược lại ghi ra dãy các đỉnh trên chu trình Hamilton tìm được (theo thứ tự đi qua, đỉnh cuối trùng đỉnh đầu), hai số liên tiếp ghi cách nhau một dấu cách.
