POJ 1182 食物連鎖
http://poj.org/problem?id=1182
復習としてUnion-Find木の実装練習をした。蟻本に掲載されている問題。
同じ動物のもので木を作って、被食関係は木同士の関係を見ることなんとかならないかと考えたが、意外と判定が難しくて自分で解法を思いつくことができなかった。
想定解をみてみると本当に頭が良い解法だったので、ただただ受け入れた。実装自体はUnion-Find木を書くだけだった。ただし、この問題は入力が多くてcinではTLEになった。その前にも原因がよく分からないWAを何回か出してしまったのだが、結局何が悪かったのか分からないまま通ってしまった。