Finding all edges of an undirected graph which are in some cycle in linear time

Question

As a reduction from another problem, I am trying to deal with finding all edges which are part of some cycle in an undirected graph $G=(V,E)$ in time $O(|V|+|E|)$.

My first idea is to use DFS and search for back edges closing cycles, but then the issue is how to add all edges found to the cycle, if we just naively add all edges each time we find a cycle the algorithm might not be linear as each edge can appear in multiple cycles (a k-clique, for example).

So my current "best" approach of counting the cycles is first building the entire DFS tree, noting where back edges are present, and then traversing the tree in DFS from the root, where each time a back edge (going forward down the tree this time) is encountered, mark all edges as being part of a cycle, and if an edge is already marked break the loop.

I can prove the approach is linear, but I'm having issues proving it actually finds all edges as required. And was wandering if there is either an easier approach or a relatively simple proof that my approach works I'm missing.

Answer 1

It is not difficult to prove that an edge is a cut-edge if and only if it does not lie on a cycle. So you can find the set $E'$ of cut edges, and what you are then looking for is $E \setminus E'$.

For finding $E'$, there are several well-known linear-time algorithms. Wikipedia gives e.g., Tarjan's bridge-finding algorithm.