一番大きいユニオンに属する人数の数だけグループを作ればい。
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)