This problem has another solution that is really easy to implement if you already have a method of finding strongly-connected components (SCC) in topologically sorted order. The AtCoder library has an implementation in the “scc” package.

Let’s call a vertex “good” if it satisfies the problem condition. Iterate through the SCCs in reverse topological order. If a component has more than one vertex, all its vertices are good (as there is a path from one vertex to another vertex in the component, and then back, in accordance with the definition of SCC). Otherwise the component has a single vertex \(u\). Check all its outgoing edges: if and only if any of the destination vertices are good, \(u\) is good as well. Due to the reverse topological order, all destination vertices have already been checked for goodness.

Time complexity should be \(O(N + M)\).