finding all vertices that are a part of a simple cycle

Question

Is there a way to find all vertices that are a part of a simple cycle in a graph in a linear time?

I found a way to do it in O(|V|(|V|+|E|)) time but was wondering if there is a way to do it faster?

Answer 1

What you want to do is remove all of the Bridges (i.e. edges that disconnect a component when removed). The Wikipedia article gives a linear time algorithm for finding all of the bridges.

Once all the bridges are gone, each node is either isolated (has degree 0) or is part of a cycle. Throw out the lonely nodes, and what's left is the nodes you want.

Answer 2

Using DFS (Depth First Search), you can do in O(|V|+|E|) time. while implementing the DFS just keep the record of the vertives you had been tracking with their parent node as soon as you find child node same as parent node(meaning the completion of cycle) you can declare all the nodes from that parent till the last child as the part of some simple cycle.

Comment below if you need more explanation.