Блог пользователя Anushi1998

Автор Anushi1998, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Anushi1998 (previous revision, new revision, compare).

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

It fails on the "standard" DAG:

4 4
1 2
1 3
2 4
3 4
»
6 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

edit: Sorry, I was completely wrong. Confused directed and undirected graphs.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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.