Let G = (V, E) be a weighted oriented multigraph. A vertex T ∈ V is called special if there exists at least one negative cycle that is accessible from T. Please compute the number of special vertices of G.
Input
The first line of input contains V and E.
Each of the following E lines contains a triple (x, y, w), denoting an edge x → y of weight w.
Output
A single integer — the number of special vertices of G.
Constraints
 1 ≤ V ≤ 100 000
 1 ≤ E ≤ 250 000
 1 ≤ x, y ≤ V
 10^{4} ≤ w ≤ 10^{4}
Sample
Input  Output  Explanation 

6 6 1 2 5 1 3 3 3 6 1 5 5 1 2 4 2 4 2 1  4  There are two negative cycles:

Solution by GabrielRobert Inelus
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 BellmanFord algorithm.
Hence, we can solve the problem by following the steps:
 decompose the graph into strongly connected components and build the SCC graph the same time (for example using the KosarajuSharir algorithm)
 apply the BellmanFord shortest path algorithm on each SCC and keep track of the components which have a negative cycle
 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)  BellmanFord
 O(N+M)  the modified topological sort.
Thus, the final complexity is O(N*M) due to BellmanFord. However, we all know that BellmanFord 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 BellmanFord (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^{5} vertices and 2.5 * 10^{5} edges), this solution is nondeterministic 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.