ARC114B✅

ARC114B✅

考えたこと

合流する時、上流同士は同時に選べない

上流を選ぶなら下流も選ばなければならない

SATっぽい

でも一つ構築するのではなく数え上げる問題だから違うか

孤立してるループは「全部選ぶ」「全部選ばない」の二択

残りは？

DAG…

いや、DAGではないな、一つの頂点から1本しか辺が出ないので分岐はない

孤立したループと、ループに流れ込む木

木の部分をどう計算するか…

いや、そもそも木の部分は選べないのでは？

ループに流れ込むところで合流が発生するが、条件2が満たせない

結局ループの個数をNとして2^N-1

公式解説

ループの個数と連結成分の個数が一致する