# 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|)$.
• @mohammedessam, I think the hard part is tarjan algorithm, and we cannot expect to someone think about it without knowing that algorithm, but for the rest let think together, if the resulted graph ($G'$) is cycle then is clear, otherwise there should be a node of degree at least three, you can contract all vertices of degree two in $G'$ to make $G"$, then the $G"$ is either made of at most three vertex or more (with possibly parallel edges), in the second case we can return false (for all vertices except for some special vertices, for example if connected to all others)(why?). – user742 Jun 20 '13 at 12:17