Is there any way to quickly find all the edges that are part of a cycle(back edges) in an undirected/directed graph?

Question

I've got a minimum spanning tree. I add an edge to it. Surely a cycle is formed. I need to find all the edges that are part of that cycle ie., all the back edges. How quickly can that be done? My solution- For example if it's edge (1,4), add 4 to Adj(1) at all places and run dfs every time. Eg. if Adj(1) had 2,3,5, first add 4 before 2, run DFS. I'll get a back edge. Then add 4 between 2 and 3 and run dfs. I get the another back edge. Then between 3 and 5 and so on. Is there any faster way to do this?

Answer 1

In a tree you have a single (simple) route between any pair of vertices. If you are adding an edge (i,j), first find the route in the tree between i and j and then you will have your cycle - it consists of all the vertices in that route(and turns into a cycle once you add (i,j) as edge).

Answer 2

You are looking for the strongly connected components of the graph, which can be found using Tarjan's algorithm (among others).