【算法笔记】非递归DFS

众所周知,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;
		}
	}
}

代码虽然长一点,但是可以接受,链剖也是可以搞的
至于空间代价,这个只是多了一个当前弧的数组
至于时间代价,有图有真相:non_recursionrecursion

 

【Tricks】手动扩栈

众所周知,HDU等搭建在windows下的OJ系统栈小得一逼,所以我们得手动扩栈……..
其实平时比赛,如果递归爆栈了,也是可以用这个特殊技能水一水的:

G++: 
int size = 256 << 20; // 256MB  
char *p = (char*)malloc(size) + size;  
__asm__("movl %0, %%esp\n" :: "r"(p)); 

C++: 
#pragma comment(linker, "/STACK:102400000,102400000")    

当然,如果会写手工栈,那也是极好的,然而我不会QAQ

———— 2016.8.28 更新 ————-
在BZOJ这种linux平台下,好像上面的扩栈方法不管用
于是我们可以添加如下代码:

const int main_stack=16;
char my_stack[128<<20];//À©Îª128MB
int main()
{
	__asm__("movl %%esp, (%%eax);\n"::"a"(my_stack):"memory");
	__asm__("movl %%eax, %%esp;\n"::"a"(my_stack+sizeof(my_stack)-main_stack):"%esp");
	my_main();
	__asm__("movl (%%eax), %%esp;\n"::"a"(my_stack):"%esp");
	return 0;
}

然后把原来的 int main() 改成 int my_main() 即可

—————————— UPD 2017.7.3 ——————————
在g++的编译命令里加入-Wl,--stack=536870912也可以开栈