1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

[Python] UnionFind ABC177D

Last updated at Posted at 2020-08-30

#ABC177D

一番大きいユニオンに属する人数の数だけグループを作ればい。
UnionFindにはいろいろな実装があるが, 本問ではparents配列にノード数を保持する実装だと非常に簡単に解ける. 以下のようにしてノード数を保持する.

・自身が子のとき, 親ノード番号を格納する。自身が根のとき, ノード数を負の数で格納する。
・負の数のときは自身が根であり, その絶対値がその木のノード数を表す。

(参考)
グループ数を求める問題が、ACL BeginnerのCで出ている。
【AtCoder解説】PythonでACL BeginnerのA,B,C問題を制する!

サンプルコード
import sys

#UnionFindTreeクラスの定義
class UnionFind():
    #クラスコンストラクタ
    #selfはインスタンス自身
    def __init__(self, n):
        #親ノードを-1に初期化する
        self.parents = [-1] * n

    #根を探す(再帰関数)
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    #xとyの木を併合する
    def union(self, x, y):
        #x,yの根をX,Yとする
        X = self.find(x)
        Y = self.find(y)

        #根が同じなら結合済み
        if X == Y:
            return

        #ノード数が多い方をXとする
        if self.parents[X] > self.parents[Y]:
            X, Y = Y, X

        #XにYのノード数を足す
        self.parents[X] += self.parents[Y]
        #Yの根を X(>0) とする
        self.parents[Y] = X

    #木のサイズ
    def size(self, x: int) -> bool:
        return self.root[self.find(x)] * -1


N, M = map(int, input().split())
 
#UnionFindインスタンスの生成
uf = UnionFind(N)
for _ in range(M):
    #インデックスを調整し、a,bの木を結合
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = min(uf.parents)

print(-ans)
1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?