__Topological Sorting (Only for Directed)__

__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***comes before**

*u***in the ordering.**

*v*

**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.

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

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

DFS method)

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

- 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[100005];

vector < int > adj[100005];

void dfs(int x)

{

vis[x]=true;

for(auto i:adj[x])

{

if(!vis[i])

{

dfs(i);

}

}

v.push_back(x);

}

int main()

{

int n,m;

cin>>n>>m;

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

{

int a,b; cin>>a>>b; adj[a].push_back(b);

}

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