LeetCode

Course Schedule

Observation: it is possible to finish all courses if and only if the course prerequisite graph does not contain a cycle.
In other words, this problem is equivalent to determining whether or not the course prerequisite graph is acyclic.

Approach 1: Modify DFS to Detect Back Edges ⭐⭐

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 determine if the graph is acyclic.
   • If we encounter a gray vertex during DFS, we have found a back edge and the graph contains a cycle (return false)
   • If we do not encounter any gray vertices during DFS, the graph has no cycles (return true)

Below, I have highlighted the changes we need to make to DFS to determine if a graph is acyclic:

DFS (original)

void DFS() {
    for (int u = 0; u < numVertices; u++)
        if (color[u] == WHITE)
            visit(u);
}

void visit(int u) {
    color[u] = GRAY;
    for (int v : adjlist[u])
        if (color[v] == WHITE)
            visit(v);
    color[u] = BLACK;
}

DFS (acyclic)

// returns true if the graph is acyclic
boolean DFS() {
    for (int u = 0; u < numVertices; u++)
        if (color[u] == WHITE)
            if (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) {
            if (visit(v)) return true; }
        // found back edge
        else if (color[v] == GRAY) return true;
    color[u] = BLACK;
    return false;
}

DFS (acyclic) refactored

// 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;
}

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 array has length \(N\) and recursive calls take \(O(N)\) stack frames. Therefore, the total space required is \(O(N)\).