強連結成分分解

夏合宿の朝は早い | JAG Domestic 2016

起こす人uから起こされる人vへ辺(u, v)を張るようなグラフを考える。このグラフは閉路があってややこしい。とりあえず強連結成分分解してみよう。各強連結成分において誰か一人でも起きれば、その強連結成分内において全員が必ず起きる。よって強連結成分S内…

Codeforces #403 (Div. 2) D: Innokenty and a Football League

解法 各チームについてshort nameの付け方は2通りある。 また、それぞれのチームのshort nameの関係は、いくつかの包含関係で表せる。 2値変数Aが真であることをa、偽であることを¬aのように表すと (x[1]=>x[2])∧(x[2]=>x[3])∧(x[3]=>x[1])∧(¬x[3]=>x[2])∧(¬…