Find lexicographically smallest topological sort of a directed acyclic graph

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

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.