Course Schedule II

Hard

0/120

Average time to solve is 50m

Contributed by

29 upvotes

Asked in companies

Problem statement

You have been given ‘N’ courses and some courses may have prerequisites. Now consider a matrix ‘PREREQUISITES’ of size 'M' x 2 which represents that you must complete the course 'PREREQUISITES[i][1]' before the course 'PREREQUISITES[i][0]'.

Your task is to return the order of courses you should take to finish all courses.

Note:

If it is impossible to finish all courses, return an empty array. If there are multiple answers, return any one.

For example:

Input:
3 2
1 2
2 3

There are three courses to take. To start with, First course 3 is taken. Then course 2 is taken for which course 3 must be completed. 

At last course 1 is taken for which course 2 must be completed. So the correct course order is [3,2,1].

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two integers 'N' and 'M' representing the number of courses and the number of prerequisite pairs.

The next ‘M’ lines in each test case contain a matrix ‘PREREQUISITES’ containing two integers denoting a prerequisite pair.

Output Format:

The only line contains a single integer 1 if the returned order of the courses is correct, otherwise 0.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Sample Input 1:

Sample Output 1:

Explanation of Sample Output 1:

There are a total of 4 courses to take. To take course 4 you should have finished both courses 2 and 3. 

Both courses 2 and 3 should be taken after you finish course 1. So one correct course order is [1,2,3,4]. Another correct ordering is [1,3,2,4]. 

When the ordering is one of the above two sets then output is 1.

Sample Input 2:

2 1
2 1

Sample Output 2:

Constraints :

2 <= 'N' <= 10^5
0 <= 'M' <= 10^5

Where ‘PREREQUISITES’ denotes the prerequisites matrix.

Time limit: 1 sec

Console