Detecting cycle in a graph

1) If the graph is undirected: Do a DFS/BFS, if you visit a previously visited node we have a cycle.

2) In a directed graph: a) Do a DFS and mark start and finish time for each node
b) Find back edges. Each back edge (u,v) has following property: start[u] <= start[v] and finish[v]<=finish[u]

c) Back edges => cycle

Important subtleties: 1) In the condition: start[u] <= start[v] and finish[v]<=finish[u], the equality corresponds to self edges, be sure to include equality if your graph can have self edges.
2) In the implementation of DFS is non-recursive, remember that a node is marked visited when it is popped from the stack and not when it is inserted in the stack.
while(stack s is not empty)
{
         u = s.pop();
         if(visited[u] ==true)
                       continue;
         visited[u] = true;
         for all nodes v adjacent to u
                      if(v is unvisited)
                              s.push(v)
}


http://www.spoj.com/problems/EPIC1304/