Better algorithm for determining if a vertex is on any cycle in a graph
You can remove the vertex $u$ and all its edges, keeping a list of its neighbours.

Then you can check whether one neighbour can reach another.

Properly organized, this will explore every vertex and edge at most once. (same complexity, but without $\Delta$ repetition factor).

I let you work out the details.