Chu trình Hamilton là chu trình đi qua mỗi đỉnh đúng một lần rồi quay về đỉnh đầu. Khác với Euler (qua mỗi cạnh), bài toán Hamilton là NP-khó; với n nhỏ ta giải bằng quy hoạch động bitmask dp[mask][u].
Hãy kiểm tra đồ thị vô hướng có chu trình Hamilton hay không (cần n >= 3).
Dòng đầu n m. m dòng cạnh vô hướng u v.
1 <= n <= 15; 0 <= m <= n*(n-1)/2.
In YES nếu tồn tại chu trình Hamilton, ngược lại NO.
Ví dụ:
Đầu vào:
4 4
1 2
2 3
3 4
4 1
Đầu ra:
YES
Giải thích:
Đang tải editor...