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:
from collections import defaultdict

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

graph = defaultdict(set)
for i in range(M):
    a,b = map(int, input().split(' '))
    graph[a].add(b)
    graph[b].add(a)

ans = 1
vis_set = set()

for start in graph:
    if start in vis_set:
        continue
    count = 0
    stack = [start]
    vis_set.add(start)
    while len(stack) > 0:
        cur = stack.pop()
        count += 1
        for adj in graph[cur]:
            if adj not in vis_set:
                stack.append(adj)
                vis_set.add(adj)

    ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().rstrip().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

def dfs(x):
    stack = [x]
    visited = 0
    checked[x] = 1
    while stack:
        visited += 1
        node = stack.pop()
        for i in graph[node]:
            if checked[i] == 0:
                stack.append(i)
                checked[i] = 1
    return visited
 
n, m = inm()
checked = [0] * (n+1)
graph = {}
for i in range(m):
    a, b = inm()
    if a not in graph:
        graph[a] = set()
    if b not in graph:
        graph[b] = set()
    graph[a].add(b)
    graph[b].add(a)
ans = 1
for i in graph:
    if checked[i] == 0:
        ans = max(ans, dfs(i))
print(ans)

Submission status: Accepted

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


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

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

#True:訪問済み False:未訪問
flag = [False]*n

res = 0

for i in range(n):
    if flag[i]:
        continue

    size = 0
    #tank element : 行く候補
    tank = [i]
    while len(tank) > 0:
        now = tank.pop()
        if flag[now]:
            continue
        flag[now] = True
        size += 1

        #今見てる点と繋がっているかつ未訪問の点を候補に追加
        for nxt in edge[now]:
            if not flag[nxt]:
                tank.append(nxt)
    
    res = max(res,size)

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

    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)

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

Submission status: Accepted

Solution code:
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[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
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, m = map(int, sys.stdin.buffer.readline().split())
    uf = UnionFind(n)
    for x in sys.stdin.buffer.readlines():
        a, b = map(int, x.split())
        uf.union(a-1, b-1)

    grp = {}
    for i in range(n):
        grp.setdefault(uf._root(i), []).append(i)

    ans = 0
    for x in grp.values():
        l = len(x)
        if ans < l:
            ans = l
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

        if x == y:
            return
        else:
            if self.rank[x] <self.rank[y]:
                self.par[y] += self.par[x] # 負+負でsize管理 
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]: # 負+負でsize管理 
                    self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

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

N,M = list(map(int,input().split()))
Tree = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    Tree.union(a-1,b-1)
print(-min(Tree.par))

Submission status: Accepted

Solution code:
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[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
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


n, m = map(int, sys.stdin.buffer.readline().split())
uf = UnionFind(n)
for x in sys.stdin.buffer.readlines():
    a, b = map(int, x.split())
    uf.union(a-1, b-1)

grp = {}
for i in range(n):
    grp.setdefault(uf._root(i), []).append(i)

ans = 0
for x in grp.values():
    l = len(x)
    if ans < l:
        ans = l
print(ans)

Submission status: Accepted

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

par = [i + 1 for i in range(n)]
rank = [1] * n
size = [1] * n

def find(x):
    if par[x - 1] == x:
        return x
    else:
        return find(par[x - 1])

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x - 1] < rank[y - 1]:
        par[x - 1] = y
        size[y - 1] += size[x - 1]
    else:
        par[y - 1] = x
        size[x - 1] += size[y - 1]
        if rank[x - 1] == rank[y - 1]:
            rank[x - 1] += 1

for i in range(m):
    a, b = map(int, input().split())
    union(a, b)

print(max(size))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
    a,b=map(int,input().split())
    d[a].add(b)
    d[b].add(a)

vis = set()
res = 0
for i in range(1,n+1):
    if i not in vis:
        stack=[i]
        ans=1
        vis.add(i)
        while stack:
            cur=stack.pop()
            for j in d[cur]:
                if j not in vis:
                    vis.add(j)
                    ans+=1
                    stack.append(j)
        res=max(res,ans)
print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
friends = {i: set([]) for i in range(N)}
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].add(b)
    friends[b].add(a)
#print(friends)
from collections import deque

reached = [-1] * N
ans = 1
for i in range(N):
    if reached[i] == -1:
        queue = deque()
        queue.append(i)
        t = 1
        reached[i] = 0
        while len(queue) > 0:
            v = queue.popleft()
            for n in friends.get(v):
                if reached[n] == -1:
                    reached[n] = 0
                    queue.append(n)
                    t += 1
    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
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)

#print(neighbor)
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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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

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

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

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

    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = MAP()
    
    tree = UnionFind(N)
    for _ in range(M):
        a, b = MAP()
        tree.union(a - 1, b - 1)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
s = input().split()
n = int(s[0]) 
m = int(s[1])
graph = defaultdict(set)
for i in range(m):
    s = input().split(" ")
    graph[int(s[0])].add(int(s[1]))
    graph[int(s[1])].add(int(s[0]))

visited = [False] * (n+1)

def bfs (node):
    queue = [node]  
    ans = 0
    visited[node] = True
    while queue:
        root = queue.pop()
        ans +=1
        
        for child in graph[root]:
            if not visited[child]:
                queue.append(child)
                visited[child]  =True
    return ans

ans  = 0
for i in range(1, n+1):
    if not visited[i]:
        ans = max(ans, bfs(i))
print( ans)

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

    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

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

n,m = map(int,input().split())
uf1=UnionFind(n)
for i in range(m):
    a,b=map(int, input().split())
    uf1.union(a-1,b-1)

for i in range(n):uf1.find(i)
X = uf1.par

ans = [0]*n
for i in range(n):
    ans[X[i]] += 1

print(max(ans))

Submission status: Accepted

Solution code:
# UnionFind

# 配列で、子のID番目:(親のID), 親のID番目:(その塊の-サイズ)
# Union Findを使う
class UnionFind:
    def __init__(self, size):
        self.parent_indexes = [-1] * size
        
    def find_parent(self, n):
#         print(self.parent_indexes[n])
        if self.parent_indexes[n] < 0:
            return n
#         print('hewe')
        # 探しているnodeが指し示しているのが現在の親ではない場合、
        # 現在の親に書き換え(memo化)た上で返す
        self.parent_indexes[n] = self.find_parent(self.parent_indexes[n])
        return self.parent_indexes[n] 
    
    def union(self, n1, n2):
        if self.same_group(n1, n2):
            return False
        
        # サイズの大きい方の親が親であり続ける
        if self.size(n1) >= self.size(n2):
            tmp = self.size(n2)
            self.parent_indexes[self.find_parent(n2)] = self.find_parent(n1)
            self.parent_indexes[self.find_parent(n1)] -= tmp
            return True
        
        tmp = self.size(n1)
        self.parent_indexes[self.find_parent(n1)] = self.find_parent(n2)
        self.parent_indexes[self.find_parent(n2)] -= tmp
        return True
        
    
    def size(self, n):
        return -self.parent_indexes[self.find_parent(n)]
    
    def same_group(self, n1, n2):
        return self.find_parent(n1) == self.find_parent(n2)



n, m = map(lambda x: int(x), input().split())
uf = UnionFind(n)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    uf.union(a-1, b-1)
    
print(-min(uf.parent_indexes))

Submission status: Accepted

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

def root(x):
    if rank[x] < 0: return x
    rank[x] = root(rank[x])
    return rank[x]

def unite(x, y):
    x, y = root(x), root(y)
    if x == y: return False
    if rank[x] > rank[y]: x, y = y, x
    rank[x] += rank[y]
    rank[y] = x
    return True

def size(x):
    return -rank[root(x)]


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

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

Submission status: Accepted

Solution code:
# from pprint import pprint
#
# N, M = map(int, input().split())
#
# G = [[0 for _ in range(N)] for _ in range(N)]
#
# for _ in range(M):
#     a, b = list(map(int, input().split()))
#     G[a-1][b-1] = G[b-1][a-1] = 1
#
# pprint(sum(sum(g) for g in G) // 2)

from collections import Counter

class UnionFindBasic():
    """via https://note.nkmk.me/python-union-find/
    """
    def __init__(self, n: int):
        # < 0 は根
        self.n = n
        self.parents = [-1] * n

    def find(self, x: int) -> int:
        if self.parents[x] < 0:
            return x
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x: int, y: int):
        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 main():
    N, M = map(int, input().split())

    if M == 0:
        print(1)
        return

    uf = UnionFindBasic(N)

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        # -1で親がいないことを示す
        self.parents = [-1] * (n+1)
        # unionの大きさ
        self.size = [1]*(n+1)

    def find(self,x):
        # 親がいない＝＞代表元xを返却
        if self.parents[x] == -1:
            return x
        else:
            # 親を辿って代表元を取得して自分の親も代表元にする
            self.parents[x]=self.find(self.parents[x])
            # それを返す
            return self.parents[x]

    def unite(self,x,y):

        xRoot = self.find(x)
        yRoot = self.find(y)

        if xRoot == yRoot:
            return

        # 今回は一つのユニオンの大きさが問題となるので、更新する
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

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

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

print(max(tree.size))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        # 自身の数で親がいないことを示す
        self.parents = [i for i in range(n+1)]
        # unionの大きさ
        self.size = [1]*(n+1)

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

    def unite(self,x,y):
        
        xRoot = self.find(x)
        yRoot = self.find(y)

        if xRoot == yRoot:
            return

        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

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

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

print(max(tree.size))

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): uf.union(*map(lambda x: int(x)-1, input().split())) # unite
ans = 0
for i in range(n): ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
def main():
 
    def find(target):
        if parent[target] < 0:
            return target
        else:
            parent[target] = find(parent[target])
            return parent[target]
 
    def is_same(x, y):
        return find(x) == find(y)
 
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x == root_y:
            return
        if parent[root_x] > parent[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_x] += parent[root_y]
        parent[root_y] = root_x

    def members(n, x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]
 
    def get_size(x):
        return -parent[find(x)]
 
    def get_root():
        return [i for i, root in enumerate(parent) if root < 0]

    n, m = map(int, input().split())
    parent = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        union(a, b)
        # print(parent)
    ans = 0
    for i in range(n):
        ans = max(ans, get_size(i))
    print(ans)
    # 状況理解用
    # max_member = 0
    # for i in get_root():
    #     # print(i, members(n, i))
    #     max_member  = max(max_member, len(members(n, i)))
    # print(max_member)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from bisect import bisect_left


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

def bindex(a,x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return i
    return None

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)


class UnionFind:
    def __init__(self, n):
        self.r = [-1]*(n+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 unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] > self.r[y]:
            x,y = y,x
        self.r[x] += self.r[y]
        self.r[y] = x
        return True

    def size(self, x):
        return -1 * self.r[self.root(x)]



if __name__ == '__main__':
    # N, M = mulinputs()
    # b = [None] * (N+1)
    # for _ in range(M):
    #     A, B = map(int,input().split())
    #     if not b[A] and b[B]:
    #         b[B].add(A)
    #         b[A] = b[B]
    #     elif b[A] and not b[B]:
    #         b[A].add(B)
    #         b[B] = b[A]
    #     elif not b[A] and not b[B]:
    #         t = set([A,B])
    #         b[A] = t
    #         b[B] = t
    #     else:
    #         b[A].add(B)
    #         b[B].add(A)
    # # 出力
    # ans = 1
    # for bb in b:
    #     if not bb:
    #         continue
    #     ans = max(ans, len(bb))
    # print(ans)

    N, M = mulinputs()
    uf = UnionFind(N)
    for _ in range(M):
        A, B = map(int,input().split())
        uf.unite(A, B)
    ans = 1
    for r in uf.r:
        ans = max(ans, -1*r)
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())

root = [-1]*n

def find(n):
    if root[n] < 0:
        return n
    else:
        root[n] = find(root[n])
        return root[n]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    else:
        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)

print(-min(root))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())

root = [-1]*n

def find(n):
    if root[n] < 0:
        return n
    else:
        root[n] = find(root[n])
        return root[n]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    else:
        root[x] += root[y]
        root[y] = x

def size(n):
    return -root[find(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

print(-min(root))

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n,m = (int(x) for x in input().split())
graph = [set() for _ in xrange(n)]
for _ in xrange(m):
    a,b = (int(x)-1 for x in input().split())
    graph[a].add(b)
    graph[b].add(a)

visited = [False for _ in xrange(n)]
ans = 0
for i in xrange(n):
    if visited[i]:
        continue
    
    stack = [i,]
    cnt = 1
    while stack:
        node = stack.pop()
        if visited[node]:
            continue
        visited[node] = True
        cnt += 1
        for next_node in graph[node]:
            stack.append(next_node)
    ans = max(cnt,ans)
print(ans-1)