ARC163 D - Sum of SCC
メモ
トーナメントグラフを強連結成分分解して得られる縮約グラフはパスである。
それが本質だった。
また、強連結成分の数え上げに苦戦した。
こういう良く分からないものの数え上げは、何か別のものの数え上げに言い換えられればいいが、今回は縮約したグラフ上のパスの数+1を数えればよかったようだ。
もう少し具体的には、N頂点をA, Bという二つの集合に分ける上で
Aに空のものを許さず、Bに空を許すときに、任意のAは任意のBよりも上流にあるようなものの合計がsccの合計になる
類題としてはこれが挙げられていた。
こちらの解説ではA, Bに分ける方法のうち
BからAに向かう辺が無いような、Bの分け方がsccの合計という説明がされていた。
辺の数を数えるか、下流から何個グループをまとめられるかの違いで本質的には同じですね。
また、tournamentの場合は、辺の数関係の制約がなかったので
一つずつ頂点を追加して、現在の状態を注意深く計算しなくてよかったようだ
一般に、何かの状態を後から推定するのが難しい場合は、一つずつ構成する必要があるが、そうでない場合は後からすべて数え上げられることがある。
