Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["data"]
    
    def __init__(self, n=0):
        self.data = [-1]*(n+1)
    
    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.data[x] < self.data[y]:
                self.data[x] += self.data[y]
                self.data[y] = x
            else:
                self.data[y] += self.data[x]
                self.data[x] = y
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def size(self, x):
        return -self.data[self.root(x)]


def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        uf.unite(a, b)
        
    ans = 0
    
    for i in range(1, n+1):
        ans = max(ans, uf.size(i))
    
    print(ans)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def members(self, x):  # 計算量n
        root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == root]

    def all_roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.all_roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.all_roots()}

    def __str__(self):
        return ''.join('{}: {}'.format(r, self.members(r)) for r in self.all_roots())

uf = UnionFind(n)

# uf.membersは呼ぶたびに計算量nかかるので，何度も呼ぶ場合は下の配列を使おう
# members = [set() for i in range(n)]
# for i in range(n):
#     r = uf.root(i)
#     members[r].add(i)
ab = [tuple(map(int,input().split())) for i in range(m)]
for i, (a,b) in enumerate(ab):
    a,b = a-1,b-1
    uf.union(a,b)

ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
par=[i for i in range(N)]
rank=[0]*(N)
friend=[0]*N
block=[0]*N
size=[1]*N
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
 
#同じ集合か判定
def same(x,y):
  return find(x)==find(y)
 
def union(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 
  if rank[x]>rank[y]:
    par[y]=x
    size[x]+=size[y]
  else:
    par[x]=y
    size[y]+=size[x]
    if rank[x]==rank[y]:
      rank[y]+=1
 
for i in range(M):
  a,b=map(int,input().split())
  a-=1
  b-=1
  union(a,b)
  friend[a]+=1
  friend[b]+=1

print(max(size))

Submission status: Accepted

Solution code:
class UnionFind:
	def __init__(self, n):
		self.p=[-1]*n
		self.size=[1]*n
	def root(self, x):
		st=set()
		while self.p[x]>=0:
			st.add(x)
			x=self.p[x]
			for y in st:
				self.p[y]=x
		return x
	def find(self, x, y):
		return self.root(x)==self.root(y)
	def union(self, x, y):
		r1=self.root(x)
		r2=self.root(y)
		if r1==r2:
			return
		p1=self.p[r1]
		p2=self.p[r2]
		if p1<=p2:
			self.p[r2]=r1
			self.size[r1]+=self.size[r2]
			if p1==p2:
				self.p[r1]-=1
		else:
			self.p[r1]=r2
			self.size[r2]+=self.size[r1]

N, M = map(int,input().split())
uft = UnionFind(N)

for i in range(M):
	A, B = map(int,input().split())
	A -= 1
	B -= 1
	uft.union(A, B)
	
print(max(uft.size))

Submission status: Accepted

Solution code:
from sys import stdin
input=lambda : stdin.readline().strip()
from math import ceil,sqrt,factorial,gcd
from collections import deque
from bisect import bisect_left,bisect_right
n,m=map(int,input().split())
graph={i:set() for i in range(1,n+1)}
for i in range(m):
	a,b=map(int,input().split())
	graph[a].add(b)
	graph[b].add(a)
v=set()
z=[]
def dfs(x):
	st=[x]
	while st:
		x=st.pop()
		if x not in v:
			z[-1]+=1
			for i in graph[x]:
				if i not in v:
					st.append(i)
			v.add(x)
for i in range(1,n+1):
	if i not in v:
		z.append(0)
		dfs(i)
print(max(z))

Submission status: Accepted

Solution code:
class UnionFindNode(object):
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()
        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)

n,q=map(int,input().split())
a=[0 for i in range(n)]
for i in range(n):
    a[i]=UnionFindNode(i)
for i in range(q):
    first,second=map(int,input().split())
    a[first-1].unite(a[second-1])
count=[0 for i in range(n)]
for i in range(n):
    count[a[i].find()]+=1
print(max(count))

Submission status: Accepted

Solution code:
n , m = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        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]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

ufd=UnionFind(n)

for i in range(m):
    b , c = map(int, input().split())
    b-=1
    c-=1
    ufd.union(b,c)

ma = 0
for j in ufd.roots():
    a = ufd.size(j)
    ma=max(ma,a)
print(ma)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class UnionFind:
    def __init__(self, n):
        self.n = n
        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]

    def union(self, x, y):
        """
        yをxの根に繋ぐ
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    res = 1
    for _ in range(m):
        a, b = map(int, input().split())
        if not uf.same(a - 1, b - 1):
            uf.union(a - 1, b - 1)
            res = max(res, uf.size(a - 1))
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
A = [set() for i in range(N+1)]
for i in range(M):
  a, b = map(int, input().split())
  A[a].add(b)
  A[b].add(a)
B = [0 for i in range(N+1)]
C = [0 for i in range(N+1)]
d = deque()
n = 1
for i in range(1, N+1):
  if B[i] != 0:
    continue
  d.append(i)
  C[n] += 1
  B[i] = n
  while len(d):
    e = d.pop()
    for k in A[e]:
      if B[k] == 0:
        d.append(k)
        C[n] += 1
        B[k] = 1
  n += 1
print(max(C))

Submission status: Accepted

Solution code:
'''
https://qiita.com/Kerzival/items/6923c2eb3b91be86f19f
'''

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N,M = map(int,input().split())
uf = UnionFind(N)

for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    uf.Unite(A,B)

print(max([uf.Count(i) for i in range(N)]))

Submission status: Accepted

Solution code:
from collections import deque
import sys

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


ans = 0
group = 0

### BFS ###


def bfs(u):

    V[u] = group
    cnt = 1  # group に属する人数

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()
        for v in E[u]:
            if V[v] == 0:  # state を確認
                V[v] = group  # state を変更
                cnt += 1  # group に人数を追加
                q.append(v)

    return cnt


N, M = map(int, sys.stdin.readline().rstrip().split())
V = [0] * N
E = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    E[a - 1].append(b - 1)
    E[b - 1].append(a - 1)

for i in range(N):
    if V[i] == 0:
        group += 1
        ans = max(ans, bfs(i))


print(ans)

Submission status: Accepted

Solution code:
"""
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m = map(int, input().split())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
size = [1 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if not same(a - 1, b - 1):
        unite(a - 1, b - 1)
x = [0] * n
ans = 0
for i in range(n):
    j = get_root(i)
    x[j] += 1
    ans = max(ans, x[j])
print(ans)
"""

from collections import deque

def bfs(s):
    q = deque()
    q.append(s)
    visit[s] = 1
    cnt = 1
    while q:
        p = q.popleft()
        for j in G[p]:
            if visit[j] == 0:
                q.append(j)
                visit[j] = 1
                cnt += 1
    global ans
    ans = max(ans, cnt)
    return

n, m = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
visit = [0] * (n + 1)
ans = 0
for i in range(1, n + 1):
    if visit[i] == 0:
        bfs(i)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1]*size

    def find(self, x):
        if self.parent[x] == x:
            return x
        # path compression
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        # union by size
        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parent[x] = y
        else:
            self.size[x] += self.size[y]
            self.parent[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def sizeofset(self, x):
        return self.size[self.find(x)]


if __name__ == "__main__":
    N, M = map(int,input().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int,input().split())
        uf.unite(a-1, b-1)
    print(max([uf.sizeofset(a) for a in range(N)]))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import re
from collections import deque
import sys
import math
input = sys.stdin.readline


def int_raw():
    return int(input())


def ss_raw():
    return input().split()


def ints_raw():
    return tuple(map(int, ss_raw()))


DIV = 10**9+7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def ncr(n, r, mod=DIV):
	r = min(r, n-r)
	ret = 1
	for i in range(1, r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * mod_inv(i, mod) % mod
	return ret


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.mini = [i for i in range(n+1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        mini = min(self.mini[x],self.mini[y])
        self.mini[x]=mini
        self.mini[y]=mini
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def main():
    N ,M = ints_raw()
    uft = UnionFind(N)
    ABs = [ints_raw() for _ in range(M)]
    for ab in ABs:
        a,b = ab
        uft.union(a-1,b-1)
    pars = [0]*N
    for n in range(N):
        pars[uft.find(n)]+=1
    print(max(pars))
    
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math, cmath
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import _heapify_max, _heappop_max, _siftdown_max
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    # def _heappush_max(h, item): h.append(item); _siftdown_max(h, 0, len(h)-1)
    
    class UnionFindTree:
        def __init__(self, num_of_elm: int):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    # table[ind] は ind の親の index を表す。ind == table[ind] の時そのグループの root である。
            self.rank = [0] * self.n    # root となる ind について rank[ind] はその木の深さを表す。それ以外の ind については意味を持たない。
            self.group_size = [1] * self.n    # root となる ind について group_size[ind] はそのグループに属するメンバの個数を表す。それ以外の ind については意味を持たない。
        
        def _find_set(self, x: int) -> int:
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                # 経路圧縮
                self.table[x] = root
                return root
        
        def is_same(self, x: int, y: int) -> bool:
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x: int, y: int) -> bool:
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            # そもそも同一グループだった時
            if shallow_root == deep_root:
                return False
            # グループが異なるので union
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                # 深さが等しかったときはつけ加えられた側の rank をインクリメントする
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x: int) -> int:
            '''
            x の属するグループのサイズを O(α(n)) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def __str__(self) -> str:
            return 'UFgroup(' + str([self._find_set(x) for x in self.table]) +')'


    n, m = mi()
    uf = UnionFindTree(n)
    cnt = 0
    for _ in range(m):
        a, b = mi_0()
        uf.union(a, b)

    size = 0
    for i in range(n):
        size = max(size, uf.akin_num(i))
    print(size)
        




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:  # 0-index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 親の番号 要素が根の場合は-(そのグループの要素数)を格納

    def find(self, x):  # 要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # 要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):  # グループの数を返す
        return len(self.roots())

    def all_group_members(self):  # {根: [グループに含まれる要素のリスト], ...}の辞書を返す
        return {root: self.members(root) for root in self.roots()}

# ---------------------- #

n, m = (int(x) for x in input().split())
if m == 0:
    print(1)
    exit()
AB = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]
uf = UnionFind(n)
for a, b in AB:
    uf.union(a, b)

ans = 0
for root in uf.roots():
    ans = max(ans, uf.size(root))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        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]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

from collections import defaultdict
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = defaultdict(int)
for i in range(n):
    ans[uf.find(i)] += 1

print(max(ans.values()))

Submission status: Accepted

Solution code:
class Union():
    def __init__(self, N):
        self.Parent = []
        for i in range(N):
            self.Parent.append(-1)

    def root(self, A):
        if (self.Parent[A] < 0):
            return A
        else:
            self.Parent[A] = self.root(self.Parent[A])
            return self.Parent[A]

    def size(self, A):
        return int(-1 * self.Parent[self.root(A)])

    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return False

        if (self.size(A) < self.size(B)):
            A, B = B, A
        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True

N, M = map(int, input().split())
union = Union(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    union.connect(a, b)

ans = 0
for i in range(N):
    ans = max(ans, union.size(i))


print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        root_x = self.root(x)
        root_y = self.root(y)
        if self.rank[x] > self.rank[y]:
            self.parent[root_y] = root_x
        elif self.rank[x] < self.rank[y]:
            self.parent[root_x] = root_y
        elif root_x != root_y:
            self.parent[root_y] = root_x
            self.rank[x] += 1
        pass


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

uf = UnionFind(n)
for a, b in ab:
    uf.unite(a - 1, b - 1)

roots = [0] * n
for i in range(n):
    roots[uf.root(i)] += 1
ans = max(roots)

print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    g = {}
    for i in range(1,n+1):
        g[i] = []
    for i in range(m):
        a,b = map(int,input().split())
        g[a] += [b]
        g[b] += [a]
    G = [-1 for i in range(n)]
    c = 0
    for i in range(n):
        if G[i] !=-1:
            continue
        que = [i]
        G[i] = c
        while len(que) > 0:
            q = que.pop(0)
            for v in g[q+1]:
                if G[v-1]!=-1:
                    continue
                G[v-1] = c
                que.append(v-1)
        c += 1
    memb_cnt = [0 for i in range(c)]
    for i in range(n):
        memb_cnt[G[i]] += 1
    print(max(memb_cnt))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,M = LI()
A,B = LIR(M,2)

class UF():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    # x が属する集合の代表値を返す
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = y = self.find(self.par[x])
            return y

    # x と y の集合を結合する
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                px, py = py, px
            if self.rank[px] == self.rank[py]:
                self.rank[px] += 1
            self.par[py] = px
            self.size[px] += self.size[py]
            return

    # x と y が同じ集合に属するか判定する
    def is_same(self,x,y):
        return self.find(x) == self.find(y)

    # x が属する集合の要素数を返す
    def get_size(self,x):
        return self.size[self.find(x)]

uf = UF(N)
for i in range(M):
    uf.union(A[i]-1,B[i]-1)

ans = 0
for i in range(N):
    ans = max(ans,uf.get_size(i))

print(ans)