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...
Top Bounteous x Accolite Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Top HR questions asked in Bounteous x Accolite Software Developer Intern
>
Bounteous x Accolite Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
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
Get AmbitionBox app