Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Find any Hamiltonian cycle in O(n^2) or similar?

Revision en1, by Hikarii, 2021-03-27 04:41:54

I've encountered a problem that wants to find any Hamiltonian cycle (it ends where it starts). The graph given has undirected edges (which is different than this problem from CSES), and the number of vertices are $$$4 * 10^3$$$. I've been doing some search online for a while now, but eventually none of the solution seems to be better than $$$O(2^n * n)$$$. Do you have any ideas? I'm glad if some (pseudo) codes are provided, if possible. Thank you.


  Rev. Lang. By When Δ Comment
en1 English Hikarii 2021-03-27 04:41:54 536 Initial revision (published)