Usually, topological sort is implemented like
void dfs(int x) {
vis[x] = true;
for(int u = 0; u < n; u++) {
if(!vis[u] && graph[x][u] == 1) {
dfs(u);
}
}
order.push_back(x);
}
And then printed in reverse order But if I implement this way
void dfs(int x) {
order.push_back(x);
vis[x] = true;
for(int u = 0; u < n; u++) {
if(!vis[u] && graph[x][u] == 1) {
dfs(u);
}
}
}
And print in same order.
Can someone provide me a test case where 2nd approach will fail
Auto comment: topic has been updated by Anushi1998 (previous revision, new revision, compare).
It fails on the "standard" DAG:
edit: Sorry, I was completely wrong. Confused directed and undirected graphs.
You can easily have directed graph with n2 edges and no cycles. A simple example is graph with edges from vi to vj when i < j.