Finding backedges in a graph, with special conditions.
- by Morteza M.
There is a vertex v, such that from the subtree rooted at v, there are at least two backedges to proper ancestors of v.
The problem is finding whether such backedges exist or not ( finding v is not important at all). I run DFS algorithm, I can find backedges and save them in an array. I know which backedges in this array belong to a common tree. but I have problem on matching this condition in O(E) time.
can anyone help me with that?