プログラミングコンテストチャレンジブック 4-3 その1

4-3 「グラフマスターへの道」からです。

• 強連結成分分解
  • 強連結成分 = 有向グラフの頂点の部分集合で任意の2点が到達可能なもの
  • 強連結成分を1ノードにまとめることで任意の有向グラフは DAG に変換できる
• Popular Cow - AがBを人気者と思っていてBがCを人気者と思っていたらAもCを人気者と思っている、というルールの元で示された"人気者と思ってるリスト"から全ての牛に人気者と思われている牛を数える
  • 牛をノードに、"人気者と思っている"を有向辺として有向グラフと考えると、任意のノードから到達可能なノードがいくつかるかという問題
  • "自分以外の全員から人気者と思われている"集団は当然お互いのことも人気者と思っているので、閉路があるはず。1つの強連結成分にまとまっている。まず強連結分解して候補を絞ってから探索できる
• 2-SAT - 乗法標準形の論理式のうちリテラル数がたかだか2つのもの
  • 論理式を a => b の形に変形 ( a ∧ b は not a => b ∧ not b => a と変形できる)
  • x と not x に対応する頂点をもち => を有向辺としてグラフを作って強連結成分分解すると強連結成分は常に真偽値が一致しないといけない。そこに x と not x が含まれていたら矛盾するので充足不可能
  • あとは強連結成分のトポロジカル順序によって論理式を充足する x の真偽値を求めることができる
• Priest John's Busiest Day - 結婚式の最初か最後に式典をするのに祭司が参加しないといけないとして、全てのカップルの結婚式に出席できるか問題
  • 各結婚式について式典を式の最初にするか最後にするかをリテラルにして 2-SAT にもちこむ