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!

  • $\begingroup$ Do you mean a cycle? $\endgroup$ – lhf May 1 '11 at 11:43
  • $\begingroup$ @lhf: yes, sorry.. $\endgroup$ – Amir May 1 '11 at 11:59
  • $\begingroup$ Please make your titles more informative. Fewer people will answer your question if they can't tell what it's asking at a glance. $\endgroup$ – Uticensis May 1 '11 at 15:31
  • $\begingroup$ @Billare Thank you, I fixed it. $\endgroup$ – 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|)$.

If you are thinking of this algorithm, then you are on the right track. Think about what SCCs are, how they are defined, and the difference between an edge that belongs to some SCC and an edge that does not. Can an edge that is not part of any SCC be part of a cycle?

  • $\begingroup$ 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? $\endgroup$ – Amir May 1 '11 at 17:24
  • $\begingroup$ (clarify: The number of the component's after I remove the edges in F, should be: |F|+1.) $\endgroup$ – Amir May 1 '11 at 17:28
  • $\begingroup$ @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$? $\endgroup$ – Fixee May 1 '11 at 17:31
  • $\begingroup$ @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$. $\endgroup$ – Fixee May 1 '11 at 17:36
  • $\begingroup$ @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? $\endgroup$ – 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?

  • $\begingroup$ Sorry, but I dont get it. Do you mean by DFS? DfS return only if there is a cycle, or not. and in some cases, it will return the same answer $\endgroup$ – Amir May 1 '11 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.