n4_t https://blog.hatena.ne.jp/n4_t/ naoya_t@hatenablog https://naoyat.hatenablog.jp/ TopCoder SRM 過去問 Algorithms グラフ理論 ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。（ちなみにSRM464には出場している）SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみのあれです (x_0 ∨ ¬x_1) ∧ (¬x_0 ∨ ¬x_3) ∧ ... みたいな論理式（乗法標準形）を満たす真偽値 x_0, x_1, ... の組み合わせが存在するか否か。（存在する場合、その組み合わせを知りたかったりする） 上の例ではすべての節が(高々)2変数なので2-SA… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnaoyat.hatenablog.jp%2Fentry%2F2013%2F07%2F13%2F220034" title="2-SATと強連結成分分解 - naoya_t@hatenablog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://ecx.images-amazon.com/images/I/41bHxtpurqL.jpg Hatena Blog https://hatena.blog 2013-07-13 22:00:34 rich https://naoyat.hatenablog.jp/entry/2013/07/13/220034 1.0 100%