Union Findはグループ分けを効率的に管理することができるデータ構造。

具体的には以下の2種類のクエリを高速に処理する。

1. 要素Aと要素Bを含むグループを統合する
2. 要素Aと要素Bが同じグループにあるかを答える

以下のようなデータ構造をしている。

上の図で言うと、要素4と要素5が同じグループかどうかは、根が同じかどうかで判別する。この場合はどちらも根が1なので同じグループと判断する。

なんとなく分かった気がするので、いつものごとく例題をこなす。

例題 ABC177 D

D - Friends

同じグループに友達がいない状況を作る。友達の友達は友達というルールになっている。

ということで、Union Findを使ってまず友人グループを作る。その後同じグループに友達がいない状況を作るには、一番大きな友人グループをバラせば良いことになる。よって、一番大きな友人グループの人数が答えになる。

class UnionFind:
  def __init__(self, n):
    self.n = n
    self.parent_size=[-1] * n

  """
  リーダーが同じなら何もしない
  リーダーが違う場合、グループの人数が少ない方を、大きい方のグループへ統合する
  """
  def merge(self, a, b):
    x, y = self.leader(a), self.leader(b)
    if x == y:
      return
    if abs(self.parent_size[x]) < abs(self.parent_size[y]):
      x, y = y, x
    self.parent_size[x] += self.parent_size[y]
    self.parent_size[y] = x
    return
  
  def same(self, a, b):
    return self.leader[a] == self.leader[b]

  """
  再帰で根にいるリーダーを探しに行く
  自分自身がリーダーなら自分を返す
  """
  def leader(self, a):
    if self.parent_size[a] < 0:
      return a
    self.parent_size[a] = self.leader(self.parent_size[a])
    return self.parent_size[a]

  """
  aが所属するグループのサイズ(人数)を返す
  """
  def size(self, a):
    return abs(self.parent_size[self.leader(a)])

  def groups(self):
    result = [[] for _ in range(self.n)]
    for i in range(self.n):
      result[self.leader(i)].append(i)
    return [r for r in result if r != []]

n, m = map(int, input().split())

uni = UnionFind(n)

# 友人関係の記録
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  uni.merge(a, b)
friends = uni.groups()

# グループの人数を確認する
howmanyfriends = []
for fri in friends:
  howmanyfriends.append(len(fri))

# 最小で分割するためには、人数が最も多いグループの人たちを全員別のグループに分けるから
print(max(howmanyfriends))