yukicoder No.497 入れ子の箱
解説見たら別解(ただし誰でも思いつきそう)だったので一応掲載。
問題概要
N個の箱の規格が与えられるので、マトリョーシカを作ったときに最大何段のマトリョーシカが作れるか求めよ。
解説
箱iが箱jを中に入れることが出来るときに頂点i→頂点jの方向に有向グラフの辺を張ることで、最も長い路の長さを求める問題になる。また、このグラフはトポロジカルソートが使えるので、入次数0の頂点から見ていき、入る辺全てを見た頂点は出る辺を確認するようにして深さを更新していけばOK。O(N^2)。
http://yukicoder.me/submissions/160343
感想
見た瞬間トポロジカルソートしか浮かばなかった…(他の解も浮かぶようになりたい)