[Python] UnionFind ABC177D - Qiita

ABC177D 一番大きいユニオンに属する人数の数だけグループを作ればい。 UnionFindにはいろいろな実装があるが, 本問ではparents配列にノード数を保持する実装だと非常に簡単に解ける. 以下のようにしてノード数を保持する. ・自身が子のとき, 親ノード番号を格納する。自身が根のとき, ノード数を負の数で格納する。 ・負の数のときは自身が根であり, その絶対値がその木のノード数を表す。 （参考） グループ数を求める問題が、ACL BeginnerのCで出ている。 【AtCoder解説】PythonでACL BeginnerのA,B,C問題を制する！ import sys # UnionFindTreeクラスの定義 class UnionFind(): #クラスコンストラクタ #selfはインスタンス自身 def __init__(self, n): #親ノードを-1に初期化する