Editing 2015 Jan Gold Problem 3 Grass Cownoisseur (section)

== Solution ==

This problem can be solved by using depth-first search (DFS), strongly connected components (SCC), and dynamic programming.

The first step is to decompose the graph into strongly connected components. SCC is a subgraph in which each node is reachable from every other node.

Create a new graph with SCCs as nodes. If there exists a path between two SCCs in the original graph, connect them in the new graph. This new graph is a Directed Acyclic Graph (DAG). Each SCC is assigned a value equal to the total value of all nodes in it.

Next, we can use dynamic programming on this DAG. Start a DFS from each node and use memoization to store and re-use previously computed results. Keep track of the maximum value of grass that can be eaten starting from each SCC. Traverse all outgoing edges from the current SCC, and for each edge going to another SCC, calculate the maximum value achievable.

The answer to the problem is the maximum total grass that can be eaten starting from each SCC.