Topological Sort
You are given a directed acyclic graph. Your task is to find any topological sorting of the graph.

A directed acyclic graph is a directed graph with no directed cycles.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge from u to v, vertex u comes before v in the ordering.

For example-

For the given DAG-

One of the possible topological sort will be- 1 2 3

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows. The first line of each test case contains two single space-separated integers ‘N’, ‘M’, denoting the number of nodes and the number of edges respectively. The next ‘M’ lines of each test case contain two single space-separated integers ‘U’, ‘V’ each denoting there is a directed edge from node ‘U’ to node ‘V’.

Output Format:

The only line of each test case will contain N single space-separated integers representing the topological sorting of the graph. You can print any valid sorting. Print the output of each test case in a separate line. Note: You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Topological Sort

You are given a directed acyclic graph. Your task is to find any topological sorting of the graph.

A directed acyclic graph is a directed graph with no directed cycles.

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge from u to v, vertex u comes before v in the ordering.

For example-

For the given DAG-

One of the possible topological sort will be-
1  2  3

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two single space-separated integers ‘N’, ‘M’, denoting the number of nodes and the number of edges respectively.

The next ‘M’ lines of each test case contain two single space-separated integers ‘U’, ‘V’ each denoting there is a directed edge from node ‘U’ to node ‘V’.

Output Format:

The only line of each test case will contain N single space-separated integers representing the topological sorting of the graph. You can print any valid sorting.

Print the output of each test case in a separate line.

Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 5000
0 <= M <= min(5000, (N*(N-1))/2)
1 <= U, V <= N and U != V 

Time Limit: 1sec

Accepted Answer

I tried to solved this question by depth first search approach.

Accepted Answer

DFS traversal of DAG

In topological sort a vertex u must come before vertex v if there is a directed edge between u and v. We can modify DFS traversal of a graph to achieve this.

The algorithm will be-

We can declare a stack ‘topSort’ which will store the nodes after the topological sort.
We also maintain an array/list ‘visited’ of size N, denoting which node is visited in a dfs traversal. Initially, all elements of visited will be initialized to false.
We will iterate through each node from 1 to N. Let the current node be ‘currNode’. In each iteration, we will-
- If currNode is not visited we will run a DFS from ‘currNode’. In each DFS call we will:
  - Set visited[currNode] to true.
  - Recurse over all directed neighbours of currNode which is not visited.
  - Push ‘currNode’ to ‘topSort’.
We will finally print the elements of ‘topSort’ which will be our topological sort.

Space Complexity: O(n)Explanation:

O(N), where N denotes the number of nodes in the graph.

The space complexity due to recursion stack will be O(N). As the size of the ‘visited’ array/list is also N, overall space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N + M), where N denotes the number of nodes and M denotes the number of edges in the graph.

As every node and edge will be visited at most once, the time complexity will be O(N + M).

Python (3.5)

'''

    Time Complexity: O(N + M)

    Space Complexity: O(N)



    where N is the number of nodes of the graph 

    and M is the number of edges.

'''





from collections import deque





def dfs(vertex, visited, topSort, adj):



    visited[vertex] = True

    

    for i in adj[vertex]:

        if visited[i] == False:

            dfs(i, visited, topSort, adj)



    topSort.append(vertex)





def topologicalSort(edges, N, M):



    # Adjacency list representation of graph

    adj = [[] for i in range(N + 1)] 



    for i in range(M):

        adj[edges[i][0]].append(edges[i][1])





    visited = [False] * (N + 1)



    # Using deque as a stack

    topSort = deque()



    for i in range(1, N + 1):



        if not visited[i]:

            dfs(i, visited, topSort, adj)





    order = []



    while len(topSort):

        order.append(topSort[-1])

        topSort.pop()



    return order

C++ (g++ 5.4)

/*
    Time Complexity: O(N + M)
    Space Complexity: O(N)

    where N is the number of nodes of the graph 
    and M is the number of edges.
*/


#include


void dfs(int vertex, bool visited[], stack& topSort, vector adj[])
{
	visited[vertex] = true;
	
	for (auto i: adj[vertex])
	{
		if (visited[i] == false)
		{
			dfs(i, visited, topSort, adj);
		}
	}

	topSort.push(vertex);
}


vector topologicalSort(vector>& edges, int N, int M)
{
	// Adjacency list representation of graph
	vector adj[N+1];

	for (int i = 0; i < M; i++)
	{
		adj[edges[i].first].push_back(edges[i].second);
	}


	bool visited[N + 1] = {false};

	stack topSort;

	for (int i = 1; i <= N; i++)
	{
		if (!visited[i])
		{
			dfs(i, visited, topSort, adj);
		}
	}


	vector order;

	while ((int)topSort.size())
	{
		order.push_back(topSort.top());
		topSort.pop();
	}

	return order;
}