2
$\begingroup$

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!

  • 0
    @Billare Thank you, I fixed it.2011-05-01

2 Answers 2

1

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?

  • 0
    @Fixee: Tha$n$k you a lot! you really help me2011-05-01
1

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?

  • 0
    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 answer2011-05-01