New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Course Schedule

Last Updated: 10 Jul, 2023

Easy

0/40

15 mins

85 %

36 upvotes

+16 more

Problem Statement

You are a student of Netaji Subhas Institute of Technology. You have to take ‘N’ number of courses labelled from 1 to N to complete your B.Tech Degree.

Some courses may have prerequisites, for example, to take course 1 you have to first take course 2, which is expressed as a pair: [1, 2]. Now, your task is to find is it possible for you to finish all courses.

Note: There are no duplicate pairs in the prerequisites array.

For example-

If N = 2 and prerequisite = [[1, 2]]. Then, there are a total of 2 courses you need to take. To take course 1 you need to finish course 2. So, it is possible to complete all courses.

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

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ representing the total number of courses and the total number of prerequisites, respectively.

From the second line of each test case, the next M lines represent the prerequisites for courses. Every line contains two single space-separated integers representing a prerequisite pair.

Output Format:

For each test case, the only line of output will print “Yes” if you can complete the courses. Else print “No”.

Print the output of each test case in a separate line.

Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 5000
0 <= M <= min(5000, (N * (N - 1)) / 2)
1 <= prerequisites[i][0] <= N 
1 <= prerequisites[i][1] <= N 

Time Limit: 1 sec

Sample Input 1:

Sample output 1:

No

Explanation of Sample output 1:

There are a total of 3 courses you need to take. To take course 1 you need to finish course 2. To take course 2 you need to finish course 1. So, it is impossible to complete all courses.

Sample Input 2:

Sample output 2:

Yes
Yes

Autocomplete

Console