引言

在某些算法中，尤其是树、图、数据结构相关的算法，会牵扯到大量的递归。在绝大部分的OI竞赛中（NOIP、NOI等），递归所占用的栈空间限制为内存限制，换句话说，就是一般只要你不MLE就不会爆栈。 但是SDOI历年使用Windows+Cena评测，这个古老的评测系统递归的栈空间有限，经常递归到3w+就会爆栈，也就是说，如果你想遍历一条10w级别的树链是不可能的。 所以SDOI的选手们就开始写手工栈这个东西。。什么是手工栈呢？其实就是根据递归的原理用一个栈代替递归的栈空间，然后进行的操作什么的是不变的。本文将给出一些常用算法手工栈的书写。

概述

手工栈的主要部分和大体写法如下： 1、stack：手工栈。“手工栈”实际上就是这个数组，作为一个栈存储的是当前遍历到的所有点，模拟递归的过程。某一个点在栈内说明它并没有利用完成，某一个点已经出栈说明其所有的信息都已经利用过了。 2、cur：当前弧。数据结构中存储边的最常用方法是nxt数组（链表），而cur表示的就是这个点当前已经遍历到了它的哪一条边。会isap的同学可以发现这个和isap的当前弧是差不多的。 3、use：标记数组。有时需要用有时不需要用。有的递归过程在某一个点第一次遍历到的时候需要记录一些信息（比如dfs序等），这个时候就需要用到标记数组判断当前点是否是第一次遍历到。

算法流程： 1、将第一个点入栈 2、只要栈非空就一直访问栈顶 3、当栈顶的点所有信息都已经被利用就弹栈 注意：需要统计信息的时刻无非：某个点入栈、某个点第一次被访问、某个点出栈，在相对应的时刻统计信息就行了。

代码可以参考下文

树链剖分+dfs序

例题：BZOJ4034 就是一道链剖+dfs序裸题

在树链剖分和dfs序相关算法中，预处理会遍历整棵树，记录一些信息：父亲、重儿子、链顶、dfs序等。。

递归写法

void dfs_1(int x,int fa) { father[x]=fa;size[x]=1;h[x]=h[fa]+1; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) { dfs_1(v[i],x); size[x]+=size[v[i]]; if (size[v[i]]>size[son[x]]) son[x]=v[i]; } } void dfs_2(int x,int fa) { if (son[fa]==x) top[x]=top[fa]; else top[x]=x; in[x]=++dfs_clock;num[dfs_clock]=a[x]; if (son[x]) dfs_2(son[x],x); for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&v[i]!=son[x]) dfs_2(v[i],x); out[x]=dfs_clock; }

手工栈写法

void dfs_1() { int tmp=0;stack[++tmp]=1; size[1]=1;h[1]=1; for (int i=1;i<=n;++i) cur[i]=point[i]; while (tmp) { int x=stack[tmp]; while (cur[x]&&v[cur[x]]==father[x]) cur[x]=nxt[cur[x]]; if (!cur[x]) { --tmp; if (father[x]) { size[father[x]]+=size[x]; if (size[x]>size[son[father[x]]]) son[father[x]]=x; } continue; } int vt=v[cur[x]];stack[++tmp]=vt; father[vt]=x;size[vt]=1;h[vt]=h[x]+1; cur[x]=nxt[cur[x]]; } } void dfs_2() { int tmp=0;stack[++tmp]=1; top[1]=1;in[1]=++dfs_clock;num[dfs_clock]=a[1]; for (int i=1;i<=n;++i) cur[i]=point[i]; while (tmp) { int x=stack[tmp]; if (!use[x]) { use[x]=1; if (son[x]) { int vt=son[x]; top[vt]=top[x];in[vt]=++dfs_clock;num[dfs_clock]=a[vt]; stack[++tmp]=vt; } continue; } while (cur[x]&&(v[cur[x]]==father[x]||v[cur[x]]==son[x])) cur[x]=nxt[cur[x]]; if (!cur[x]) { --tmp; out[x]=dfs_clock; continue; } int vt=v[cur[x]];stack[++tmp]=vt; top[vt]=vt;in[vt]=++dfs_clock;num[dfs_clock]=a[vt]; cur[x]=nxt[cur[x]]; } }

完整代码 戳这里

Tarjan

例题 BZOJ1051

如果要是出题人出一条链来卡你的话也是会爆栈的。。 主要是tarjan本来就需要用栈好烦啊

递归写法

void tarjan(int x) { dfn[x]=low[x]=++dfs_clock;vis[x]=1;st[++t]=x; for (int i=point[x];i;i=nxt[i]) if (!dfn[v[i]]) { tarjan(v[i]); low[x]=min(low[x],low[v[i]]); } else if (vis[v[i]]) low[x]=min(low[x],dfn[v[i]]); if (dfn[x]==low[x]) { int now=0;++scc; while (now!=x) { now=st[t--]; belong[now]=scc; ++cnt[scc]; vis[now]=0; } } }

手工栈写法

void tarjan(int x) { int tmp=0;t=0;stack[++tmp]=x; dfn[x]=low[x]=++dfs_clock;vis[x]=1;st[++t]=x;cur[x]=point[x]; while (tmp) { int x=stack[tmp]; if (!cur[x]) { --tmp; if (dfn[x]==low[x]) { int now=0;++scc; while (now!=x) { now=st[t--]; belong[now]=scc; ++cnt[scc]; vis[now]=0; } } if (father[x]) low[father[x]]=min(low[father[x]],low[x]); continue; } int vt=v[cur[x]]; if (!dfn[vt]) { stack[++tmp]=vt;st[++t]=vt; dfn[vt]=low[vt]=++dfs_clock; father[vt]=x;vis[vt]=1; cur[vt]=point[vt]; } else if (vis[vt]) low[x]=min(low[x],dfn[vt]); cur[x]=nxt[cur[x]]; } }

完整代码 戳这里

二分图匹配

例题 BZOJ1854 这种需要返回参数的东西有点GG，自己YY了一个有点麻烦的写法。。。

递归写法

bool find(int x,int k) { for (int i=point[x];i;i=nxt[i]) if (vis[v[i]]!=k) { vis[v[i]]=k; if (!belong[v[i]]||find(belong[v[i]],k)) { belong[v[i]]=x; return true; } } return false; }

手工栈写法

void find(int x,int k) { int top=0;stack[++top]=x; cur[x]=point[x]; while (top) { int x=stack[top]; if (flag[belong[v[cur[x]]]]==k) { belong[v[cur[x]]]=x; flag[x]=k; --top; continue; } while (cur[x]&&vis[v[cur[x]]]==k) cur[x]=nxt[cur[x]]; if (!cur[x]) { --top; continue; } int vt=v[cur[x]]; vis[vt]=k; if (!belong[vt]) { belong[vt]=x; flag[x]=k; --top; continue; } cur[belong[vt]]=point[belong[vt]]; stack[++top]=belong[vt]; } }

完整代码 戳这里

点分治

感觉点分写手工栈最蛋疼啊。。递归的次数太多要写3次。。

递归写法

手工栈写法