class FindRankingWithTopoSort :
	
    def __init__(self) :
        self.adj ={}; 

	#Add edge, Time O(1), Space O(1)
    def addEdge(self, v, w) :
        if self.adj.get(v) == None:
            self.adj[v]= []
        if self.adj.get(w) == None:
            self.adj[w]= []
        self.adj[v].append(w)

	#DFS, use stack, Time O(V+E), Space O(V), V is number of nodes, E is number of edges
    def topoSortDfs(self) : 
        stack = []; 
        visited = {};       
        for k in self.adj.keys():
            visited[k] = False; 
        for  k in self.adj.keys():  
            if visited[k] == False: 
                self.dfsHelper(k, visited, stack)
        res = []
        while len(stack) > 0: 
            res.append(stack.pop())
        return res
    
    # DFS helper, Time O(V+E), Space O(V)
    def dfsHelper(self, v, visited, stack) : 
        visited[v] = True 
        for  i in self.adj.get(v) :
            if visited[i] == False:
                self.dfsHelper(i, visited, stack);        
        stack.append(v); 


    # BFS Kahn’s algorithm, use indegree, Time O(V+E), Space O(V)
    def topoSortBfs(self) : 
        indegree = {};   
        for key in self.adj.keys():
            indegree[key] = 0
        for key in self.adj.keys(): 
            losers =  self.adj[key]; 
            for node in losers:
                indegree[node]= indegree[node]+1

        queue = [] 
        for key in self.adj.keys() :
            if indegree.get(key) == 0 :
                queue.append(key); 
              
        count = 0
        res = []
        while len(queue) != 0:  
            u = queue.pop()
            res.append(u)   
            for node in self.adj[u]: 
                indegree[node] = indegree[node]-1  #decrease indegree by 1 first
                if indegree[node] == 0: 
                    queue.append(node)
            count += 1;                    
        if count != len(self.adj):  #failed to sort
            return None           
        return res

obj = FindRankingWithTopoSort()        
obj.addEdge('P2', 'P5')
obj.addEdge('P4', 'P3')
obj.addEdge('P1', 'P5')
obj.addEdge('P3', 'P2')
obj.addEdge('P4', 'P1')

print(obj.adj)

res = obj.topoSortDfs()
print("Topological sort dfs:")
print(res)

res1 = obj.topoSortBfs()
print("Topological sort bfs:")
print(res1)