ARC 049 C - ぬりまーす

• 問題
• AC

タイプ2の条件はひとまず無視して考える。

タイプ1のそれぞれの条件$(x, y)$について$y$から$x$に辺を張ったグラフ$G$を与えたとき、問われていることは「$G$から入次数が$0$の頂点を次々に消していくとき、最大で何個消せるか？」ということだった。この個数に消す順序は関係ないので、実際に自由に消していって確かめればよい。具体的には、入次数が$0$の頂点をすべてキュー（あるいはスタック）に入れてBFS（あるいはDFS）をすれば${O}(N+A)$でできる。手順としては、キューから頂点を取り出したら、隣接頂点の入次数を1ずつ下げて、入次数が$0$になったものをキューに入れればよい。あるいは、この制約ならBellman-Fordっぽく入次数が0の頂点の隣接頂点の入次数を下げる操作を$N$周繰り返す、でもよさそう。(${O}(NA)$)

タイプ2の条件$(u, v)$については、

1. $u$を選ばないとする（=頂点$u$は存在しないものとする）
2. $v$を選ぶ場合には$u$を先に選んでいなくてはならないとする。

の2通りを調べれば十分で、後者はタイプ1と同じなので上の問題に帰着できている。タイプ2の条件は十分に少ないので、$2^B$通りのグラフを調べればよい。${O}((N+A)2^B)$。