http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2748&lang=jp 問題 各頂点が確率を重みとして持つような頂点からなる有向グラフが与えられる。 また、各頂点は確率で状態Aとなる。状態Aとなった頂点は、隣接する頂点の状態をAに変えることが出来…

次のサイトを参考にさせていただきました。 一応自分で使いやすい感じにカスタマイズさせていただきました。 強連結成分分解(Strongly-Connected-Components) | Luzhiled’s memo 解説 トポロジカルソートの要領で各頂点からdfsして、帰りがけに頂点を追加し…

Codeforces Round #656 (Div. 3) https://codeforces.com/contest/1385/problem/E 問題 頂点辺のグラフが与えられる。 ここで、与えられる辺は、有向辺または無向辺のどちらかである。 無向辺に向きを付けることで、DAGを構成できるかどうか判定せよ。 判定…