不思議マーケット

問題

解法

h->gではなくg->hの向きに辺を張るなら、グラフ中の有向閉路および 閉路につながる ノードがfalse、他のノードはtrueです。逆向きに辺を張るのは、閉路につながるノードをfalseにする処理はDFSにより容易に書けるからです。

tyama_yukicoder679.rb

def cycle(c,m,f,h)
    return f[c] if !f[c].nil?
    f[c]=h[c].all?{|e|
        !m.has_key?(e) && (m[e]=1;k=cycle(e,m,f,h);m.delete e;k)
    }
end
n,m=gets.split.map &:to_i
h=Hash.new{|h,k|h[k]=[]}
m.times{
g,r=gets.split.map &:to_i
h[g]=gets.split.map(&:to_i)
}
f=[nil]*-~n
(1..n).map{|i|cycle(i,{i=>1},f,h)}
p f.count(true)

感想

トポロジカルソートと聞いて、身構えてしまった。「品物の並び替え」や「おいしい好みの順番」の経験上、どうしても拒否反応が出てしまうのである。
しかし、DAGにするために取り除くのが辺ではなく頂点自体なら DAGをなしている頂点を探すだけなら高速に解けることがわかり、勉強になった。