cycleInDirectedGraph.py

# -*- coding: utf-8 -*-
"""
Created on Mon Jun 26 11:54:20 2017
http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
@author: Pratik Mishra
"""

import collections
import os
import sys

from collections import defaultdict

class Graph:
    
    def __init__(self,vertices):
        self.graph = defaultdict(list)
        self.V = vertices
    
    def addEdge(self,u,v):
        self.graph[u].append(v)
    
    def isCyclicUtil(self,v,visited,recStack):
        # current node is marked visited
        visited[v] = True
        recStack[v] = True
        
        for neighbour in self.graph[v]:
            if visited[neighbour] == False:
                if self.isCyclicUtil(neighbour, visited, recStack) == True:
                    return True
            elif recStack[neighbour] == True:
                return True
            
        recStack[v] = False
        return False

    def isCyclic(self):
        visited = [False]*self.V
        recStack = [False]*self.V
        for node in range(self.V):
            if visited[node] == False:
                if self.isCyclicUtil(node,visited,recStack) == True:
                    return True
        return False

g = Graph(4)
g.addEdge(0,1)
g.addEdge(0,2)
g.addEdge(1,2)
g.addEdge(2,0)
g.addEdge(2,3)
g.addEdge(2,2)
g.addEdge(3,3)

if g.isCyclic() == 1:
    print "Cyclic"
else:
    print "Not Cyclic"