Feb. 21, 2014, 5:37 p.m. by Rosalind Team

Topics: Graphs

A Hamiltonian path is a path in a graph that visits each vertex exactly once. Checking whether a graph contains a Hamiltonian path is a well-known hard problem. At the same time it is easy to perform such a check if a given graph is a DAG.

Given: A positive integer $k \le 20$ and $k$ simple directed acyclic graphs in the edge list format with at most $10^3$ vertices each.

Return: For each graph, if it contains a Hamiltonian path output "1" followed by a Hamiltonian path (i.e., a list of vertices), otherwise output "-1".

2 3 3 1 2 2 3 1 3 4 3 4 3 3 2 4 1

1 1 2 3 -1

Please login to solve this problem.

Page:

Context: