Editorial for RGPC '17 P4 - Snow Day


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: chenj

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)


Comments

There are no comments at the moment.