【DSU編】AtCoder Library 解読 〜Pythonでの実装まで〜 - Qiita

0. はじめに 2020年9月7日にAtCoder公式のアルゴリズム集 AtCoder Library (ACL)が公開されました。 私はACLに収録されているアルゴリズム、データ構造のほとんどが初見だったのでいい機会だと思い、アルゴリズムの勉強からPythonでの実装までを行いました。 この記事ではDSUをみていきます。 対象としている読者 DSUってなに？という方。 ACLのコードを見てみたけど何をしているのかわからない方。 C++はわからないのでPythonで読み進めたい方。 参考にしたもの AtCoder公式によるわかりやすい解説があります。 スライド youtube解説動画（ABC157の解説動画です） 1. DSUとは DSU (Disjoint Set Union, 素集合データ構造)はあるデータ集合を素集合(グループ)に分割して保持するデータ構造です。すなわち各データが１つ