Unlike the shortest path problem, which can be solved in polynomial time for arbitrary graphs, the longest path problem is NP-hard and no efficient solution exists. However, a linear time solution does exist for directed acyclic graphs (DAGs).

Simply run a topological sort on the DAG (which simultaneously checks for cycles), and output ~-1~ if a cycle exists. Otherwise, loop through the sorted graph and compute distances, updating if a new greatest distance is found. If there exist multiple paths that reach the same vertex with the same distance, choose the one with the greater amount of visited vertices.

Another way to solve this problem would be to negate all edge weights and then run the Bellman-Ford algorithm on the graph, but this method would be slower due to its complexity of ~\mathcal{O}(N \times M)~.

Time complexity: ~\mathcal{O}(N + M)~