Vertices reachable from negative-weight cycles in Bellman-Ford
You don't need to perform DFS separately from each such vertex.  Instead, add a new fake vertex $s_0$, with an edge from $s_0$ to each vertex in a negative cycle; use DFS to find all vertices reachable from $s_0$; and set their distances to $-\infty$.  This needs only a single DFS, rather than many DFS's.  It is simple and fast; there is no hope for something that is asymptotically faster, as it takes linear time, and in the worst case, you might need to visit all vertices, taking linear time in the worst case.