# Graph - finding cycles which contain specific edegs in O(|V| + |E|) (by DFS?)

I got this question, and I'd be happy for help.

There is a graph G=(V,E), directed graph, and F is subset of E.

I need an algorithm which find if there is a cycle composed from one (or more) of the edges in F. This must run in O(|V|+|E|).

I tried to run DFS twice: one on the original graph, and one on G'=(V,E/F), but the main problem that it not decisive about situation when in the first and the second run, I got that there is a cycle in the graph.

Any suggestions? Thank you!

-
 Do you mean a cycle? – lhf May 1 '11 at 11:43 @lhf: yes, sorry.. – Amir May 1 '11 at 11:59 Please make your titles more informative. Fewer people will answer your question if they can't tell what it's asking at a glance. – Billare May 1 '11 at 15:31 @Billare Thank you, I fixed it. – Amir May 1 '11 at 15:40

Have you learned about SCCs (Strongly-Connected Components) yet? Since your question mentions running DFS twice, perhaps you are thinking of Kosaraju's Algorithm? This algorithm finds all SCCs in $O(|V|+|E|)$.
 Thank you a lot for your help. I understood that any edge that is no in a cycle, is not in SCC. meaning - It connect bewtween two SCC's. I thoght to remove the edges in F from the graph I got (with SCC), and to count the number of the connected component's in the Graph. but there are 2 problems: The one: remove the edges taking O(E^2), the second: I don't know a method that count numbers of component's. What am i Missing? – Amir May 1 '11 at 17:24 (clarify: The number of the component's after I remove the edges in F, should be: |F|+1.) – Amir May 1 '11 at 17:28 @Amir: Kosaraju's algorithm, cited in my answer above, gives a way label each edge in $E$ with a component number telling you what SCC each edge lives in. This immediately gives you the number of components (and more). Now, if any edge of $F$ belongs in an SCC, then you know that there exists a cycle with at least one edge from $F$. Wasn't that your question? Or do you need to find a cycle composed entirely from edges in $F$? – Fixee May 1 '11 at 17:31 @Amir: Also, there is no need to remove any edges from $E$. First, mark each edge that is in $F$. Now run Kosaraju's algorithm and each time an edge is found in an SCC, check to see if it has the $F$ label. If it does, you know some cycle uses an edge from $F$. – Fixee May 1 '11 at 17:36 @Fixee: Thank you! but really the last question: mark each edge that is in F - taking O(E^2). because I need to scan F |E| times, and then E, |E| times. Am I missing something? – Amir May 1 '11 at 17:59
Hint: If $f \in F$ is an edge which is not part of a cycle, what can we say about it? Is there an easy way to find all such edges?