Get nodes that are participating in any cycle in a graph I have a problem that states the following :


  Given a cyclic graph , output for each node if the node removes all cycles in the graph.


The most trivial way to do this is using a Union-find disjoint set , and for each node , try not putting it in the Union-find disjoint set , if there are no cycles , then this node should output "Yes" , otherwise "No".

This approach would take about $\Theta(N^2)$ time and $\Theta(N)$ memory.

The problem also stated that $N \leq 1,000,000$ which would definitely get a TLE (Time Limit Exceeded) Answer on any problem.

So, my question is, What's the algorithm that would take $\Theta(N \lg N) $ or $\Theta(N)$ time and $\Theta(N)$ memory?
First use Tarjan algorithm to find all of the bridges in the graph. Then remove all of them. Remaining graph should be made of some cycles, such that all of them have at least one common vertex, otherwise we can return false for all vertices. Is possible to check this with DFS, further reasoning is easy, total running time is $O(|V|+|E|)$.