前回のUnion Find木実装を踏まえてAtCoder ABC/ARCのD問題や蟻本の元の例題に取り組んでみる。 ABC049 D問題 - 連結/Connectivity abc049.contest.atcoder.jp abc049.contest.atcoder.jp 道路ネットワークと鉄道ネットワークが走っている国で、街ごとに道路…

「ある集合の二つの要素が繋がっているか」を効率的に判定できるデータ構造であるUnion Find木の話。 非常に簡単でエレガントな実装のわりに非常に強力な概念だという印象で、個人的にはとても好き。 蟻本の例題が一番特殊で面白いので後回し。まずはAtCoder…