Find lexicographically smallest topological sort of a directed acyclic graph

tutorial
#1

this can be easily done using with bfs but if some one wants to try with dfs.
there is two imp point
1 sort all adjacency list in descending order.
2 when apply calling of dfs function iterate vertes in descending order.

this cause to push vertex with large value first in stack and then with less index vertex.

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

 vector<int> t;
int visit[10000] = {0};


void dfs(vector<int> adj[],int n)
{// {cout<<n<<" ";
if(visit[n]==0)
{visit[n]=1;
    for(int i=0;i<adj[n].size();i++)
    {
        dfs(adj,adj[n][i]);
    }
      t.push_back(n);
}
}




int main()
{
int n;
cin>>n;
vector<int> adj[n+1];

int m;
cin>>m;
int x,y;
for(int i=0;i<m;i++)
{
cin>>x>>y;
adj[x].push_back(y);
}

for(int i=0;i<=n;i++)
{
 sort(adj[i].begin(),adj[i].end(),greater<int>());
}

for(int j=n;j>=1;j--)
{
if(visit[j]==0)
{dfs(adj,j);}
}

for(int j=t.size()-1;j>=0;j--)
{
cout<<t[j]<<" ";
}


return 0;
}
5 Likes
#2

This approach fails in the following testcase:
4 4
1 3
1 2
4 2
4 1
The expected output is 4 1 2 3 but it returns 4 1 3 2.

#3

In that case plzz tell what should be the correct way to do so?

#4

Hey, as stated in the blog, it can be done easily (as well as correctly) using BFS.
Here are the steps for it

  1. Sort all adjacency list in descending order.
  2. Traverse the graph using the standard BFS algorithm.
  3. Maintain an integer i, that is the number of nodes that you have visited before visiting the current node.
  4. Assign the value of SizeOfTree - i to each node, where for each node i is the number of nodes that you have visited before visiting the current node.
#5

Do Topological sort using BFS but instead of using a queue for bfs traversal use multiset, ordered set, or priority_queue(MIN Heap) this way every time we will always pick the smallest node value present inside the container.