読者です 読者をやめる 読者になる 読者になる

yukicoder No.497 入れ子の箱

解説見たら別解(ただし誰でも思いつきそう)だったので一応掲載。

問題概要

N個の箱の規格が与えられるので、マトリョーシカを作ったときに最大何段のマトリョーシカが作れるか求めよ。

No.497 入れ子の箱 - yukicoder

解説

箱iが箱jを中に入れることが出来るときに頂点i→頂点jの方向に有向グラフの辺を張ることで、最も長い路の長さを求める問題になる。また、このグラフはトポロジカルソートが使えるので、入次数0の頂点から見ていき、入る辺全てを見た頂点は出る辺を確認するようにして深さを更新していけばOK。O(N^2)。

http://yukicoder.me/submissions/160343

感想

見た瞬間トポロジカルソートしか浮かばなかった…(他の解も浮かぶようになりたい)