Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list. The first node in the order can be any node in the graph with no nodes direct to it. Find any topological order for the given graph.

Example For graph as follow:

The topological order can be: [0, 1, 2, 3, 4, 5] [0, 2, 3, 1, 5, 4] ...

/**
 * 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.
     */
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        ArrayList<DirectedGraphNode> res = new ArrayList<>();

        //第一步，找到所有有in degree的node以及对应的in degree个数，存在map里
        HashMap<DirectedGraphNode, Integer> map = new HashMap<>();
        for(DirectedGraphNode node : graph) {
            for(DirectedGraphNode neighbor : node.neighbors) {
                if(!map.containsKey(neighbor)) {
                    map.put(neighbor, 1);
                }
                else {
                    map.put(neighbor, map.get(neighbor) + 1);
                }
            }
        }

        //第二步，找到没有in degree的node，它就是整个图的起点
        Queue<DirectedGraphNode> q = new LinkedList<>();
        for(DirectedGraphNode node : graph) {
            if(!map.containsKey(node)) {
                res.add(node);
                q.offer(node);
            }
        }

        //第三步，拿到当前node处理（更新每个neighbor在map里的value：
        每当当前node有指向该neighbor，则其在map中value-1，直至变为0，再将其放入result和queue中）
        while(!q.isEmpty()) {
            DirectedGraphNode curr = q.poll();
            for(DirectedGraphNode neighbor : curr.neighbors) { //当4poll出来了这步发生什么？
                map.put(neighbor, map.get(neighbor) - 1);
                if(map.get(neighbor) == 0) {
                    res.add(neighbor);
                    q.offer(neighbor);
                }
            }
        }
        return res;
    }
}