content: package Topological_Sort;
  
  // Problem Statement: Topological Sort (medium)
  // LeetCode Question:
  
  import java.util.*;
  
  public class Problem_1_Topological_Sort {
      public List<Integer> sort(int vertices, int[][] edges) {
          List<Integer> sortedOrder = new ArrayList<>();
          if (vertices <= 0)
              return sortedOrder;
  
          // a. Initialize the graph
          HashMap<Integer, Integer> inDegree =
                  new HashMap<>(); // count of incoming edges for every vertex
          HashMap<Integer, List<Integer>> graph = new HashMap<>(); // adjacency list graph
          for (int i = 0; i < vertices; i++) {
              inDegree.put(i, 0);
              graph.put(i, new ArrayList<Integer>());
          }
  
          // b. Build the graph
          for (int i = 0; i < edges.length; i++) {
              int parent = edges[i][0], child = edges[i][1];
              graph.get(parent).add(child); // put the child into it's parent's list
              inDegree.put(child, inDegree.get(child) + 1); // increment child's inDegree
          }
  
          // c. Find all sources i.e., all vertices with 0 in-degrees
          Queue<Integer> sources = new LinkedList<>();
          for (Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
              if (entry.getValue() == 0)
                  sources.add(entry.getKey());
          }
  
          // d. For each source, add it to the sortedOrder and subtract one from all of its
          // children's in-degrees if a child's in-degree becomes zero, add it to sources queue
          while (!sources.isEmpty()) {
              int vertex = sources.poll();
              sortedOrder.add(vertex);
              // get the node's children to decrement their in-degrees
              List<Integer> children = graph.get(vertex);
              for (int child : children) {
                  inDegree.put(child, inDegree.get(child) - 1);
                  if (inDegree.get(child) == 0)
                      sources.add(child);
              }
          }
  
          // if topological sort is not possible as the graph has a cycle
          if (sortedOrder.size() != vertices)
              return new ArrayList<>();
  
          return sortedOrder;
      }
  
  }
  