import java.util.*;

public class FindRankingWithTopoSort<T> {
	
	Map<T, LinkedList<T>> adj = new HashMap<>(); 
  
	//Add edge, Time O(1), Space O(1)
	public void addEdge(T v, T w) { 
    	adj.putIfAbsent(v, new LinkedList<>());
    	adj.putIfAbsent(w, new LinkedList<>());
    	adj.get(v).add(w); 
	} 
 
	//DFS, use stack, Time O(V+E), Space O(V), V is number of nodes, E is number of edges
    public List<T> topoSortDfs() { 
        Stack<T> stack = new Stack<>(); 
        Map<T, Boolean> visited = new HashMap<>();       
        for (T key: adj.keySet()) 
            visited.put(key, false); 
        for (T key: adj.keySet()) { 
            if (visited.get(key) == false) 
                dfsHelper(key, visited, stack);
        }      
        List<T> res = new ArrayList<>();
        while (stack.empty() == false) 
        	res.add(stack.pop());
        return res;	
    } 
    
    //DFS helper, Time O(V+E), Space O(V)
    private void dfsHelper(T v, Map<T, Boolean> visited, Stack<T> stack) { 
        visited.put(v, true); 
        for (T i: adj.get(v)) {
            if (!visited.get(i))
                dfsHelper(i, visited, stack); 
        } 
        stack.push(v); 
    } 
    
    //BFS Kahn’s algorithm, use indegree, Time O(V+E), Space O(V)
    public List<T> topoSortBfs() { 
        Map<T, Integer> indegree = new HashMap<>();   
        for (T key: adj.keySet())
        	indegree.put(key, 0);
        for(T key: adj.keySet()) { 
            LinkedList<T> losers =  adj.get(key); 
            for(T node : losers) { 
            	indegree.put(node, indegree.get(node)+1);
            } 
        } 
        
        Queue<T> queue = new LinkedList<T>(); 
        for(T key: adj.keySet()) { 
            if(indegree.get(key) == 0) 
                queue.add(key); 
        }        
        int count = 0; 
        List<T> res = new ArrayList<>(); 
        while(!queue.isEmpty()) { 
        	T u = queue.poll(); 
            res.add(u);
            for(T node : adj.get(u))  { 
            	indegree.put(node, indegree.get(node)-1); //decrease indegree by 1 first
                if (indegree.get(node) == 0) {
                    queue.add(node);
                }
            } 
            count++;             
        }     
        if (count != adj.keySet().size()) { //failed to sort
            return null; 
        }            
        return res;
    }
    
    public static void main(String args[])  {       
 
        FindRankingWithTopoSort<String> obj = new FindRankingWithTopoSort<>(); 
        //build adjacent list
        obj.addEdge("P2", "P5"); 
        obj.addEdge("P4", "P3"); 
        obj.addEdge("P1", "P5"); 
        obj.addEdge("P3", "P2"); 
        obj.addEdge("P4", "P1");        
        System.out.println(obj.adj); 
        
        //topo sort using dfs
        List<String> res = obj.topoSortDfs();
        System.out.println("Topological sort dfs: "+ res);

        //topo sort using bfs
        List<String> res1 = obj.topoSortBfs();
        System.out.println("Topological sort bfs: " +res1);
    } 
}