[Python] UnionFind ABC177D

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)