Solution of Lumber Jack and Cycles

We have to make a couple important trivial notes which count towards solving the problem:

• any cycle lies entirely inside a strongly connected component;
• given a strongly connected component, we can detect whether it contains a negative cycle using the Bellman-Ford algorithm.

Hence, we can solve the problem by following the steps:

1. decompose the graph into strongly connected components and build the SCC graph the same time (for example using the Kosaraju-Sharir algorithm)
2. apply the Bellman-Ford shortest path algorithm on each SCC and keep track of the components which have a negative cycle
3. having the DAG of the SCC's, we can run a modified topological sort using a queue. Instead of the classic algorithm (pushing into the queue all the nodes with OUT degree 0 and removing them along with any edge that is incident to them and then repeating the process while possible), we add the condition that we push into the queue only the nodes which represent a strongly connected component (nodes of SCC Graph) that have no negative cycles inside.

The worst case time complexity is:

• O(N+M) - SCC
• O(N*M) - Bellman-Ford
• O(N+M) - the modified topological sort.

Thus, the final complexity is O(N*M) due to Bellman-Ford. However, we all know that Bellman-Ford is a probabilistic algorithm; Hence, in general, it performs better than O(N * log N).

I leave as homework to the curious reader the following claims:

By using the fact that Bellman-Ford (probabilistic algorithm) usually runs faster then Dijkstra's algorithm, I claim that if there are no negative cycles in a strongly connected component of size S, each node will be pushed into the queue at most log S times. This imposes the expected O(S * log S) time complexity.

We can pick a constant c, such that log |maxS| < c = 60 and claim with a very high success rate that if a node is pushed into the queue for more than 60 times, then it is a member of a negative cycle. Even though this runs fast (less than half a second per testcase on an average computer for 10⁵ vertices and 2.5 * 10⁵ edges), this solution is non-deterministic and may fail on a smart particular test. The success rate increases as the constant gets larger and hits certainty when c = S, considering that a node that is pushed into the queue S times must be a member of a negative cycle.