Mae向きなブログ

Mae向きな情報発信を続けていきたいと思います。

合併-発見(Union Find)アルゴリズム(その2)

Python

以前、『アルゴリズムC〈第3巻〉グラフ・数理・トピックス』のp34で紹介されている「合併-発見アルゴリズム」をPythonで作ってみたのですが、

「D - Friend Suggestions」を解くときに、同じグループに所属している要素の数を求める必要が出てきたので、size()メッドを追加しました。

size()メソッドの追加

    def size(self, x):
        while uf.dad[x] >= 0:
            x = uf.dad[x]
        return (abs(self.dad[x]) + 1) // 2

AtCoder Beginner Contest 157 D

作成したUnionFindを使って以下の問題を解いてみました。

参考