对于以下两种输出顺序:
void dfs(int u)
{
cout << u << " ";
for (int &i = h[u]; ~i;)
{
int j = e[i];
i = ne[i];
dfs(j);
}
ans[++ cnt] = u;
}
后者保证了记录时其之后的路径已经记录完成,即在记录的时候,它往后的路径已经被记录,否则就不会走到记录这一步,而是停留在 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)