Topological Sorting

Contributed by

Anup Kumar Singh

Medium

Avg time to solve 30 mins

Success Rate 60 %

5 upvotes

Problem Statement

Given a DAG(direct acyclic graph), print Topological Sorting of a given graph

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

Input Format:

The first line of input contains an integer T, the number of test cases.
The first line of each test case contains two single space-separated integers V, and E.
From the second line onwards of each test case, the next 'E' lines will denote the edges of the graph where every edge is defined by two single space-separated integers 'a' and 'b', which signifies an edge from vertex 'a’ to vertex 'b'.

Output Format :

For each test, case output will be "Correct" if the topological sort is done correctly else it will be "Incorrect".

Constraints:

1 <= T <= 10
1 <= V <= 1000
0 <= E <= 3000
0 <= U, V <= V-1

Time Limit: 1sec

Sample Input 1:

Sample Output 1:

Correct

Sample Output 1 Explanation:

One correct sort order is : 3 1 0 4 2.

Console