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():
    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 same(self, x, y):
        return self.find(x) == self.find(y)

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

N, M = list(map(int, input().split()))

tree = UnionFind(N)

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

group_size_max = 0
for j in range(N):
    group_size_max = max(group_size_max, tree.size(j))

print(group_size_max)

Submission status: Accepted

Solution code:
# 幅優先探索, BFS
from collections import deque

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

neighbor = [[] for _ in range(n)]
for edge in edges:
    neighbor[edge[0]-1].append(edge[1]-1)  # 1- → 0-index
    neighbor[edge[1]-1].append(edge[0]-1)


visited = [-1] * n
ans = 1
for idx in range(n):
    if visited[idx] == -1:
        queue = deque()
        queue.append(idx)
        group_population = 1
        visited[idx] = 0
        while len(queue) > 0:
            vertex = queue.popleft()
            for nei in neighbor[vertex]:
                if visited[nei] == -1:
                    visited[nei] = 0
                    queue.append(nei)
                    group_population += 1
    
    ans = max(ans, group_population)
        
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(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)
x = 0
for i in range(n):
    x = max(x, uf.group_size(i))
print(x)

Submission status: Accepted

Solution code:
"""
UnionFind
"""
class UnionFind:
    def __init__(self, n: int) -> None:
        self.forest = [-1] * n

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x,y = y,x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

    def findRoot(self, x: int) -> int:
        if self.forest[x] < 0:
            return x
        else:
            self.forest[x] = self.findRoot(self.forest[x])
            return self.forest[x]

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)
    
    def size(self,x: int) -> int:
        return -self.forest[self.findRoot(x)]

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

u = UnionFind(n)
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    u.union(a,b)
ans = 0
for i in range(n):
    ans = max(ans,u.size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

uf = UnionFind(n)

for ai, bi in ab:
    uf.union(ai-1, bi-1)

for i in range(n):
    p = uf.find(i)

print(-min(uf.parents))

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())



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

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

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()}

N,M = map(int,input().rstrip().split(" "))
uft = UnionFind(N)
ans = 0
for i in range(M):
    a,b = map(int,input().rstrip().split(" "))
    uft.union(a-1,b-1)
for i in range(N):
    ans = max(ans,uft.size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys


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 read():
    return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, read().split())
    uf = UnionFind(n)
    for _ in range(m):
        a, b,  = [int(i) - 1 for i in read().split()]
        uf.union(a, b)
    print(-min(uf.parents))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return
        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
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

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

    def count(self, x):
        return -self.root[self.find(x)]


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)

val = 0
for i in range(n):
    val = max(val, uf.count(i))

print(val)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#Union Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y] #xにyの個数くっつける 
        par[y] = x #yをxにくっつける
        return 

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

N,Q = map(int,readline().split())
#0-index
par = [-1]*(N+1)
for _ in range(Q):
    x,y = map(int,readline().split())
    union(x,y)

print(-min(par))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

class UnionFind(object):
    def __init__(self, n):
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

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

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

    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.par) if x < 0]

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

def main():
    from builtins import int, map
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        uf.unite(ai, bi)

    # 最大のグループサイズ
    ans = -1
    for n in range(N):
        ans = max(ans, uf.size(n))
        # print(n, uf.size(n))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        parent = self.parent
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.parent[y] = x
        self.size[x] += sy


uni = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    uni.merge(a, b)


max_size = 0
for i in range(1, N+1):
    max_size = max(max_size, uni.size[i])

print(max_size)

Submission status: Accepted

Solution code:
class UF:
  def __init__(self,n=0):
    self.vertices=n
    self.mother=[-1 for i in range(self.vertices)]
  
  def root(self,x):
    normalize_v=[]
    while x!=-1:
      normalize_v.append(x)
      y=x
      x=self.mother[x]
    for i in normalize_v[:-1]:
      self.mother[i]=y
    return y
  
  def union(self,x,y):
    root_y=self.root(y)
    root_x=self.root(x)
    if root_x!=root_y:
      self.mother[root_x]=root_y
  
  def find(self,x,y):
    if self.root(x)==self.root(y):
      return True
    else:
      return False

n,m=map(int,input().split())
uf=UF(n)
for i in range(m):
  q=list(map(lambda x:int(x)-1,input().split()))
  uf.union(q[0],q[1])

l=[0 for i in range(n)]
ml=0
for i in range(n):
  r=uf.root(i)
  l[r]+=1
  ml=max(ml,l[r])

print(ml)

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int, input().split())

# Union-Find
parent = [i for i in range(N)]
rank = [1] * N
def get_root(node):
  global parent
  if parent[node] == node:
    return node
  root = get_root(parent[node])
  parent[node] = root
  return root

def union(a, b):
  global parent
  global rank
  root_a = get_root(a)
  rank_a = rank[root_a]
  root_b = get_root(b)
  rank_b = rank[root_b]
  if root_a == root_b:
    return
  if rank_a < rank_b:
    parent[root_a] = root_b
  else:
    parent[root_b] = root_a
    if rank_a == rank_b:
      rank[root_a] += 1

for _ in range(M):
    a, b = map(int, input().split())
    union(a-1, b-1)

for i in range(N):
    get_root(i)

ct = Counter(parent)
print(ct.most_common()[0][1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n,m=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)

ans=0
from collections import deque
used=[0 for _ in range(n)]
for i in range(n):
    if used[i]==0:
        d=deque([i])
        cnt=0
        while d:
            now=d.popleft()
            cnt+=1
            used[now]=1
            for e in es[now]:
                if used[e]==0:
                    used[e]=1
                    d.append(e)
        ans=max(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

input = sys.stdin.buffer.readline
int1 = lambda x: int(x) - 1

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

frm, to = [0] * M, [0] * M
for i in range(M):
    a, b = map(int1, input().split())
    frm[i] = a
    to[i] = b

matr = csr_matrix(([1] * M, (frm, to)), shape=(N, N))
_, labels = connected_components(matr, directed=False)
print(max(Counter(labels).values()))

Submission status: Accepted

Solution code:
import sys


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


N, M = map(int, input().split())
info = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]

uf = UnionFind(N)
for a, b in info:
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
MOD = 10**9 + 7

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

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

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x] 
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
n, m = map(int, input().split())
DS = DisjointSet(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    DS.unite(a, b)
ans = 0
for i in range(n):
    ans = max(ans, DS.get_size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return float(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


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())






def main():
	n,m=MI()
	UF=UnionFind(n)

	for _ in range(m):
		a,b=MI()
		UF.union(a-1,b-1)

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








if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# UnionFind、0-indexであることに注意
#############################################################


class UnionFind:

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

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################


N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.unite(a, b)

ans = 1
for i in range(N):
    s = uf.size(i)
    ans = max(ans, s)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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()}

N, M = mapint()
uf = UnionFind(N)
for _ in range(M):
    a, b = mapint()
    uf.union(a-1, b-1)

print(max([uf.size(r) for r in uf.roots()]))

Submission status: Accepted

Solution code:
class UFtree:
    def __init__(self,length):
        self.N=length
        self.tree=[-1 for i in range(length)]
        self.rank=[0 for i in range(length)]
    def find(self,X):
        if self.tree[X]<0:
            return X
        XX=self.find(self.tree[X])
        self.tree[X]=XX
        return XX

    def unite(self,X,Y):
        X=self.find(X)
        Y=self.find(Y)

        if Y==X:
            return

        if self.rank[X]>self.rank[Y]:
            self.tree[X]+=self.tree[Y]
            self.tree[Y]=X
        else:
            if self.rank[Y]==self.rank[X]:
                self.rank[Y]+=1
            self.tree[Y]+=self.tree[X]
            self.tree[X]=Y



def resolve():
    N,M = map(int,input().split())
    ut = UFtree(N)
    for i in range(M):
        A,B = map(int,input().split())
        ut.unite(A-1,B-1)

    print(-1*min(ut.tree))
resolve()

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["_size", "_first_idx", "_parents"]

    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), 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 get_size(self, x: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]


def main():
    import sys
    input = sys.stdin.readline

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

    uf = UnionFind(size=N)
    for _ in range(M):
        a, b = (int(x) - 1 for x in input().split())
        uf.unite(a, b)

    max_size = -1
    for i in range(N):
        if uf.find(i) == i:
            max_size = max(max_size, uf.get_size(i))
    print(max_size)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

class UnionFind(object):
    def __init__(self, n: int):
        """ ノードのつながりを辞書型で表現する
        要素数nであり、要素は0からn-1である想定
        >> - usage
        g = Graph(n=n)

        """
        self.adjacency_dict = {}
        self.parent = [None] * n

        for i in range(n):
            self.add_vertex(i)
            self.parent[i] = i
        self.rank = [0] * n

    def add_vertex(self, v: int):
        """ ノードを追加する """
        self.adjacency_dict[v] = []

    def unite(self, v1: int, v2: int):
        """ ノード同士をつなぐ。"""
        if v1 == v2:
            return

        # すでにつながっている場合は親の更新のみしておく
        if self.same(v1, v2):
            return

        p1 = self.parent[v1]
        p2 = self.parent[v2]

        # つながっていない場合は親同士をつなげる
        # その場合rankが小さい方から大きい方につなげる
        if self.rank[p1] == self.rank[p2]:
            self.update(p1, p2)
            self.rank[p2] += 1
        elif self.rank[p1] < self.rank[p2]:
            self.update(p1, p2)
        else:
            self.update(p2, p1)

    def update(self, v, parent):
        self.adjacency_dict[v].append(parent)

    def same(self, v1, v2):
        """ 親が同一であれば連結 """
        self.parent[v1] = self.root(v1)
        self.parent[v2] = self.root(v2)

        return self.parent[v1] == self.parent[v2]

    def root(self, v1):
        """ vから上向きに辿って根を調べる """
        if self.adjacency_dict[v1] == []:
            return v1

        for v in self.adjacency_dict[v1]:
            parent = self.root(v)
        return parent

    def print_graph(self):
        print(self.adjacency_dict)


u = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    u.unite(a, b)

dic = defaultdict(int)
ans = 0
for i in range(N):
    val = u.root(i)
    # print(i, val)
    dic[val] += 1
    ans = max(ans, dic[val])

print(ans)

Submission status: Accepted

Solution code:
import sys

class UnionFind():
    def __init__(self, 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 False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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


def solve():
    readline = sys.stdin.readline
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        A, B = map(int, readline().split())
        A -= 1
        B -= 1
        uf.union(A, B)
    print(-min(uf.parents))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#https://note.nkmk.me/python-union-find/
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())

def main():
    N,M = list(map(int,input().split()))
    ab = [list(map(int,input().split())) for i in range(M)]

    uf = UnionFind(N+1)
    for i in range(M):
        uf.union(ab[i][0],ab[i][1])
    print(max([uf.size(i) for i in range(1,N)]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

n, m = map(int,input().split())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

for _ in range(m):
  a, b = map(int,input().split())
  a -= 1
  b -= 1
  unite(a,b)
  
print(-min(par))