Python3で書いたはじめてのクラスなので、もっと簡潔な表現ができるかもしれないが、自己メモとして置いておく。

Union Setは2つの要素が同一集合に属するかどうか、効率的に判定できるアルゴリズム。構造が簡単で、競プロではよく見かける。

使い方は簡単。
u = UnionSet(nmax)  # クラスの生成。nmaxは集合の最大値
u.unite(a, b)  # 整数 a, b を同一集合にする
u.connected(a, b)  # 整数 a, b は同一集合に属するかどうかを聞く
u.root(a)  # 整数 a が属する集合の代表値(ルート値)

以下はコード。AOJ-ALDS1_11_Dに対する解答でもある。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

Post Navigation