Question

Converging Maze: Maximum Weight Node​

Answer 1

Answer:

Given a node in the graph, there's a unique maximal path starting from it (since there's at most one exit from any node). It may or may not cycle.

It's easy to find the eventual cycle length starting from a node: keep following exit nodes, recording nodes in a set along the path. Stop when you either find no exit node, or you're about to visit a previously visited node. If there's no exit node there's no cycle, and otherwise you can find the cycle length by starting at the previously visited node, and re-trace the cycle. [You could also use Floyd's algorithm here which would require O(1) rather than O(N) storage, but we're going to use O(N) storage anyway in the next step].

Using this, one can find the maximum cycle in O(N) time: repeat the above algorithm for each node in the graph, but cache results (storing -1 if there's no cycle found). You have to be careful to stop the cycle-finding above if you find a previously cached result along your path, and once you've found a result for a node, you must cache the result for all nodes along the path until you find a node who's result is already cached. The size of the largest cycle is the value of the largest cached value.

This is O(N) runtime: each edge (of which there's at most N) is followed at most 3 times in the graph, and the cache is updated exactly once for each node in the graph. It's uses O(N) additional storage.

Explanation: