2026-09-13
dfs_order.cpp
#include <vector>
// Returns the vertices reachable from start, in depth-first visiting order.
std::vector<int> dfs_order(const std::vector<std::vector<int>>& graph, int start) {
std::vector<bool> seen(graph.size());
std::vector<int> order;
auto visit = [&](int v) {
if (seen[v])
return;
seen[v] = true;
order.push_back(v);
for (int next : graph[v])
visit(next);
};
visit(start);
return order;
}
seenとorderをキャプチャしたラムダで深さ優先探索を書きましたが、コンパイルが通りません。何が問題で、どう直せばよいでしょうか?
Answer
autoで宣言した変数は、初期化式からその型が決まるまで使えません。ラムダ本体のvisit(next)はvisit自身の初期化式の中にあるので、「型の決まっていない変数を参照している」としてエラーになります。C++23の明示的オブジェクト引数(deducing this)を使えば、ラムダは呼ばれた自分自身を第1引数として受け取れます:
auto visit = [&](this const auto& self, int v) {
if (seen[v])
return;
seen[v] = true;
order.push_back(v);
for (int next : graph[v])
self(next);
};
呼び出し側はvisit(start)のままで、selfは自動で渡されます。C++20まではstd::function<void(int)>で型を先に書いて逃げるのが定番でしたが、型消去による間接呼び出しが入るうえ、関数の型を二度書くことになりました。