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:
import collections
import sys
import resource
sys.setrecursionlimit(1000000)

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

f = [x for x in range(n)]

def find(x):
  if f[x] == x:
    return x
  root = find(f[x])
  f[x] = root
  return root

for i in range(m):
  a, b = map(int, input().split(' '))
  a -= 1
  b -= 1
  if find(a) != find(b):
    f[find(a)] = find(b)

for i in range(n):
  find(i)
  
print(max(collections.Counter(f).values()))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
friends = [[] for _ in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  friends[a].append(b)
  friends[b].append(a)

check = [False] * N
ans = 0

for i in range(N):
  if check[i] == False:
    check[i] = True
    D = deque(friends[i])
    tmp = 1
    while D:
      f = D.popleft()
      if check[f] == False:
        check[f] = True
        tmp += 1
        for j in friends[f]:
          D.append(j)
    ans = max(ans, tmp)

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

        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 = [()] * M
for i in range(M):
    info[i] = map(int, input().split())

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

ans = min(uf.parents)

print(-ans)

Submission status: Accepted

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

def solve():
    class UnionFindVerSize():
        def __init__(self, N):
            """ N個のノードのUnion-Find木を作成する """
            # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
            self._parent = [n for n in range(0, N)]
            # グループのサイズ（個数）
            self._size = [1] * N

        def find_root(self, x):
            """ xの木の根(xがどのグループか)を求める """
            if self._parent[x] == x: return x
            self._parent[x] = self.find_root(self._parent[x]) # 縮約
            return self._parent[x]

        def unite(self, x, y):
            """ xとyの属するグループを併合する """
            gx = self.find_root(x)
            gy = self.find_root(y)
            if gx == gy: return

            # 小さい方を大きい方に併合させる（木の偏りが減るので）
            if self._size[gx] < self._size[gy]:
                self._parent[gx] = gy
                self._size[gy] += self._size[gx]
            else:
                self._parent[gy] = gx
                self._size[gx] += self._size[gy]

        def get_size(self, x):
            """ xが属するグループのサイズ（個数）を返す """
            return self._size[self.find_root(x)]

        def is_same_group(self, x, y):
            """ xとyが同じ集合に属するか否か """
            return self.find_root(x) == self.find_root(y)

        def calc_group_num(self):
            """ グループ数を計算して返す """
            N = len(self._parent)
            ans = 0
            for i in range(N):
                if self.find_root(i) == i:
                    ans += 1
            return ans

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

    # 求める答えは、最大グループ数の人数に等しい。
    ans = 0
    for i in range(N):
        ans = max(ans, uf.get_size(i))

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    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 x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

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


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

u = UnionFind(N+1)

for i in range(M):
    A, B = map(int, input().split())
    u.union(A, B)

print(max([u.get_size(i) for i in range(1, N+1)]))

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

uf = UnionFind(N+1)

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

print(max(uf.size(num) for num in uf.roots()))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
 
root = [-1]*n
def r(x):
    if root[x] < 0:
        return x
    else:
        root[x] = r(root[x])
        return root[x]
 
def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x
 
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)
 
ans = 0
for i in range(n):
    ans = max(ans, -root[i])
 
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():

    def __init__(self, N):
        # parent of each node
        self.parent = [n for n in range(N)]

        # number of nodes in union
        self.rank = [1] * N
        
    def find(self, u):
        if self.parent[u] == u:
            return u
        else:
            # recursive call
            return self.find(self.parent[u])
    
    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)

        # same union
        if pu == pv: 
            return

        # let pv join into pu union 
        if self.rank[pu] < self.rank[pv]:
            pu, pv = pv, pu

        self.rank[pu] += self.rank[pv]
        self.parent[pv] = pu
 
N, M = map(int, input().split())
UF = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    UF.union(A, B)


ret = 0

for n in range(N):
    ret = max(ret, UF.rank[n])

print(ret)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def readInt():
    return list(map(int, input().split()))

n, m = readInt()

root = [-1] * n

def r(x):
    # print("root[x]=",root[x])
    if root[x] < 0:
        # print("r(x)=",x)
        return x
    else:
        root[x] = r(root[x])
        # print(root[x])
        return root[x]

def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x
    # print(root)

def size(x):
    x = r(x)
    # print(x, root[x])
    return -root[x]

for i in range(m):
    x, y = readInt()
    x -= 1
    y -= 1
    unite(x, y)

max_size = 0

for i in range(n):
    max_size = max(max_size, size(i))

print(max_size)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, N):
        self.N = N
        self.par = [n for n in range(N)]
        self.rank = [1] * N
        
    def find(self, u):
        if self.par[u] == u:
            return u
        else:
            return self.find(self.par[u])
    
    def union(self, u, v):

        pu = self.find(u)
        pv = self.find(v)

        if pu == pv: 
            return

        if self.rank[pu] < self.rank[pv]:
            self.par[pu] = pv
            self.rank[pv] += self.rank[pu]

        else: # self.rank[pu] > self.rank[pv]
            self.par[pv] = pu
            self.rank[pu] += self.rank[pv]
 
N, M = map(int, input().split())
UF = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    UF.union(A, B)


ret = 0

for n in range(N):
    ret = max(ret, UF.rank[n])

print(ret)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    # xの属する木の根を求める
    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 = 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
    
    # xの属する集合の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]
    
    # xとyが同じ集合に属するかを判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    # 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.parents) if x < 0]
    
    # グループ数を返す
    def group_count(self):
        return len(self.roots())
    
    # groupとそれに属するメンバーの辞書を返す
    # exp. {0: [0, 1, 4], 2: [2, 3]}
    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())

union = UnionFind(N)

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

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

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 {root: self.members(root) for root in self.roots()}

    def __str__(self):
        return '\n'.join(f'{root}: {self.members(root)}' for root in self.roots())


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

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

print(max(uf.size(i) for i in range(N)))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
data2 = []
for i in range(m):
    data2.append(input().split())

graph = [[] for i in range(n)]
for i in range(0,m):
    a, b = map(lambda z: int(z) - 1, data2[i])
    graph[a].append(b)
    graph[b].append(a)

size = [0 for i in range(n)]
check = [True for i in range(n)]
for i in range(n):
    if check[i]:
        tmp = 1
        stack = [i]
        check[i] = False
        while stack:
            now = stack.pop()
            size[now] = tmp
            tmp += 1
            for to in graph[now]:
                if check[to]:
                    check[to] = False
                    stack.append(to)
print(max(size))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from collections import deque
from functools import *
from fractions import Fraction as f
from copy import *
from bisect import *	
from heapq import *
#from math import *
from itertools import permutations ,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def inc(d,c):
	d[c]=d[c]+1 if c in d else 1
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<n	
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)


t=1
def find(a,i):
	if i==a[i]:
		return a[i]
	a[i]=find(a,a[i])
	return a[i]
def union(a,x,y):
	xs=find(a,x)
	ys=find(a,y)
	if xs!=ys:
		if rank[xs]<rank[ys]:
			xs,ys=ys,xs
		a[ys]=xs
		rank[xs]+=1			

while t>0:
	t-=1
	n,m=mi()
	a=[i for i in range(n+1)]
	rank=[0]*(n+1)
	for i in range(m):
		x,y=mi()
		union(a,x,y)
	d=[0]*(n+1)	
	for i in range(1,n+1):	
		a[i]=find(a,i)
		d[a[i]]+=1
	print(max(d))

Submission status: Accepted

Solution code:
import sys


def union(parent, rank, i, j):
    i_id = find(parent, i)
    j_id = find(parent, j)

    if i_id == j_id:
        return
    if rank[i_id] > rank[j_id]:
        parent[j_id] = i_id
    else:
        parent[i_id] = j_id
        if rank[i_id] == rank[j_id]:
            rank[j_id] += 1

def find(parent, i):
    v = list()
    while i != parent[i]:
        i = parent[i]
        v.append(i)
    for j in v:
        parent[j] = i
    return i


def main():
    input = sys.stdin.read()
    data = list(map(int, input.split()))

    n, m = data[0], data[1]
    rank = [0]*(n+1)
    parent = [i for i in range(n+1)]

    for i in range(2,len(data)-1,2):
        union(parent, rank, data[i], data[i+1])

    s = [0]*(n+1)

    # data = data[2:]
    # print(data)

    for i in range(1,n+1):
        s[find(parent,i)] += 1
        # print(i, find(parent, i))

    print(max(s))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.d = [-1] * n
  
  def find(self, x):
    if (self.d[x] < 0):
      return x
    else:
      self.d[x] = self.find(self.d[x])
      return self.d[x]
  
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if (x == y): return
    if (self.d[x] > self.d[y]):
      x, y = y, x
    self.d[x] += self.d[y]
    self.d[y] = x
  def same(self, x, y): return self.find(x) == self.find(y)
  def size(self, x): return -self.d[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)
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())

class unionfind():
    def __init__(self,n):
        self.li = [-1]*(n+1)

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return;
        if x>y:
            x, y = y, x
        self.li[x]+=self.li[y]
        self.li[y] = x

x = unionfind(n)
ans = 0
for _ in range(m):
    a,b = map(int,input().split())
    x.union(a,b)
print(-min(x.li))

Submission status: Accepted

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

class unionfind():
    def __init__(self,n):
        self.li = [i for i in range(n+1)]
        self.group = [1]*(n+1)

    def find(self, x):
        while self.li[x]!=x:
            x = self.li[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return;
        elif x>y:
            self.li[y] = x
            self.group[x] += self.group[y]
        else:
            self.li[x] = y
            self.group[y] += self.group[x]
x = unionfind(n)
ans = 0
for _ in range(m):
    a,b = map(int,input().split())
    x.union(a,b)
print(max(x.group))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a, b = [], []
for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  a.append(_)
  b.append(__)
  
# union-find

# 誰の肩に手を置いているか（先頭の場合は-1）
parent = [-1 for i in range(n)]

# 列車の深さ
depth = [0 for i in range(n)]

# kさんの「運転手」が誰かを調べる関数
def find_root(k):
  while parent[k] != -1:
    k = parent[k]
  return k 

for i in range(m):
  # a[i] と b[i] の合併
  root_a = find_root(a[i])
  root_b = find_root(b[i])
  if root_a == root_b: continue
  
  # 浅い列車を持っている方が負けるようにする
  if depth[root_a] > depth[root_b]:
    root_a, root_b = root_b, root_a
  parent[root_a] = root_b
  depth[root_b] = max(depth[root_a]+1, depth[root_b])
  
group = [find_root(i) for i in range(n)]

from collections import Counter
print(Counter(group).most_common()[0][1])

Submission status: Accepted

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

# 隣接リストをつくる 
adj_list = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  adj_list[a].append(b)
  adj_list[b].append(a)
  
# どの連結成分に属してるかを把握するための配列
group = [-1 for i in range(n)]

# 各頂点 i から探索をする
for i in range(n):
  if group[i] != -1: continue
  # i から DFS
  newly_visited = [i]
  group[i] = i
  while len(newly_visited) > 0:
    now = newly_visited.pop()
    for j in adj_list[now]:
      if group[j] != -1: continue
      newly_visited.append(j)
      group[j] = i

hist = [0 for i in range(n)]
for g in group:
  hist[g] += 1
print(max(hist))

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())
uf=UnionFind(n)
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a-1, b-1)
cnt=0
for i in range(n):
    cnt=max(cnt, uf.size(i))
print(cnt)

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 = list(map(int,input().split()))
uf = UnionFind(N)
for _ in range(M):
  A,B = list(map(int,input().split()))
  uf.union(A-1,B-1)
print(abs(min(uf.parents)))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self._n = n
        self._table = [-1]*n

    def _root(self, x):
        stack = []
        while self._table[x] >= 0:
            stack.append(x)
            x = self._table[x]
        for y in stack:
            self._table[y] = x
        return x
    
    def unite(self, x, y):
        x, y = self._root(x), self._root(y)
        if x == y:
            return
        if x > y:
            x, y = y, x
        self._table[x] += self._table[y]
        self._table[y] = x

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

    def count_members(self, x):
        return -self._table[self._root(x)]

    def count_groups(self):
        return len({self._root(i) for i in range(self._n)})

    def __iter__(self):
        return (self._root(i) for i in range(self._n))

    def __str__(self):
        return str([self._root(i) for i in range(self._n)])

    def __repr__(self):
        return repr([self._root(i) for i in range(self._n)])

n, m, *AB = map(int, open(0).read().split())
uf = UnionFind(n)
for a, b in zip(AB[::2], AB[1::2]):
    uf.unite(a-1, b-1)
print(max(uf.count_members(group) for group in set(uf)))

Submission status: Accepted

Solution code:

n,m=map(int,input().split())
parent=[*range(n)]
sz=[1]*n


def anc(a):
	# print(a)
	if parent[a]==a:
		return a
	else:
		return(anc(parent[a]))


def union(a,b):
	pa=anc(a)
	pb=anc(b)
	if sz[pb]<sz[pa]:
		pa,pb=pb,pa
	parent[pa]=pb
	sz[pb]+=sz[pa]
	sz[pa]=0


# print(parent)
for i in range(m):
	a,b=map(int,input().split())
	a-=1
	b-=1
	if anc(a)!=anc(b):
		union(a,b)
	# print(parent,a,b)

print(max(sz))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self._n = n
        self._table = [-1]*n

    def _root(self, x):
        stack = []
        while self._table[x] >= 0:
            stack.append(x)
            x = self._table[x]
        for y in stack:
            self._table[y] = x
        return x
    
    def unite(self, x, y):
        x, y = self._root(x), self._root(y)
        if x == y:
            return
        if x > y:
            x, y = y, x
        self._table[x] += self._table[y]
        self._table[y] = x
    
    def same(self, x, y):
        return self._root(x) == self._root(y)

    def count_members(self, x):
        return -self._table[self._root(x)]
    
    def count_groups(self):
        return len({self._root(i) for i in range(self._n)})
    
    def __str__(self):
        return str([self._root(i) for i in range(self._n)])
    
    def __repr__(self):           
        return repr([self._root(i) for i in range(self._n)])

n, m, *AB = map(int, open(0).read().split())
uf = UnionFind(n)
for a, b in zip(AB[::2], AB[1::2]):
    uf.unite(a-1, b-1)
print(max(uf.count_members(group) for group in {uf._root(i) for i in range(n)}))

Submission status: Accepted

Solution code:
class Union_Find():
    def __init__(self, N):
        self.N = N
        self.par = [n for n in range(N)]
        self.rank = [0] * N
        
    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            return self.root(self.par[x])
    
    def same(self, x, y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
    
    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.rank[y] += self.rank[x] + 1
        else:
            self.par[y] = x
            self.rank[x] += self.rank[y] + 1

N, M = map(int, input().split())
UF = Union_Find(N)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    UF.unite(a, b)
ans = -1
for n in range(N):
        ans = max(ans, UF.rank[n])
print(ans+1)

Submission status: Accepted

Solution code:
from _collections import deque

n,m=map(int,input().split())
f=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)
g=[0]*(n+1)
p=[0]*(n+1)
for i in range(1,n+1):
    if p[i]==0:
        p[i]=i
        data=[i]
        data=deque(data)
        while len(data)>0:
            pos=data.popleft()
            p[pos]=i
            for j in f[pos]:
                if p[j]==0:
                    p[j]=i
                    data.append(j)
for i in range(n):
    g[p[i+1]]+=1
print(max(g))

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=list(map(int,input().split()))
g=UnionFind(n)
ans=0
for i in range(m):
    a,b=list(map(int,input().split()))
    a-=1;b-=1
    g.union(a,b)

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

Submission status: Accepted

Solution code:
class union:
  def __init__(self, box):
    self.r = []
    for i in range(box):
      self.r.append(-1)
    
  def root(self, x):
    if self.r[x] < 0:
      return x
    self.r[x] = self.root(self.r[x])
    return self.r[x]

  def add(self, a):
    a[0] -= 1
    a[1] -= 1
    a[0] = self.root(a[0])
    a[1] = self.root(a[1])
    if a[0] == a[1]:
      return False
    if self.r[a[0]] > self.r[a[1]]:
      a[0], a[1] = a[1], a[0]
    self.r[a[0]] += self.r[a[1]]
    self.r[a[1]] = a[0]
    return True
  
  def size(self, x):
    return -self.r[x]

n, m = map(int, input().split())
uf = union(n)
ans = 0
for i in range(m):
  uf.add(list(map(int, input().split())))

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__ (self,n):
        self.parent = [i for i in range (n)]
        self.height = [0 for _ in range (n)]

    def get_root(self,i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.get_root(self.parent[i])
            return self.parent[i]

    def unite(self,i,j):
        root_i = self.get_root(i)
        root_j = self.get_root(j)
        if root_i != root_j:
            if self.height[root_i] < self.height[root_j]:
                self.parent[root_i] = root_j
            else:
                self.parent[root_j] = root_i
                if self.height[root_i] == self.height[root_j]:
                    self.height[root_i] += 1

    def is_in_group(self,i,j):
        if self.get_root(i) == self.get_root(j):
            return True
        else:
            return False

def main():
    N,M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range (M):
        A,B = map(lambda x: int(x)-1,input().split())
        uf.unite(A,B)

    check = [0]*N
    for i in range(N):
        check[uf.get_root(i)] += 1
    print(max(check))


main()