DFSを再帰を使わずに書いて数msを捻りだす回

年末なので文字を書いて生きた証を残しましょう。記事タイトルの時点でしょうもないFastestメモですが頑張りましょう。

C++で、木のDFSって再帰関数で簡単に書けますよね。
以下に、ある根からDFSを始めて「自分の親の頂点」と「自分以下の部分木の頂点数」と「自分と根の距離」を記録するDFSをてきとーに書きました。

const int VN = 100100;
vector<int> edge[VN];
int parent[VN], subnum[VN], dist[VN], d;
int dfs(int u) {
	int ret = 1;
	dist[u] = d++;
	for (int v : edge[u]) {
		if (v != parent[u]) {
			parent[v] = u;
			ret += dfs(v);
		}
	}
	d--;
	return subnum[u] = ret;
}

頂点0があったら壊れそうですね。あと辺を大量のvectorで持っていますがこれは遅いので私がFastestやるときは絶対やりません（何）。
まぁ本筋は再帰でDFSを書くのは簡単ということです。
で、今回はですね。再帰を使わずに配列とかwhileとかでDFSをやろうという話です。

再帰でDFSを書くと、プログラミング言語さんがメモリとか自分で確保しながらうまい具合にやってくれるのだと思いますが、それに頼っていてはFastest道を究めることはできません。配列などを使って自力でDFSを書くと数msを捻りだすことができます。この数msは世界の役に立つことはないかもしれませんがFastest道には必要なものです。
(もう少し細かくこの数msの話をしますと、再帰で書いた場合と配列で書いた場合で実行時間の差が大きくなるのは再帰が深くなる時です。木が一本の長い構造の時に差が大きくなります。再帰が浅いときは実行時間の差はほぼありません。頂点数が多くて一本の構造の時この差は10msにも近づきます。)

上に書いた再帰のDFSは「自分の親の頂点」と「自分以下の部分木の頂点数」と「自分と根の距離」を結果として記録するDFSですが、以下の処理の代表例とできると思いチョイスしています。
・親から降りてくる情報に基づいて計算できるもの
・子から吸い上げてくる情報に基づいて計算できるもの
・(オイラーツアー的な)行き帰りの探索順に沿って計算できるもの
再帰を捨て配列で書くと頭が爆発するかもしれませんが、今回の例を頑張って応用すれば配列でDFSは必ず実現できるはずです。頑張っていきましょう。

const int VN = 100100;
vector<int> edge[VN];
int parent[VN], dist[VN], subnum[VN], d;
int Q[VN], q;
int main() {
	Q[q++] = 1;
	while (q) {
		int u = Q[q - 1];
		if (u > 0) {
			dist[u] = d++;
			Q[q - 1] = -u;
			subnum[u] = 1;
			for (int v : edge[u]) {
				if (v != parent[u]) {
					parent[v] = u;
					Q[q++] = v;
				}
			}
		}
		else {
			d--;
			q--;
			subnum[parent[-u]] += subnum[-u];
		}
	}
}

解説はコメントでやるといい気がするので、もっかいコメント付きで載せて解説とします。

const int VN = 100100;
//本当にFastestを目指すときは辺をvectorで書いてはならない。
vector<int> edge[VN];
int parent[VN], dist[VN], subnum[VN], d;
//以下が追加。stackの代わりの配列。ここはvectorで書いてもよさそう。
int Q[VN], q;
int main() {
	//stack代わりの配列に頂点1を追加。(今回は1が根。)
	Q[q++] = 1;
	//stack代わりの配列に残っている限り探索継続。
	while (q) {
		int u = Q[q - 1];
		//stackの最後の要素(u)が正のときは、行きの処理。
		if (u > 0) {
			//stackの最後の要素(u)を負にして次回が帰りの処理になるようにする。
			Q[q - 1] = -u;
			//行き帰りの探索順で行う計算の行きパートはここ。
			dist[u] = d++;
			//子から吸い上げてくる情報を初期化するのはここ。
			subnum[u] = 1;
			for (int v : edge[u]) {
				if (v != parent[u]) {
					//親からの情報による計算はここがおすすめ。(親uと子vが定義済みのため。)
					parent[v] = u;
					Q[q++] = v;
				}
			}
		}
		//stackの最後の要素(u)が負のときは、帰りの処理。
		else { 
			//stackの最後の削除。配列なら最後尾の番号減らすだけでよい。
			q--; 
			//行き帰りの探索順で行う計算の帰りパートはここ。
			d--;
			//子から吸い上げてくる情報による計算はここ。(親に渡す。)
			subnum[parent[-u]] += subnum[-u]; 
		}
	}
}

正と負で行きと帰りを分けているので、こちらも頂点0が入ってくると壊れます。
子から吸い上げてくる処理をするにはparentの情報が必要になります。今回のように配列を別途用意するか、もしくはQ(stack)をintのpairにしたり64bit整数にしたりして、親の情報を入れ込むのも面白いかもしれませんね。

DFSがstackで実装できるのは常識かもしれませんが、再帰で書くと簡単に書けるため、再帰を使わずにDFSしているのを見かけることはほとんどありません。
競プロのコンテスト本番では当然再帰を選ぶことになりますが、Fastest道に手を出すとこんなところにも一手間かける必要がある、というお話でした。