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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])
        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g

@mt
def slv(N, M, AB):
    uf = UnionFind()
    p = set()
    for a, b in AB:
        uf.union(a, b)
        p.add(a)
        p.add(b)

    ans = 1
    for c in p:
        ans = max(ans, uf.size(c))
    return ans


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


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_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(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 Count(self, x):
        return -self.root[self.Find_Root(x)]


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

for i in range(M):
    A,B = map(int,input().split())
    A -= 1; B -= 1
    UF.Unite(A,B)
ans = 0
for i in range(N):
    ans = max(ans,UF.Count(i))

print(ans)

Submission status: Accepted

Solution code:
# union find
def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])


def unite(x, y):
    '''x,yの属する集合の併合'''
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


def roots():
    '''rootリストを返す'''
    roots = []
    for i in range(N):
        roots.append(find_root(i))
    return roots


def group_size(x):
    '''xが所属するグループのサイズ'''
    return size[find_root(x)]


# 入力
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

# 初期化
parent = [i for i in range(N)]  # 根
rank = [1] * N  # 深さ
size = [1] * N  # iを根とするグループのサイズ

# 前処理
edge = [[ab[M - 1 - i][0] - 1, ab[M - 1 - i][1] - 1] for i in range(M)]

# 結合
for i in range(M):
    unite(edge[i][0], edge[i][1])

ans = 0
for i in range(N):
    ans = max(ans, group_size(i))
print(ans)

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 1
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"

def UnionFind(n):
    a = n
    while a != groups[a]:
        a = groups[a]
    groups[n] = a
    return a

n,m = I()
groups = [x for x in range(n)]
count = [0]*n

for _ in range(m):
    x,y = I()
    x,y = UnionFind(x-1), UnionFind(y-1)
    if x != y:
        groups[y] = x

for i in range(n):
    count[UnionFind(i)] += 1

print(max(count))

Submission status: Accepted

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

for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    
    f[a].append(b)
    f[b].append(a)
    
import collections
q = collections.deque()

for i in range(n):
    for j in f[i]:
        q.append(j)
        
    while q:
        p = q.popleft()
        
        if p != i:
            f[i] += f[p]

            for k in f[p]:
                q.append(k)

            f[p] = []
        
    f[i] = sorted(set(f[i]))
            
ans = 1

for i in f:
    res = len(i)
    ans = max(ans,res)
    
print(ans)

Submission status: Accepted

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

for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    
    f[a].append(b)
    f[b].append(a)
    
import collections
q = collections.deque()

for i in range(n):
    for j in f[i]:
        q.append(j)
        
    while q:
        p = q.popleft()
        
        if p != i:
            f[i] += f[p]

            for k in f[p]:
                q.append(k)

            f[p] = []
        
    f[i] = sorted(set(f[i]))
            
ans = 1

for i in f:
    res = len(i)
    ans = max(ans,res)
    
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root


def main():
    N,M = MI()
    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes

    for _ in range(M):
        A,B = MI()
        unite(A-1,B-1)

    ans = 0
    for i in range(N):
        ans = max(ans, -nodes[get_root(i)])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

uf = UnionFind(N)
for i in range(M):
    uf.unite(L[i][0]-1, L[i][1]-1)

team = {}
for i in range(N):
    tmp = uf.find(i)
    if tmp not in team:
        team[tmp] = 1
    else:
        team[tmp] += 1

ans = 0
for k, v in team.items():
    ans = max(ans, v)

print(ans)

Submission status: Accepted

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [int(x) for x in range(n)]
        self.tree_size = [1 for _ in range(n)]

    def unite(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)

        if self.same(x_root, y_root):
            return

        if self.size(x_root) >= self.size(y_root):
            self.parent[y_root] = x_root
            self.tree_size[x_root] += self.tree_size[y_root]
        else:
            self.parent[x_root] = y_root
            self.tree_size[y_root] += self.tree_size[x_root]

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

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

    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False


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

# print([uf.size(i) for i in range(n)])
print(max([uf.size(i) for i in range(n)]))

Submission status: Accepted

Solution code:
class Union:
    def __init__(self, n):
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.root(self.parents[x])
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

uni = Union(n)
for a, b in ab:
    a -= 1
    b -= 1
    uni.unite(a, b)
print(-min(uni.parents))

Submission status: Accepted

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [int(x) for x in range(n)]
        self.tree_size = [1 for _ in range(n)]

    def unite(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)

        if self.same(x_root, y_root):
            return

        if self.size(x_root) >= self.size(y_root):
            self.parent[y_root] = x_root
            self.tree_size[x_root] += self.tree_size[y_root]
        else:
            self.parent[x_root] = y_root
            self.tree_size[y_root] += self.tree_size[x_root]

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

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

    def same(self, x, y):
        if x == y:
            return True
        else:
            return False


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

# print([uf.size(i) for i in range(n)])
print(max([uf.size(i) for i in range(n)]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]

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

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

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

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

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

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

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

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

    def all_group_members(self):  # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {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)
for i in range(M):
    uf.union(AB[i][0] - 1, AB[i][1] - 1)
l = []
for i in range(N):
    l.append(uf.size(i))
print(max(l))

Submission status: Accepted

Solution code:
N,M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0

for AB in ABs:
    unite(AB[0],AB[1])
print(max(size))

Submission status: Accepted

Solution code:
#親要素を示す
par = {}
size_list = []

# 初期化 -- すべての要素が根である --
def init(n):
    for i in range(n):
        par[i] = i
        size_list.append(1)
    return 

# 根を求める
def root(x):
    if par[x] == x:
        return x
    else:
        #根の直下にxを置く
        par[x] = root(par[x])
        return par[x]

#　同じ集合に属するかどうかは根が同じかで判定
def same(x, y):
    return root(x) == root(y)

#　別々のUnion同士を融合する
def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        par[x] = y
        size_list[y] += size_list[x]
        size_list[x] = 0
        return


N, M = map(int, input().split())
init(N)
for mi in range(M):
    a, b = map(int, input().split())
    unite(a-1,b-1)
print(max(size_list))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self):
        self.data = {}
        self.heights = {}
        self.sizes = {}

    def get_num_trees(self):
        return len(self.heights)

    def get_tree_size(self, a):
        return self.sizes[self.get_root(a)]

    def add_node(self, a):
        self.data[a] = a
        self.heights[a] = 1
        self.sizes[a] = 1

    def get_root(self, a):
        nodes = [a]
        while nodes[-1] not in self.heights:
            nodes.append(self.data[nodes[-1]])
        for x in nodes:
            self.data[x] = nodes[-1]
        return nodes[-1]

    def union(self, a, b):
        root_a = self.get_root(a)
        root_b = self.get_root(b)
        if root_a == root_b:
            return
        if self.heights[root_a] > self.heights[root_b]:
            a, b = b, a
            root_a, root_b = root_b, root_a
        self.data[root_a] = root_b
        self.heights[root_b] = max(self.heights.pop(root_a) + 1, self.heights[root_b])
        self.sizes[root_b] += self.sizes.pop(root_a)

    def find(self, a, b):
        return self.get_root(a) == self.get_root(b)


N, M = map(int, input().split())
uf = UnionFind()
for i in range(1, N + 1):
    uf.add_node(i)

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

print(max(uf.sizes.values()))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

from collections import Counter
N,M=map(int,input().split())
ufbs=UnionFind(N)
for _ in range(M):
    A,B=map(int,input().split())
    ufbs.union(A-1,B-1)
ans=0
for x in ufbs.roots():
    ans=max(ans,ufbs.size(x))
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)



n,m = map(int, input().split())
f = []

for x in range(m):
    ff = []
    a,b = map(int, input().split())
    ff.append(a)
    ff.append(b)
    f.append(ff)

uf = UnionFind(n)

for i in range(m):
    a = f[i][0] - 1
    b = f[i][1] - 1
    uf.union(a, b)

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

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
graph = [[] for i in range(n)]
for i in range(m):
  a,b = map(lambda z:int(z)-1,input().split())
  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:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for i in range(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=[int(i) for i in input().split(" ")]
uf = UnionFind(N)
for i in range(M):
    A,B=[int(i) for i in input().split(" ")]
    uf.union(A-1,B-1)

d={}
for i in range(N):
    root = uf.find(i)
    d[root]=d.get(root,0)+1

print(max(d.values()))

Submission status: Accepted

Solution code:
import sys,os
import math
from fractions import Fraction 
from collections import defaultdict
from random import randint

# sys.stderr=open('err.txt','w')
# sys.stdout=open('output.txt','w')
# sys.stdin=open('input.txt','r')

def linput():
    return list(minput())

def minput():
    return map(int, sys.stdin.readline().strip().split())

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

def make_set(a):
    parent[a]=a
    sizen[a]=1

def find_set(a):
    if parent[a]==a:
        return a
    parent[a]=find_set(parent[a])
    return parent[a]

def union_set(a,b):
    x=find_set(a)
    y=find_set(b)
    if x==y:
        return
    else:
        if sizen[x]>sizen[y]:
            parent[y]=x
            sizen[x]+=sizen[y]
        else:
            parent[x]=y
            sizen[y]+=sizen[x]

n,m=minput()
parent=[0]*n
sizen=[0]*n
for i in range(n):
    make_set(i)
ans=0
for i in range(m):
    x,y=minput()
    if x>y:
        x,y=y,x
    x=x-1
    y=y-1
    union_set(x,y)
# print(parent)
di = defaultdict(int)
# for i in parent:
#     di[i]+=1
# print(di)

for v in sizen:
    ans=max(ans,v)
print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, M = map(int, input().split())
# A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# A_B = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# edges = [list(map(int,input().split())) for _ in range(M)]
# tree = [[] for _ in range(N + 1)]

# for edge in edges:
#     tree[edge[0]].append([edge[1], edge[2]])
#     tree[edge[1]].append([edge[0], edge[2]])

# depth = [-1] * (N + 1)
# depth[1] = 0

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr

# d = deque()
# d.append(1)
# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

uf = UnionFind(N + 1)

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

print(-1 * 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())
uf = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
maxsize = 0
for j in range(N):
  s = uf.size(j)
  maxsize = max(maxsize, s)
print(maxsize)

Submission status: Accepted

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


    #Union Find

    #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 i in range(m):
        X,Y = map(int,input().split())
        unite(X-1,Y-1)
    
    #tank = set([])
    for i in range(n):
        find(i)
    ans=0
    for i in par:
        if i<0:
            ans=max(ans,-i)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
flag=list(range(n+1))
flagnum=[0]*(n+1)

#以下でフラグ建設 フラグが同じなら同じチームである
def takeflag(p):
    stock=[]
    while flag[flag[p]]!=flag[p]:
        stock.append(p)
        p=flag[p]
    p=flag[p]
    for i in stock:
        flag[i]=p
    return p
for i in range(m):
    a,b = map(int,input().split())
    a,b = map(takeflag,(a,b))
    a,b = min(a,b),max(a,b)
    flag[a]=b
for i in range(n+1):
    flag[i]=takeflag(i)
    flagnum[flag[i]]+=1 #チームの人数を知りたいときこの行を使う
print(max(flagnum))

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline()
n,m = map(int, input().split())
ab = []
for i in range(m):
  a,b = map(int, input().split())
  ab.append([a,b])

class UnionFind:
  def __init__(self,N):
    self.parent = [i for i in range(N)]
    self._size = [1] * N
    self.count = 0
  def root(self,a):
    if self.parent[a] == a:
      return a
    else:
      self.parent[a] = self.root(self.parent[a])
      return self.parent[a]
  def is_same(self,a,b):
    return self.root(a) == self.root(b)
  def unite(self,a,b):
    ra = self.root(a)
    rb = self.root(b)
    if ra == rb: return
    if self._size[ra] < self._size[rb]: ra,rb = rb,ra
    self._size[ra] += self._size[rb]
    self.parent[rb] = ra
    self.count += 1
  def size(self,a):
    return self._size[self.root(a)]


uf = UnionFind(n)

for i in range(m):
  a, b = ab[i][0],ab[i][1]
  a -= 1
  b -= 1
  if uf.is_same(a,b):
    continue
  uf.unite(a,b)
x = 0
for i in range(n):
  x = max(x, uf._size[i])
print (x)