LeetCode

Course Schedule II

Observation: this problem is equivalent to finding a reverse topological sort of the course prerequisite graph (if it exists). A valid course order will exist if the course prerequisite graph is acyclic.

Approach 1: Modify DFS to Find a Reverse Topological Sort ⭐⭐

Our algorithm consists of two parts:

1. Store the graph as an adjacency list (each prerequisite pair is a directed edge). This will improve runtime.
2. Use a modified version of DFS to find a reverse topological sort of the graph if it is acyclic.

In Approach 1 for Course Schedule, we saw how to modify DFS to determine if a graph is acyclic. Using this as a starting point, we only need to make a minor change to our code to store the reverse topological sort in our answer array: simply append vertices to the answer array as they finish during DFS. I have highlighted these changes below:

Modified DFS (determines if a graph is acyclic)

// returns true if the graph is acyclic
boolean DFS() {
    for (int u = 0; u < numVertices; u++)
        if (color[u] == WHITE && visit(u))
            return false;
    return true;
}

// returns true if a cycle is found
boolean visit(int u) {
    color[u] = GRAY;
    for (int v : adjlist[u])
        if (color[v] == WHITE && visit(v) || color[v] == GRAY)
            return true;
    color[u] = BLACK;
    return false;
}

Modified DFS (returns a reverse topological sort)

// returns a reverse topological sort
int[] DFS() {
    for (int u = 0; u < numVertices; u++)
        if (color[u] == WHITE && visit(u))
            return new int[0];
    return answer;
}

// returns true if a cycle is found
boolean visit(int u) {
    color[u] = GRAY;
    for (int v : adjlist[u])
        if (color[v] == WHITE && visit(v) || color[v] == GRAY)
            return true;
    color[u] = BLACK;
    // as vertices finish, store them in the answer array
    answer[index++] = u;
    return false;
}

Here is the full commented solution:

Complexity Analysis

Time: \(O(N)\)

The running time of DFS is \(O(|V|+|E|)\). In this case, the number of vertices (numCourses) is at most \(2N\) (the worst case happens when every prerequisite pair contains two unique courses) and the number of edges (number of prerequisites) is \(N\). Therefore, the total running time is \(O(N)\).

Space: \(O(N)\)

The space required by an adjacency list is \(O(|V|+|E|)\). As stated above, the number of vertices is at most \(2N\) and the number of edges is \(N\). In addition, the color and answer arrays have length \(N\) and recursive calls take \(O(N)\) stack frames. Therefore, the total space required is \(O(N)\).