Find cycles in directed graph

As far as I know, the best way to solve this would be with Tarjans(or Gabows or Kosaraju's --see Wikipedia link below) algorithm for finding strongly connected components of a graph. Strongly connected components and cycles are synonymous (not exactly).

To get a better idea, please see the following links:

1. Great explanation http://www.pointy-stick.com/blog/2009/02/04/finding-connectedness-directed-graphs/

2. Wikipedia on Tarjans algorithm:http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

3. A rigorous explanation: http://www.ics.uci.edu/~eppstein/161/960220.html

4. Other interesting links:
   http://discuss.joelonsoftware.com/default.asp?design.4.249152.10
   http://forums.sun.com/thread.jspa?threadID=597673
   http://coding.derkeiler.com/Archive/General/comp.theory/2004-02/0468.html

5. Similar question on SO: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph

Now, that I've given the links, let me proceed to explain (after all its good answers and not links that really make stackoverflow such a great place).

Some points to remember (Taken from link 1):
1.Two vertices, A and B, are strongly connected if there's a path from A to B and a path from B to A.

2.The set of all vertices that are strongly connected to a given vertex forms a strongly connected component of a graph.

3.Any strongly connected component with more than one vertex in it is a cycle.

4.We want to somehow collapse all the vertices in a cycle into a single node in a 'tree' (See links). Any future cycle involving vertices we've already visited gets folded into the same node. What we end up with is a tree where each node is a strongly connected component.

5.To do this is to store two extra bits of information on each node. The number of steps the depth-first search takes to reach that node and the minimum number of steps the depth-first search takes to reach any node in that node's strongly connected component (from the nodes we've seen so far).

6.As we perform a depth-first search on the main graph, we use the secondary data structure to help with the testing of whether two nodes are "the same" (in the same strongly connected component, as it turns out) and add the current node to that secondary structure correctly.

Algorithm
The question you have isn't trivial to solve. Here's how Tarjans algorithm works-

1.The first thing to know is that you have to do a DFS. I am assuming that a stack is used to implement it. The DFS has to cover all vertices in the graph.

2.Each vertex v, has to be labeled with two values, the index and the lowval. The index is simply the order in which DFS visits the node. The lowval is the minimum of the v's index and the index of the vertex that is nearest to v in the DFS. This vertex is then pushed onto the stack.

3.For each vertex accessible from v, recurse if it isn't already in the stack.

4.For a vertex v, whose lowval == index, pop off all elements on the stack upto v itself and print them as

Here are few thoughts

1) A graph can be tree if the edges of the graph are |V| - 1 where |v| is number of vertices

2) Graph should be connected.

3) Graph should not have any cycle.