AtCoder Regular Contest 049 C - ぬりまーす

頂点が有向グラフである意味がない…

問題概要

(リンク)http://arc049.contest.atcoder.jp/tasks/arc049_c

• N頂点の有向グラフがある
• 頂点に色を塗る
• その際以下の制約つける
  • 頂点xに色をぬるとき、頂点yに色が塗られていなければならない
  • 頂点uに色を塗るとき、 既に頂点vに色が塗られていてはいけない
• 適切な順番で色を塗った時、最大いくつ色を塗られるか

解法

制約をグラフで表現する。

• ひとつ目の制約はy→xというエッジ
• ふたつ目の制約は
  • u → vというエッジ
  • あるいはuを通行不可 (塗らない) とする

ふたつ目の制約は最大10個しかないので「u → vというエッジ」、「uを通行不可とする」を総当りする。
作成したグラフを強連結成分分解すると、強連結成分として2つ以上のノードがある場合、そのノードには辿りつけない。
例えばu←→vのようなエッジが貼ってあれば、お互いを塗るためにお互いが先に塗られていなければいけないためである。
また、通行不可としたノードから辿り着けるノードは通行不可である。