Topological Sort Problem Statement

Given a Directed Acyclic Graph (DAG) consisting of V vertices and E edges, your task is to find any topological sorting of this DAG. You need to return an array of size V representing the topological sort of the vertices of the given DAG.

Input:
``` The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases follows. The first line of each test case contains two space-separated integers ‘V’, ‘E’, representing the number of vertices and edges in the graph respectively. Then ‘E’ lines follow, each containing 2 space-separated integers ‘u’, ‘v’ representing that there is a directed edge from vertex ‘u’ to vertex ‘v’. ```
Output:
``` For each test case, return an array representing the topological sort of the vertices of the given DAG. ```
Example:

Consider a sample DAG. If there are directed edges as follows: from 0 to 1, from 0 to 3, from 1 to 2, and from 3 to 2, then one possible topological sort of this DAG is: {0, 1, 3, 2}.

Constraints:

1

Question

Topological Sort Problem Statement

Given a Directed Acyclic Graph (DAG) consisting of V vertices and E edges, your task is to find any topological sorting of this DAG. You need to return an array of size V representing the topological sort of the vertices of the given DAG.

Input:

``` The first line of input contains an integer ‘T’ denoting the number of test cases. The description of ‘T’ test cases follows. The first line of each test case contains two space-separated integers ‘V’, ‘E’, representing the number of vertices and edges in the graph respectively. Then ‘E’ lines follow, each containing 2 space-separated integers ‘u’, ‘v’ representing that there is a directed edge from vertex ‘u’ to vertex ‘v’. ```

Output:

``` For each test case, return an array representing the topological sort of the vertices of the given DAG. ```

Example:

Consider a sample DAG. If there are directed edges as follows: from 0 to 1, from 0 to 3, from 1 to 2, and from 3 to 2, then one possible topological sort of this DAG is: {0, 1, 3, 2}.

Constraints:

1 <= T <= 50
1 <= V <= 10⁴
0 <= E <= 10⁴
0 <= u, v < V

Note:

It is guaranteed that the given graph is a DAG.
There will be no multiple edges and self-loops in the given DAG.
There can be multiple correct solutions; you can find any one of them.
You do not need to print anything. It has already been taken care of. Just implement the given function.

Accepted Answer

Topological sort of a Directed Acyclic Graph (DAG) is found by ordering the vertices in such a way that for every directed edge u -> v, u comes before v in the ordering.

Use Depth First Search (DFS) to find the topological ordering of the vertices.
Start by visiting a vertex and recursively visit its neighbors before adding it to the result array.
Maintain a visited array to keep track of visited vertices and a stack to store the topological ordering.
Once all neighbors of a vertex are visited, add it to the stack in reverse order to get the correct topological ordering.
Return the stack as the topological sort of the DAG.

Asked in Bounteous x Accolite