プログラミング備忘録

日頃のプログラミングの成果をここに書いていきます.

深さ優先探索において,引数に母親を指定する

久々の更新ですが,メモを書いておきます. 深さ優先探索において,母親を指定しておくと一回行ったかどうかを判定しなくてもいい.

void dfs (ll i, ll pa = -1) {
  dp[i][0] = 1;
  dp[i][1] = 1;
  for (auto j : box[i]) {
    if (j != pa) {
      dfs(j, i);
      
      dp[i][0] = ((dp[i][0] % mod) * ((dp[j][0] + dp[j][1]) % mod)) % mod;  
      dp[i][1] = ((dp[i][1] % mod) * (dp[j][0] % mod)) % mod;
    }  
  }
}