## Topological Sorting (Only for Directed)

Topological sorting of a directed graph in graph theory is just a simple linear ordering of the nodes of the graph in such a way such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Example:

Here one of the topologically sorted sequence can be

A,B,C,E,D,F.

To find a topologically sorted sequence, the following algorithm is used.

1. We start from any vertex and apply a DFS on the node and start searching for all its childs.

1. We do DFS on a certain node until all its child are visited (using

DFS method)

1. After all the children of a the node are visited, we push that into a stack.

1. Popping out the stack after visiting all nodes through this algorithm will give us the topologically sorted sequence.

#include<bits/stdc++.h> using namespace std; vector <int> v;

bool vis;

void dfs(int x)

{

vis[x]=true;

{

if(!vis[i])

{

dfs(i);

}

}

v.push_back(x);

}

int main()

{

int n,m;

cin>>n>>m;

for(int i=0;i<m;i++)

{

}

memset(vis,false,sizeof(vis));

for(int i=1;i<=n;i++)

{

if(!vis[i])

{

dfs(i);

}

}

reverse(v.begin(),v.end());

cout<<"Topologically sorted sequence "<<endl;

for(auto i:v)

{

cout<<i<<" ";

}

cout<<endl;

}

Some Practice Problems

Happy Coding 😊

By Programmers Army