単調減少してから単調増加するPathがキーになることは分かったけど…ループがどうなるかよくわからなくなった。
http://agc016.contest.atcoder.jp/tasks/agc016_e
まずある一つの頂点xに注目する。操作を後ろから見て、i番目の人の操作が終わった際、何が生き残っていればxが生き残るかを調べる。
この際にマークした点でループが出来ると不可。xは候補から取り除く。
1番目の人の操作の前、生き残っていてほしい鳥の集合をCxとしよう。
xとyが最終的に生き残るためにはCxとCyが共通の要素を持たないことが必要十分条件となる。
共通の要素を持つとCxとCyの要素どちらとも端点に持つ辺が存在してしまい、その辺についての操作でどちらの鳥を食べてしまうからだ。
逆にCxとCyに共通の要素がなければ、各辺についてCxとCyのどちらにも含まれない鳥を食べていけばxとyは生き残ることが出来る。
これを少し見方を変えると、xからある点zまで単調減少するpathとzからyまで単調増加するpathを考える問題と同値になる。
x=y(つまりループの時)なら単にxは使えないとすればよい。
