ゆくゆくは有へと

おかゆ/オカ∃/大鹿有生/彼ノ∅有生 の雑記

Disjoint set を勉強した AOJ #2512222 - Python編

Disjoint Set: Union Find Tree | Aizu Online Judge

AOJの解説とは異なり、root が自身へのポインタではなく、その木の集合を持つようにしてある。

当たり前ながら、破壊的更新ができるなら冗長な構造ですけど、ちょっと先のことも踏まえてこうした。

Pythonの集合はたしかハッシュセットなので、そこまで極端に速度落ちないことを期待する。

あと、競プロにありがちなデータ入力が毎回打つのダルすぎて、Stdinクラスに関数をまとめた。

パターンマッチ使いて~~~~~~~~~~~~~~~~~~~~~~~

Aizu #2512222