关于输出顺序
查看原帖
关于输出顺序
641047
4607wjq楼主2023/10/14 15:26

对于以下两种输出顺序:

void dfs(int u)
{
    // 1 (20 pts)
    cout << u << " ";
    
    for (int &i = h[u]; ~i;)
    {
        int j = e[i];
        i = ne[i];
        dfs(j);
    }
    
    // 2 (100 pts)
    ans[++ cnt] = u;
    // while (cnt) cout << ans[cnt --] << " ";
}

后者保证了记录时其之后的路径已经记录完成,即在记录的时候,它往后的路径已经被记录,否则就不会走到记录这一步,而是停留在 dfs 中。
而对于前者,无法保证这一点,比如如下数据:

3 4
1 2
2 3
3 3
3 1

输出数据对比:

1 2 3 1 3   (ver 20pts)
1 2 3 3 1   (ver 100pts)
2023/10/14 15:26
加载中...