E - Unique Color(ABC198緑)
DFSの実装で手間取ったのでメモ。
未だに、再帰はイマイチ苦手。
大事なところ
今までdfsを実装する時、"上から下に"行く処理しか書いていなかった。
今回は下から上に上がる(戻る)時にも処理をする必要がある。
木構造の絵を書いてみるとわかる。
具体的には、
void dfs(int now){
//ここにnowに"来た時"の処理
for(auto next:G[now]){
dfs(next);
}
//ここにnowを"抜ける時"の処理
return;
}
の様に書く必要がある。
言われてみれば当たり前だけど、なぜかforの中に抜ける時の処理を書いてたりして脳がバグってた。 再帰をイメージする力を鍛える必要があるようだ。
以下は自分のACコード
