There are N courses with a prerequisites relationship among them. Our task is to determine the number of semester needed to complete all the courses. Here are the key points that will help us get started:
We cannot take a course whose prerequisites are not yet taken.
We cannot take a course whose prerequisites are even taken in this semester.
We have to start with the course that has no prerequisites.
If there is a cycle in the prerequisites relationship, there will be no solution.
As there are relationship among courses and we need to pick and complete each course at semesters, we know that it is a graph problem. We need to check if there is any cycle or not, if there isn’t, then we will need to get the course whose prerequisites are all complete. This is exactly what Topological Sorting does.
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.
So the answer of our problem is to make a topological ordering of the courses. And if we cannot make the ordering, then we will need to return -1.
Step 2: Build the Graph
To solve the problem with topological sorting, we need a graph first. In this graph, the nodes will be courses and the edges will be the relationships. The relationships are already given as edges relations. We will convert these into adjacency matrix representation.
So the graph will be a dictionary where, keys are courses and values are lists having courses that are dependent on the keys. We loop through relations and put them in the graph accordingly.
1
2
3
4
5
6
graph={}forrelationinrelations:# Make sure we don't get KeyErrorifrelation[0]notingraph:graph[relation[0]]=[]graph[relation[0]].append(relation[1])
Step 3: Topological Sorting Initialization
Topological Sorting requires us to track the in degrees of all nodes. For this, we will create an array named in_degree of size N+1. The courses in the problem is given in 1-indexed notation, for this, we have to create the extra unused index at 0.
1
2
in_degree=[0]*(N+1)# Or: in_degree = [0 for _ in range(N+1)]
We can track the degrees while building the graph. Each time we find a relation, we increase the in degree of the descendant node.
1
2
3
4
5
6
7
8
# in_degree of N nodes, 1 indexedin_degree=[0]*(N+1)# in_degree initializationgraph={}forrelationinrelations:ifrelation[0]notingraph:graph[relation[0]]=[]graph[relation[0]].append(relation[1])in_degree[relation[1]]+=1# update in_degree
Topological Sorting is very similar to BFS (Breadth First Search) or DFS (Depth First Search). Except that BFS/DFS starts from a source, topological sorting starts from all the nodes that has in_degree = 0. We will do a BFS. To do this, we will need a queue. For implementation, we will use pythons built-in collections.deque data structure. Start a loop through all the N courses, and put the courses that has in_degree = 0 into the queue.
1
2
3
4
5
# Collect all 0 in degree nodesqueue=deque()foriinrange(1,N+1):ifin_degree[i]==0:queue.append(i)
Step 4: Topological Sorting
Topological Sorting will keep running a loop until the queue is empty. At the beginning of the loop, we will keep track of how many courses we have in the queue. Because that will be the number of courses we can take in this semester (this_semester). this_semester is not used in anywhere, it is named so, for understanding purposes only.
At each semester, we will take each course from the queue, and decrease the in_degrees of all the courses that depend on current course. If in_degree for a course becomes 0, we push it into the queue to mark it available for the next semester. After doing this for all the queue elements, we will increament the semester by 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Topological sortsemesters=0courses_taken=0whilequeue:# len(queue) courses in 1 semesterforthis_semesterinrange(len(queue)):course=queue.popleft()courses_taken+=1ifcourseingraph:forneighboringraph[course]:in_degree[neighbor]-=1ifin_degree[neighbor]==0:queue.append(neighbor)semesters+=1
courses_taken another variable is used to count the number of courses popped from the queue. This will be used after the topological sorting to test if we could take all the courses or not. Here, courses_taken != N will be True when there is a cycle detected in the graph and there is no topological sorting possible.
Below is a demonstration of the topological sorting process.
If courses_taken == N, we know that we have taken all the courses, so we return the number of semesters.
1
2
3
4
5
# Make sure all courses are takenifcourses_taken!=N:return-1returnsemesters
This is a pure algorithm of topological sorting with no overhead. So the time and space complexity for this problem is that of topological sorting, O(N+|relations|) and O(N). The complete solution is given below.
fromcollectionsimportdequefromtypingimportListclassSolution:defminimumSemesters(self,N:int,relations:List[List[int]])->int:# in_degree of N nodes, 1 indexedin_degree=[0]*(N+1)graph={}forrelationinrelations:# Make sure we don't get KeyErrorifrelation[0]notingraph:graph[relation[0]]=[]graph[relation[0]].append(relation[1])in_degree[relation[1]]+=1# Collect all 0 in degree nodesqueue=deque()foriinrange(1,N+1):ifin_degree[i]==0:queue.append(i)# Topological sortsemesters=0courses_taken=0whilequeue:# len(queue) courses in 1 semesterforthis_semesterinrange(len(queue)):course=queue.popleft()courses_taken+=1ifcourseingraph:forneighboringraph[course]:in_degree[neighbor]-=1ifin_degree[neighbor]==0:queue.append(neighbor)semesters+=1# Make sure all courses are takenifcourses_taken!=N:return-1returnsemesters
classSolution{public:intminimumSemesters(intN,vector<vector<int>>&relations){// in_degree of N nodes, 1 indexed
vector<int>inDegree(N+1);map<int,vector<int>>graph;for(autorelation:relations){graph[relation[0]].push_back(relation[1]);inDegree[relation[1]]++;}// Collect all 0 in degree nodes
queue<int>q;for(inti=1;i<N+1;i++)if(inDegree[i]==0)q.push(i);// Topological sort
intsemesters=0;intcoursesTaken=0;while(!q.empty()){// q.size() courses in 1 semester
intthisSemesterCourses=q.size();for(intthisSemester=0;thisSemester<thisSemesterCourses;thisSemester++){intcourse=q.front();q.pop();coursesTaken++;if(graph.find(course)!=graph.end()){for(autoneighbor:graph[course]){inDegree[neighbor]--;if(inDegree[neighbor]==0)q.push(neighbor);}}}semesters++;}// Make sure all courses are taken
if(coursesTaken!=N)return-1;returnsemesters;}};
classSolution{publicintminimumSemesters(intN,List<List<Integer>>relations){// in_degree of N nodes, 1 indexed
int[]inDegree=newint[N+1];Map<Integer,List<Integer>>graph=newHashMap<>();for(List<Integer>relation:relations){List<Integer>descendants=graph.getOrDefault(relation.get(0),newArrayList<>());descendants.add(relation.get(1));graph.put(relation.get(0),descendants);inDegree[relation.get(1)]++;}// Collect all 0 in degree nodes
Queue<Integer>queue=newLinkedList<>();for(inti=1;i<N+1;i++)if(inDegree[i]==0)queue.add(i);// Topological sort
intsemesters=0;intcoursesTaken=0;while(!queue.isEmpty()){// queue.size() courses in 1 semester
intthisSemesterCourses=queue.size();for(intthisSemester=0;thisSemester<thisSemesterCourses;thisSemester++){intcourse=queue.remove();coursesTaken++;if(graph.containsKey(course)){for(intneighbor:graph.get(course)){inDegree[neighbor]--;if(inDegree[neighbor]==0)queue.add(neighbor);}}}semesters++;}// Make sure all courses are taken
if(coursesTaken!=N)return-1;returnsemesters;}}