class DirectedGraphNode :
    #constructor, Time O(1), Space O(1)
    def __init__(self, x):
        self.label = x 
        self.neighbors = []	

class GraphDetectCycleAndRemove :
    #constructor, Time O(1), Space O(1)
    def __init__(self) :
        self.adj = {}

    #Add nodes and edges, Time O(1), Space O(1)
    def addEdge(self, a, b): 
        if a not in self.adj:
            self.adj[a] = DirectedGraphNode(a)
        if b not in self.adj:
            self.adj[b] = DirectedGraphNode(b)
        node1 = self.adj[a]
        node2 = self.adj[b]
        node1.neighbors.append(node2); #add edge		

	# Detect whether there is cycle in graph, DFS, Time O(V+E), Space O(V)
    def detectCycle(self) :
        visited = {}
        backTrack = {}
        for k, v in self.adj.items():
            visited[k] = False
            backTrack[k] = False
        for k, v in self.adj.items() :	
            if visited[k] == False:
                if (self.cycleUtil(k, visited, backTrack)) :               
                    return True   
        return False
	
	# DFS helper, Recursion + memoization, Time O(V+E), Space O(V)
    def cycleUtil(self, v, visited, backTrack):
        if backTrack[v]: 
            return True   
        if visited[v]:
            return False	    
        visited[v] = True
        backTrack[v] = True
        for ne in self.adj[v].neighbors :
           if self.cycleUtil(ne.label, visited, backTrack):
                return True
        backTrack[v] =  False
        return False

	#Check all edges, remove one edge at a time and re-check whether the cycle is removed
	#Time O(E*(V+E)), Space O(V)
    def removeCycle(self) :
        for k, v in self.adj.items(): 
            for ne in self.adj[k].neighbors :
                self.removeEdge(k, ne.label)
                b = self.detectCycle()
                if (b == False) : #no more cycle
                    print("remove edge: " + str(k) + "," + str(ne.label))
                    return True			
                else: 
                    self.addEdge(k, ne.label); #add back
        return False

	#Remove edges, Time O(1), Space O(1)
    def removeEdge(self, a, b) :
        node1 = self.adj[a]
        node2 = self.adj[b]
        if node1 == None or node2 == None:
            return
        node1.neighbors.remove(node2)

# build directed graph with one cycle
# /*
#        1
#      > |
#     /  V
#   0 <- 2 
#        |
#        V
#        3
#  
g = GraphDetectCycleAndRemove()
g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 0)	
g.addEdge(2, 3)	

hasCycle = g.detectCycle()
print("has cycle: " + str(hasCycle))

if hasCycle:
    g.removeCycle()
hasCycle = g.detectCycle()
print("After remove, has cycle: " + str(hasCycle))