C++: Course Schedule

Thought Process

The problem involves determining if it's possible to finish all courses given their prerequisites. This can be modeled as a directed graph where courses are nodes and prerequisites are directed edges. The problem further reduces to detecting if the graph contains a cycle. If a cycle exists, it's impossible to complete all courses.

We use Kahn's Algorithm for Topological Sorting to solve this problem. First, we build the adjacency list and calculate the in-degree of each node. Nodes with an in-degree of '0' are added to a queue. We then process each node, reduce the in-degree of its neighbors, and add neighbors with an in-degree of '0' to the queue. This process continues until the queue is empty. In the end, if the number of processed nodes equals the total number of courses, the schedule is valid. 

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<int> adj[2005];
        int inDegree[2005] = {0};

        // Create the Adjacency List
        for(int i=0;i<prerequisites.size();i++){

            int u = prerequisites[i][0];
            int v = prerequisites[i][1];

            inDegree[v]++;
            adj[u].push_back(v);
        }

        // Vertex whose indegree = 0, put them in queue
        queue<int> qu;
        for(int i=0;i<numCourses;i++){
            
            if(inDegree[i]==0){
                qu.push(i);
            }
        }

        // Now, process the nodes
        int noOfProcessedNodes=0;
        while(!qu.empty()){

            int x = qu.front();     qu.pop();
            noOfProcessedNodes++;

            for(int i=0;i<adj[x].size();i++){

                int neighbor = adj[x][i];
                inDegree[neighbor]--;

                if(inDegree[neighbor]==0)
                    qu.push(neighbor);
            }
        }
        if(noOfProcessedNodes==numCourses)
            return true;
        else
            return false;
    }
};

Code Complexity

Time Complexity: O(V + E)

The algorithm processes each node (V) and each edge ( E) exactly once, making it linear in terms of the number of nodes and edges.

Space Complexity: O(V + E)

The algorithm uses an adjacency list to store the graph and an in-degree array, requiring space proportional to the number of nodes (V) and edges (E).

Code copied!