CourseScheduleDFS.java

// This is a DFS solution, basically just like detecting if a graph has loops.
// Used a lookup table prune, with lookup, this is O(V + E), same as BFS since each node is visited once and only once
public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (numCourses <= 1 || prerequisites.length == 0 || prerequisites[0].length == 0) {
        return true;
    }

    // this is adjacency list, used a set to dedup
    Map<Integer, Set<Integer>> graph = new HashMap<>();

    for (int i = 0; i < numCourses; i++) {
        graph.put(i, new HashSet<>());
    }

    for (int i = 0; i < prerequisites.length; i++) {
        graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
    }

    Map<Integer, Boolean> lookup = new HashMap<>();

    boolean[] visited = new boolean[numCourses];
    for (int i = 0; i < numCourses; i++) {
        if (!this.explore(i, graph, visited, lookup)) {
            return false;
        }
    }
    return true;
}

// This is the DFS way to solve it, This could also generate a topological order, think about post order way
// return false if there is a loop, true if no loop
private boolean explore(int vertex, Map<Integer, Set<Integer>> graph, boolean[] visited, Map<Integer, Boolean> lookup) {
    // keeps track of if the node has been visited or not, 
    // with this lookup, it's pruning (memorization so that we don't need to re-calculate previously visited node)
    /*
           1
         /    \
       0       3  - 4
         \ 2  /

      e.g., when recursion 0 -> 1 -> 3 -> 4
                 in 2nd round, 0 -> 2 -> 3(could directly return) 

     */
    if (lookup.containsKey(vertex)) {  
        return lookup.get(vertex);
    }

    visited[vertex] = true; // keeps track of visited or not during recursion

    Set<Integer> dependencies = graph.get(vertex);
    for (Integer i : dependencies) {
        if (visited[i] || !this.explore(i, graph, visited, lookup)) {
            return false;
        }
    }
    visited[vertex] = false;
    lookup.put(vertex, true);
    return true;
}