Here we can run DFS on the DFS tree, to detect whether there is a cycle in O(V+E) time
Since, in a tree of n vertices, we have n-1 edges, adding a cycle will create n edges.
So, there will exist a cycle of exactly n edges when we add one edge to T.
So, now time complexity of DFS becomes, O(V+V)=O(V) which will be proportional to the length of the cycle.
Now, consider an example where we have a graph and DFS produces DFS tree for it.
And DFS tree will be
Now suppose I add a edge between 1-3 in the graph and now my algorithm would be
(1)Initialize all vertices of T to white.
Start with say 1
(2) Mark this vertex 1 with GREY color.
Now, push 1 onto stack and move to it's neighbor in T
(3)If 1's neighbor has color white(undiscovered vertex), push it onto the stack, mark it grey and now discover 2's neighbors.
(4)Then, we move to 5(white), marked grey, pushed onto stack and neighbor of 5 i.e. 4(white) being examined.
(5)4 marked greyed and pushed onto the stack.
(6) No more neighbor for 4, mark 4 as black and pop off 4 from the stack.
(7)Discovered 3 as white neighbor of 5, mark it grey and now examine all neighbor of 3.
(8)Now because of new edge added in T, vertex 1 which is grey is discovered as the neighbour of 3 and 3 is also gray.
Means we have encountered a back edge!!.
Now, return all the vertices which are in the stack and those will be the vertices which make up a cycle.
Time complexity-O(V)