用 std::stack 实现非递归 DFS

众所周知,在有些省份(比如山东、河南),省选时使用 Windows 垃圾系统评测,而 Windows 下默认的系统栈非常小(只有 1M),这造成了有些 DFS 相关算法无法通过极端数据,而是发生『栈溢出』的错误。一种解决方法是使用非递归的 DFS。

框架

我们通常这样实现递归 DFS:

第一次访问每个元素时,标记它为访问过,并对其进行初始化操作;枚举所有子元素,分为『未访问过』和『已访问过』分别进行处理。

为了将这个过程转化为非递归,我们使用一个栈来存储 DFS 搜索树上的一条链。

Tarjan 强连通分量模板

树链剖分模板

树链剖分的 DFS 过程比较特殊,我们可以每次将一个节点的所有子节点压入栈中,所有子树全部遍历完后回溯回来上传信息。