Problem Statement:

There are a total of numCourses courses you have to take, labeled from 0 to numCourses – 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take the course bi first if you want to take the course ai.

  • For example, the pair [0, 1], indicates that to take the course you have to first take the course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Observation:

If you recall the concept of Topological Ordering, you will find that this question is nothing but about finding the Topological Ordering of the given courses. Therefore, we would recommend you first read about Topological Ordering.
One key difference is there, the sequence here is reversed. In Topological Ordering, we were given tasks in form of [ai, bi], and ai comes before bi. But in this problem, the order is reversed, and hence bi comes before ai.

So, to achieve this we will make a few small changes in our Topological Ordering code only.

Changes:

In Topological Ordering, we were assuming parent to 0th index element and child to 1st index element.

parent = edges[i][0]
child = edges[i][1]

In this case, the 0th index will become a child and the 1st index will become a parent. And the rest of the things are going to be the same.

child = prerequisites[i][0] 
parent = prerequisites[i][1]

Code:

import java.util.*;

class Innoskrit {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer> sortedOrder = new ArrayList<>();
        if(numCourses < 0) {
            return true;
        }
        HashMap<Integer, Integer> inDegree = new HashMap<>();
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        
        // intializing the graph
        for(int i = 0; i < numCourses; i++) {
            inDegree.put(i, 0);
            graph.put(i, new ArrayList<>());
        }
        
        // building the graph
        for(int i = 0; i < prerequisites.length; i++) {
            int child = prerequisites[i][0];
            int parent = prerequisites[i][1];
            graph.get(parent).add(child);
            inDegree.put(child, inDegree.get(child) + 1);
        }
        
        // processing all valid starting nodes
        Queue<Integer> queue = new LinkedList<>();
        for(Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
            if(entry.getValue() == 0) {
                queue.offer(entry.getKey());
            }
        }
        while(!queue.isEmpty()) {
            int vertex = queue.poll();
            sortedOrder.add(vertex);
            List<Integer> children = graph.get(vertex);
            for(int child : children) {
                inDegree.put(child, inDegree.get(child) - 1);
                if(inDegree.get(child) == 0) {
                    queue.offer(child);
                }
            }
        }
        if(sortedOrder.size() != numCourses) {
            return false;
        }
        return true;
    }

    public static void main (String[] args) {
        Innoskrit obj = new Innoskrit();
        int prerequisites[][] = new int[][]{{3, 2}, {1, 2}, {1, 0}};
        System.out.println(obj.canFinish(4, prerequisites));
    }
}
#include <bits/stdc++.h> 
using namespace std;

class Innoskrit {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> sortedOrder;
        if(numCourses <= 0) {
            return true;
        }
    
        map<int, int> inDegree;
        map<int, vector<int>> graph;
    
        // intializing the graph
        for(int i = 0; i < numCourses; i++) {
            inDegree[i] = 0;
            vector<int> v;
            graph[i] = v;
        }
    
        // building the graph
        for(int i = 0; i < prerequisites.size(); i++) {
            int parent = prerequisites[i][0];
            int child = prerequisites[i][1];
            graph[parent].push_back(child);
            inDegree[child] += 1;
        }
    
        // processing all valid starting nodes
        queue<int> q;
        for(auto entry : inDegree) {
            if(entry.second == 0) {
                q.push(entry.first);
            }
        }
    
        while(!q.empty()) {
            int vertex = q.front();
            q.pop();
            sortedOrder.push_back(vertex);
            vector<int> children = graph[vertex];
            for(auto child : children) {
                inDegree[child] -= 1;
                if(inDegree[child] == 0) {
                    q.push(child);
                }
            }
        }
    
        if(sortedOrder.size() != numCourses) {
            return false;
        }
    
        return true;
    }
};

int main(int argc, char const *argv[]) {
    Innoskrit obj;
    vector<vector<int>> prerequisites {{3, 2}, {1, 2}, {1, 0}};
    if(obj.canFinish(4, prerequisites)) cout << "true" << endl;
    else cout << "false" << endl;
    return 0;
}
from collections import deque

class Innoskrit:
    def canFinish(self, numCourses, prerequisites):
        sorted_order = []
        if(numCourses <= 0):
            return true
        in_degree = dict()
        graph = dict()
        
        # intializing the graph
        for i in range(numCourses):
            in_degree[i] = 0
            graph[i] = []
        
        # building the graph
        for i in range(len(prerequisites)):
            child = prerequisites[i][0]
            parent = prerequisites[i][1]
            in_degree[child] += 1
            graph[parent].append(child)
        
        # processing all valid starting nodes
        queue = deque()
        for key in in_degree:
            if in_degree[key] == 0:
                queue.append(key)
        while queue:
            vertex = queue.popleft()
            sorted_order.append(vertex)
            children = graph[vertex]
            for child in children:
                in_degree[child] -= 1
                if in_degree[child] == 0:
                    queue.append(child)
    
        if len(sorted_order) != numCourses:
            return False

        return True

if __name__ == '__main__':
    obj = Innoskrit()
    prerequisites = [[3, 2], [1, 2], [1, 0]]
    print(obj.canFinish(4, prerequisites))

Output:

true

Time and Space Complexity:

Let’s V be the number of courses and E is the number of prerequisites. Therefore:

Time Complexity: O(V + E)

Space Complexity: O(V + E)

Similar Problem:

Task Scheduling: There are ‘N’ tasks, labeled from ‘0’ to ‘N-1’. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, find out if it is possible to schedule all the tasks.

Solution: The above problem is exactly the same and hence can be done with the same algorithmic steps.