众所周知,DFS可能会爆系统栈。
当然手写栈可以解决这个问题,但是我不会QAQ
但昨天%原教的代码,发现DFS,可以用一个“BFS + while() + 当前弧” 给优雅地替换掉
例如:
void DFS(int w, int f){ l[w] = ++tot; dep[w] = dep[f]+1; for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i], w); r[w] = tot; fa[w][0] = f; }
就可以用一下代码给完美替代:
inline void BFS(){ BUF[1] = 1; dep[1] = 1; for (int fro=1,bak=1;bak<=fro;bak++){ int w = BUF[bak]; for (int i=head[w];i;i=nxt[i]){ if (!dep[to[i]]) dep[to[i]] = dep[w]+1, fa[to[i]][0] = w, BUF[++fro] = to[i]; } } } inline void DFS(){ for (int i=1;i<=n;i++) now[i] = head[i]; int w = 1; tot = 1; while (w) { if (!now[w]) { r[w] = tot; w = fa[w][0]; } else { if (!l[w]) l[w] = ++tot; int tmp = to[now[w]]; now[w] = nxt[now[w]]; if (dep[tmp] != dep[w]+1) continue; else w = tmp; } } }
代码虽然长一点,但是可以接受,链剖也是可以搞的
至于空间代价,这个只是多了一个当前弧的数组
至于时间代价,有图有真相: