A graph is a convenient data structure to represent such things as social networks, word relations etc.
Operations on directed graphs are easy to perform if there are no cycles.
To determine if a directed graph is acyclic, we discussed a method but didn’t review the proof.
Let’s take a look at it now:
DFS ( V, E)
For each vertex v in V
       V.color=white
       V.d = nil
  Time = 0
 For each vertex v in V:
       If v.color == white:
              DFS-Visit (V, E)
     
 DFS-VISIT (V,E, u)
  time = time + 1
   u.d = time
   u.color = gray
   foreach  vertex v adjacent to u
        If v.color == white
           DFS-VISIT(V,E,v)
         Else
               If v.d  <= u.d < u.f <= v.f  throw back edge exception.
 u.color = black
time = time + 1
 u.f = time

This method is called topological sorting. Essentially this method says that
 there exists an order in which the
vertices can be listed such that if u is before v in the
list then there is no edge from u to v.This is called
"topological order". It’s easy to prove this. Consider the vertices listed in the order v1, v2, v3 … vk, … vn
This means that each successive call is to the next neighbor.
Let us traversed vk. Let w be the one adjacent to vk. Then there are two cases
W.f != nil  in this case DFS-VISIT (w) has already completed do w must have already been listed.
W.f == nil  in this case the last thing that happens is vk is printed. Therefore w would be printed before then.
Therefore when an element is printed, each element adjacent to the original element has already been printed. This is topological sorting.
We now discuss connected components . This is a way to test the bipartiteness of a graph. A bipartite graph is one that does not have an odd cycle. Here we label each vertex with a component number such that two vertices are connected if and only if they have the same component number.

The DFS for this looks like this :
for all v in V do visited(v) = 0
   c = 0
   for all v in V do {
       if (visited(v)==0) {
           DFS_VISIT(v)
           c = c+1
       }
   }

   DFS_VISIT (v) {
      visited(v) = 1
      comp(v) = c
      for all w in adj(v) do if (visited(w)==0) DFS_VISIT (w)
   }


Now we determine the bipartiteness this way
for all v in V do visited(v) = 0
   for all v in V do if (visited(v)==0) DFS_VISIT (v,0)

   DFS_VISIT (v,p) {
      visited(v) = 1
      part(v) = p
      for all w in adj(v) do {
          if (visited(w)==0) {
              DFS_VISIT (w,1-p)
          } else {
              if (part(v) == part(w)) print "graph not bipartite"
          }
      }
   }

Courtesy: Sleator notes CMU