Tree雑記①

木の問題はたいてい何回かDFSを行う必要がある。まだDFSに慣れていないので、バグなく一発で実装を終えることは稀。

たとえば、DFSを中断させたくてreturnしたのに、再帰呼び出し側でreturnせずに処理を続行させてしまったり…みたいなバグを埋め込んでしまう。こういったときは、DFS関数がbool型を返すようにして、if (dfs(...)) { return true; }みたいに書くのがいいのかな。

DFSによって得たい値はDFS関数の戻り値としてではなく、副作用的に取得するのが良さそう。ただ、これだと変数のスコープが大きくなるので、集中していない限り途中で訳が分からなくなる。二重にラムダ関数を定義すればいいかも。たとえば2頂点間距離を求めるDFSは次のように書いたり。

int L = [&]() {
  int ret = 0;
  function<bool(int, int, int)> dfs = [&](int u, int p, int d) {
    if (u == T) {
      ret = d;
      return true;
    }
    for (auto v : edges[u]) {
      if (v == p) continue;
      if (dfs(v, u, d + 1)) return true;
    }
    return false;
  };
  dfs(S, -1, 0);
  return ret;
}();

このように書くことで、スコープの広い変数がLだけで済むし、dfs2などの変数を定義する必要がなくなる。けっこういいかも。これからはこういった書き方をする。

木の問題の実装は苦手だったけど、これで少しだけ苦手じゃなくなった。

次のように書くのもいいかも。

int L;
{
  function<bool(int, int, int)> dfs = [&](int u, int p, int d) {
    if (u == T) {
      L = d;
      return true;
    }
    for (auto v : edges[u]) {
      if (v == p) continue;
      if (dfs(v, u, d + 1)) return true;
    }
    return false;
  };
  dfs(S, -1, 0);
};

どっちの書き方をしようか悩む。