/** * Definition for Directed graph. * class DirectedGraphNode { *     int label; *     ArrayList
      
        neighbors; *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList
       
        (); } * }; */public class Solution {    /**     * @param graph: A list of Directed graph node     * @return: Any topological order for the given graph.     */        public ArrayList
        
          topSort(ArrayList
         
           graph) {        // write your code here        ArrayList
          
            order = new ArrayList<>();        if (graph == null) {            return order;        }        //1.count indegree        Map
           
             indegree = getIndegree(graph); //2.bfs Queue
            
              queue = new LinkedList<>(); for (DirectedGraphNode node : graph) { if (indegree.get(node) == 0) { queue.offer(node); order.add(node); } } while (!queue.isEmpty()) { DirectedGraphNode node = queue.poll(); for (DirectedGraphNode neighbor : node.neighbors) { //node -> neighbor indegree.put(neighbor, indegree.get(neighbor) - 1); if (indegree.get(neighbor) == 0) { queue.offer(neighbor); order.add(neighbor); } } } //check 环状依赖 if (order.size() == graph.size()) { return order; } else { return null; } } private Map
             
               getIndegree(ArrayList
              
                graph) { //1.统计indegree,用map装 Map
               
                 indegree = new HashMap(); //初始化 for (DirectedGraphNode node : graph) { indegree.put(node, 0); } for (DirectedGraphNode node: graph) { for (DirectedGraphNode neighbor : node.neighbors) { //node -> neighbor indegree.put(neighbor, indegree.get(neighbor)+1); } } return indegree; }}