Toplogical Sort

Правка en1, от Anushi1998, 2017-11-18 20:48:36

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

Теги #graph, #algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Anushi1998 2017-11-18 21:43:46 12
en1 Английский Anushi1998 2017-11-18 20:48:36 619 Initial revision (published)