@@ -0,0 +1,2794 @@
+/**%0A * There are a total of n courses you have to take, labeled from 0 to n - 1.%0A * Some courses may have prerequisites, for example to take course 0 you have to first take course 1, %0A * which is expressed as a pair: %5B0,1%5D%0A * Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?%0A */%0Apublic class Solution %7B%0A  public static boolean canFinish(int numCourses, int%5B%5D%5B%5D prerequisites) %7B%0A    int%5B%5D courses = new int%5BnumCourses%5D;%0A    for (int i = 0; i %3C numCourses; i ++) %0A      courses%5Bi%5D = i;%0A%0A    return null != topologicalOrder(courses, prerequisites);%0A  %7D%0A%0A  public static List%3CInteger%3E topologicalOrder(int%5B%5D courses, int%5B%5D%5B%5D dep) %7B%0A    // map to represent the graph where the key is the node and the value is the list of adjacent nodes.%0A    HashMap%3CInteger, List%3CInteger%3E%3E table = new HashMap%3CInteger, List%3CInteger%3E%3E();%0A    // Hashset to keep track of duplicates.%0A    HashSet%3CInteger%3E visited = new HashSet%3CInteger%3E();%0A%0A    // Populate the map with empty lists.%0A    for (int i = 0; i %3C courses.length; i ++)%0A      table.put(courses%5Bi%5D, new ArrayList%3CInteger%3E());%0A%0A    // Iterate through the dependencies which are the edges where the second value is the start node and the first value is the end node.%0A    // For example, this dependency %5BA, B%5D is represented in the graph as node A points to node B.%0A    for (int i = 0; i %3C dep.length; i++) %7B%0A      List%3CInteger%3E list = table.get(dep%5Bi%5D%5B0%5D);%0A      list.add(dep%5Bi%5D%5B1%5D);%0A    %7D%0A%0A    // the list to return.%0A    List%3CInteger%3E order = new ArrayList%3CInteger%3E();%0A%0A    for (int i = 0; i %3C courses.length; i ++) %7B%0A      order = topologicalSort(table, visited, order, courses%5Bi%5D);%0A      if (order == null) return null;%0A    %7D%0A%0A    return order;%0A  %7D%0A%0A  private static List%3CInteger%3E topologicalSort(HashMap%3CInteger, List%3CInteger%3E%3E table, HashSet%3CInteger%3E visited, List%3CInteger%3E order, int index) %7B%0A    // If the node is in the visited set then return to prevent duplicates.%0A    if (visited.contains(index)) return order;%0A%0A    // Mark the node as visited.%0A    visited.add(index);%0A%0A    // Iterate through and call recursively for every neighbor.%0A    List%3CInteger%3E neighbors = table.get(index);%0A    for (int i = 0; i %3C neighbors.size(); i ++) %7B%0A      // Prevent duplicates%0A      int neighbor = neighbors.get(i);%0A      if (visited.contains(neighbor)) %7B%0A        // If the neighbor has already been visited but is not in the final topological order, then a cycle must exist.%0A        if (!order.contains(neighbor)) return null;%0A        continue;%0A      %7D%0A%0A      // Set order equal to the recursive call.%0A      order = topologicalSort(table, visited, order, neighbor);%0A      if (order == null) return null;%0A    %7D%0A%0A    // Add to the order list then return it.%0A    order.add(index);%0A    return order;%0A  %7D%0A%7D%0A

Add course schedule problem