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 <= 104
  • 0 <= E <= 104
  • 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.
Be the first one to answer
Add answer anonymously...
Bounteous x Accolite Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter