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?