/**

* Definition for Directed graph.

* class DirectedGraphNode {

* int label;

* ArrayList<DirectedGraphNode> neighbors;

* DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }

* };

*/

public class Solution {

/**

* @param graph: A list of Directed graph node

* @return: Any topological order for the given graph.

*/

/* BFS */

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {

// write your code here

ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();

HashMap<DirectedGraphNode, Integer> map = new HashMap();

//Map.Entry = <Node N, # parents for N>

for (DirectedGraphNode node : graph) {

for (DirectedGraphNode neighbor : node.neighbors) {

if (map.containsKey(neighbor)) {

map.put(neighbor, map.get(neighbor) + 1);

} else {

map.put(neighbor, 1);

}

}

}

//add nodes without parents to the queue

Queue<DirectedGraphNode> q = new LinkedList<DirectedGraphNode>();

for (DirectedGraphNode node : graph) {

if (!map.containsKey(node)) {

q.offer(node);

result.add(node);

}

}

//poll a node from the queue and update # parents (-1) for its children

while (!q.isEmpty()) {

DirectedGraphNode node = q.poll();

for (DirectedGraphNode n : node.neighbors) {

map.put(n, map.get(n) - 1);

if (map.get(n) == 0) { //add nodes without parents to the queue

result.add(n);

q.offer(n);

}

}

}

return result;

}

}