= Solution
Compute any <topological sort> $(w_1,\ldots,w_n)$ using a standard algorithm, then check its consecutive entries in the <adjacency matrix>:
``
DAGHamiltonianPath(A):
order = TopologicalSort(A)
for j = 1,...,n-1:
if not A[order[j],order[j+1]]:
return "no Hamiltonian path"
return order
``
If all checks pass, the returned ordering is a <Hamiltonian path>. If a check fails but a <Hamiltonian path> existed, part (d) would force the computed <topological sort> to equal the unique path order, whose consecutive edges all exist. This contradiction proves the negative answer correct.
A standard <topological sort> scans all matrix rows and therefore takes $O(n^2)$ time with this input representation; the subsequent $n-1$ edge checks take $O(n)$. The answer is consequently \b[$O(n^2)$ time], with $O(n)$ auxiliary storage beyond the input matrix. An $O(|V|+|E|)$ bound for an <adjacency list> must not be substituted for the stipulated <adjacency matrix> bound.
Back to article page
