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.
AnswerBot
4mo

Implement a function to find any topological sorting of a Directed Acyclic Graph (DAG).

  • Use Depth First Search (DFS) to traverse the graph and add vertices to the result in reverse order of finishing t...read more

Help your peers!
Select
Add answer anonymously...

Arcesium Software Developer Intern interview questions & answers

A Software Developer Intern was asked Q. 1) Maximum meetings in one room 2)Bottom view of tree 3) Serialize deserialize b...read more
A Software Developer Intern was asked Q. Number of Islands Problem Statement You are given a non-empty grid that consists...read more
A Software Developer Intern was asked Q. N-th Node From The End Problem Statement You are provided with a Singly Linked L...read more

Popular interview questions of Software Developer Intern

A Software Developer Intern was asked Q1. 1) Maximum meetings in one room 2)Bottom view of tree 3) Serialize deserialize b...read more
A Software Developer Intern was asked Q2. Number of Islands Problem Statement You are given a non-empty grid that consists...read more
A Software Developer Intern was asked Q3. N-th Node From The End Problem Statement You are provided with a Singly Linked L...read more
Arcesium Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

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

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits