問題

$N$ 頂点のグラフのいくつかの頂点に、以下のような制約を満たすように色を塗る。

タイプ1：ある頂点 $x$ に色を塗るとき、既に頂点 $y$ に色が塗られてなければならない
タイプ2：ある頂点 $u$ に色を塗るとき、既に頂点 $v$ に色が塗られていてはいけない

全ての制約を満たすときに塗れる頂点の最大数を求める。

考察

タイプ1の制約は、「頂点 $y \rightarrow x$ の順番で塗る」ということ。これを「 $y \rightarrow x$ 」と表記する。ある頂点 $x$ が塗れないとき、 $y \rightarrow x$ を満たし塗れない頂点 $y$ が存在する、もしくは $x \rightarrow \cdots \rightarrow x$ となっているとき（「 $x$ を塗る前に $x$ が塗られている」必要がある）である。後者は、有向グラフの閉路検出で、強連結成分分解が使える。2つ以上の頂点を含む連結成分から連鎖的に塗れない頂点がわかる。