from ARC114 ARC114B✅
- 考えたこと
- 合流する時、上流同士は同時に選べない
- 上流を選ぶなら下流も選ばなければならない
- SATっぽい
- でも一つ構築するのではなく数え上げる問題だから違うか
- 強連結成分分解する
- 孤立してるループは「全部選ぶ」「全部選ばない」の二択
- 残りは？
- DAG…
- いや、DAGではないな、一つの頂点から1本しか辺が出ないので分岐はない
- 孤立したループと、ループに流れ込む木
- 木の部分をどう計算するか…
- いや、そもそも木の部分は選べないのでは？
- ループに流れ込むところで合流が発生するが、条件2が満たせない
- 結局ループの個数をNとして2^N-1
- 公式解説
- ループの個数と連結成分の個数が一致する