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 sys
import resource

def root(x):
  if par[x] == x:
    return x
  par[x] = root(par[x])
  return par[x]

def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx != ry:
    par[rx] = ry
  return 0

sys.setrecursionlimit(10 ** 6)
n, m=map(int, input().split(" "))
par = list(range(n + 1))
for i in range(m):
  a, b = map(int, input().split(" "))
  union(a, b)
#print(par)
maxi = 0
count = 1
#print(par)
countpar = [0 for i in range(n + 1)]
#print(len(countpar), len(par))
for i in range(1, n + 1):
  countpar[root(par[i])] += 1
print(max(countpar))
#print(countpar, par)

Submission status: Accepted

Solution code:
from networkx import *
print(max(*map(len,connected_components(Graph([*map(str.split,open(0))][1:]))),1,0))

Submission status: Accepted

Solution code:
"""
UnionFindにはいろいろな実装があるが, 本問ではparents配列にノード数を保持する実装だと非常に簡単に解ける. 
以下のようにしてノード数を保持する.
自身が子のとき, 親ノード番号を格納する.
自身が根のとき, ノード数を負の数で格納する.
つまり,　負の数のときは自身が根であり, その絶対値がその木のノード数を表す.
初期化時は、すべてのノードを−1で初期化する.
"""

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

#UnionFind木の実装
#-1で初期化し、併合のたびに-1していく
par = [-1] * N  #親
rank = [0] * N #木の深さ

#木の根を求める
def find(x):
    #par[x]が負のとき(自分が代表のとき)、自身を返す
    if par[x] < 0:
        return x
    else:
        return find(par[x])

#xとyの属する集合を併合
def unite(x,y):
    x = find(x)
    y = find(y)
    #もとから同じ集合のときは何もしない
    if (x == y):
        return
    #x側を常に小さくする
    if par[x] > par[y]:
            x, y = y, x
    
    #x側に併合する、その際xの代表にノード数を加算する
    par[x] += par[y]
    par[y] = x
    

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

for i in range(M):
    x,y = map(int,input().split())
    x -= 1; y -= 1
    unite(x,y)


ans = min(par)

print(abs(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)]


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

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

print(ans)

Submission status: Accepted

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(n)]
# print(par)
s = list()
"""
# union find(parには0も入れているので、par[1]=1になる)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
"""


def find(x):

    while par[x] != x:
        tmp = par[x]
        par[x] = par[par[x]]
        x = par[x]

    return x


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        par[x] = y


# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(n):
    s.append(find(k))
# print(s)
c = collections.Counter(s)
print(max(c.values()))

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
lst = [-1 for i in range(n + 1)]
lst[0] = 0
def find(x):
    if(lst[x] < 0):
        return(x)
    else:
        return(find(lst[x]))
def unit(x, y):
    xr = find(x)
    yr = find(y)
    if (xr == yr):
        pass
    else:
        if (xr > yr):
            x, y = y, x
            xr, yr = yr, xr
        lst[xr] = lst[xr] + lst[yr]
        lst[yr] = xr

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

print(-(min(lst)))

Submission status: Accepted

Solution code:
import collections

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

q = collections.deque()
visited = [0 for i in range(n)]

ans = 0
for i in range(n):
    tmp = 0
    if visited[i] == 0:
        visited[i] = 1
        tmp += 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        while q:
            s = q.pop()
            for k in friend[s]:
                if visited[k] == 0:
                    visited[k] = 1
                    tmp += 1
                    q.append(k)
    ans = max(ans,tmp)

print(max(ans,1))

Submission status: Accepted

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

graph = [[] for _ in range(N+1)]
for i in range(M):
    a, b = map(int, input().split(' '))
    graph[a].append(b)
    graph[b].append(a)
    
dist = [-1] * (N+1)
dist[0] = 0

disjoint_set = []
n_disj = 0
d = deque()

for j in range(1,N+1):
    if dist[j] != -1:
        continue
    
    dist[j] = 0
    d.append(j)
    disjoint_set.append([])
    disjoint_set[n_disj].append(j)
        
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
            disjoint_set[n_disj].append(i)

    n_disj+=1
    
ans = 1
for s in disjoint_set:
    ans = max(ans, len(s))
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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N,M,*f = map(int, open(0).read().split())
AB = [f[i*2:i*2+2] for i in range(M)]
uf = UnionFind(N)
for A,B in AB:
    uf.union(A-1,B-1)
print(min(uf.parents)*(-1))

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
class UnionFind:
    def __init__(self,n): # 頂点数 親ならばその集合に∉頂点数に-1をかけたもの
        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 unite(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)]
n,m = readInts()
uni = UnionFind(n)
for i in range(m):
    a,b = map(lambda x:int(x)-1, input().split())
    uni.unite(a,b)
ans = -1
for i in range(n):
    ans = max(ans, uni.size(i)) # 一番大きいサイズを全部分割する必要があるため
print(ans)

Submission status: Accepted

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

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

tree = [-1] * N

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

def unite(x, y):
  rx, ry = root(x), root(y)
  if rx == ry: return
  tree[rx] += tree[ry]
  tree[ry] = rx

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

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

print(max(map(size, range(N))))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = 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)
for i in range(M):
    uf.union(A[i]-1,B[i]-1)

answer = 1
uflist = uf.parents
for i in range(N):
    time = uf.size(uflist[i])
    answer = max(time,answer)
print(answer)

Submission status: Accepted

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${TYO>cuR480@qAH2g<SksD5J4|Tok8~W85Fi=^lxC{7Uq74hU0=X{&(AMTO53&2Xd%xxXSJz7>bCE!gI2XS<-(vOg8X%LXU;vhylGT3lX}ZdrAE@IQs{2RE9GR(EkmL<t_%ZNs1oq^`kGMW(1(Ga6!i>F7X}`H7r5y^)s+#F<9Kdtv{BTL6HF9?=_=i%VE`DDGzbO~GDv*+Uh77|Wh7Au1V>|0yp(l`$OpW=ry#82-wQ%&5*=L<I3nkS91mLMeyjnxoC_Mo3uVbQ@U1`8@2@<^5lK3Aat{slZ0e;f-VC71YKCFZGT@9(su?&&4({63n|X#@)0TYNZqu@}piynS!l;c`8{%8;w6tA`FP1qj<+5Xskk~=E1`badh}FFHdOq<Z@*POwP?JBF$%S|<lLNOc5Aw%s(BC5>_v-Un{8mi7T;8d_YO*KO;Xw>(82E=B9iEFXbHIzhll}vB`qr2")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

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

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

    def root(self, x): 
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 圧縮経路
            return self.par[x]
            # return root(par[x]) # 圧縮しない場合

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

    def unite(self, x, y): 
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: 
            return

        # par[rx] = ry # naiveな連結

        # 低い木を高い方にくっつける。
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.sizes[ry] += self.sizes[rx]
        else:
            self.par[ry] = rx
            self.sizes[rx] += self.sizes[ry]

        # rx木とry木の高さが同じならば、rx木を深くする。
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def size(self, x): 
        '''
        xが属するグループのサイズを返す
        (連結成分の大きさ)
        '''
        return self.sizes[self.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):
    tmp = uf.size(i)
    if ans <= tmp:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
l=lambda:map(int, input().split())
n,m=l()
p=[-1]*n
def root(x):
  if p[x]<0:return x
  p[x]=root(p[x]);return p[x]
def union(x,y):
  x,y=root(x),root(y)
  if x==y: return
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[r(x)]
for _ in range(m):
  a,b=l()
  union(a-1,b-1)
print(-min(p))

Submission status: Accepted

Solution code:
import sys
from collections import Counter


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

class UnionFind():
    def __init__(self, n):
        self.n = n                              # 要素数(初期頂点数)
        self.root = [i for i in range(n)]       # 根
        self.rank = [0] * n                     # 深さ
        self.sizes = [1] * n                     # 要素数(木)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:         # 浅い方を深い方につなげる
            self.root[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.root[y] = x
            self.sizes[x] += self.sizes[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):                       # 同じ集合かどうかの真偽を返す
        return self.find(x) == self.find(y)

    def roots(self):
        return {i for i, num in enumerate(self.root) if i == num}

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

n, m = inintm()

uf = UnionFind(n)

for i in range(m):
    a, b = inintm()
    uf.unite(a-1, b-1)

ans = 0

r = uf.roots()

for i in r:
    if uf.size(i) > ans:
        ans = uf.size(i)

print(ans)

Submission status: Accepted

Solution code:
"""D."""

import sys


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


class UnionFindTree:
    """Union-find."""

    def __init__(self, n: int) -> None:
        """Init."""
        self.n = n
        self.rank = [-1] * n

    def find_root(self, x: int) -> int:
        """Find root."""

        if self.rank[x] < 0:
            return x

        self.rank[x] = self.find_root(self.rank[x])
        return self.rank[x]

    def union(self, x: int, y: int) -> None:
        """Unite two trees."""
        x_root = self.find_root(x)
        y_root = self.find_root(y)

        if x_root == y_root:
            return

        if x_root > y_root:
            x_root, y_root = y_root, x_root

        self.rank[x_root] += self.rank[y_root]
        self.rank[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.rank[self.find_root(x)] * -1

    def is_same(self, x: int, y: int) -> bool:
        """Is same group."""
        return self.find_root(x) == self.find_root(y)


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

tree = UnionFindTree(n)

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

ans = 0

for i in range(n):
    ans = max(ans, tree.get_size(i))

print(ans)

Submission status: Accepted

Solution code:
"""D."""

import sys

#def input() -> str:  # noqa: A001
#    """Input."""
#    return sys.stdin.readline()[:-1]


class UnionFindTree:
    """Union-find."""

    def __init__(self, n: int) -> None:
        """Init."""
        self.n = n
        self.rank = [-1] * n

    def find_root(self, x: int) -> int:
        """Find root."""

        if self.rank[x] < 0:
            return x

        self.rank[x] = self.find_root(self.rank[x])
        return self.rank[x]

    def union(self, x: int, y: int) -> None:
        """Unite two trees."""
        x_root = self.find_root(x)
        y_root = self.find_root(y)

        if x_root == y_root:
            return

        if x_root > y_root:
            x_root, y_root = y_root, x_root

        self.rank[x_root] += self.rank[y_root]
        self.rank[y_root] = x_root

    def get_size(self, x: int) -> int:
        """Get size."""
        return self.rank[self.find_root(x)] * -1

    def is_same(self, x: int, y: int) -> bool:
        """Is same group."""
        return self.find_root(x) == self.find_root(y)


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

tree = UnionFindTree(n)

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

ans = 0

for i in range(n):
    ans = max(ans, tree.get_size(i))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]

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

    ans = 0
    visited = [False] * n

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

        q = deque()
        q.append(i)
        cnt = 1
        visited[i] = True

        while q:
            u = q.popleft()
            for v in adj[u]:
                if not visited[v]:
                    q.append(v)
                    cnt += 1
                    visited[v] = True
            ans = max(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy

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

pairs = [0] * M
for i in range(M):
    pairs[i] = list(map(int, input().split()))


# N = 5
# pairs = [[1,2], [3,4], [5,1]]


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

    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 -self.r[self.root(x)]

uf = UnionFind(N)
for pair in pairs:
    a = pair[0] - 1
    b = pair[1] - 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:
# import sys
# input = sys.stdin.readline
import collections

def main():
    n, m = input_list()
    Friend = [[] for i in range(n+1)]
    for _ in range(m):
        a, b = input_list()
        Friend[a].append(b)
        Friend[b].append(a)
    Flag = [False for i in range(n+1)]
    ans = 1
    for i in range(1, n+1):
        if Flag[i]:
            continue
        q = collections.deque()
        q.append(i)
        cnt = 1
        while q:
            st = q.popleft()
            Flag[st] = True
            for j in Friend[st]:
                if Flag[j]:
                    continue
                cnt += 1
                Flag[j] = True
                q.append(j)
            ans = max(ans, cnt)
    print(ans)


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


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 最大の友達集団の人の数ぶんだけグループに分ける必要がある。
# union-findを使用する必要がある。

class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木の結合を行う。親の配下に入る
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

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

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


N, M = map(int, input().split())
tree = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    tree.unite(A-1, B-1)


bag = {}
for i in range(N):
    boss = tree.root(i)
    if not boss in bag.keys():
        bag[boss] = 1
    else:
        bag[boss] += 1

print(max(bag.values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class UnionFind():
    """ UnionFindはグループの分割はできないことに注意 """
    def __init__(self, n):
        """
            n: 要素数
            parents: 親を示す、-1の場合、自身の親がいない(頂点)であることを示す
        """
        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と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 most_depth_root(self):
        return -min(self.parents)


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

union_find = UnionFind(N)
for i in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)

print(union_find.most_depth_root())

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
INF = 10**9


"""
UnionFind
要素を素集合(互いに素)に分割して管理するデータ構造
O(α)<O(log)
逆アッカーマン関数
"""

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


if __name__ == "__main__":
    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.union(a,b)
    ans = 0
    for i in range(n):
        c = uf.size(i)
        ans = max(ans,c)
    print(ans)

Submission status: Accepted

Solution code:

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

    def find(self, x :int) -> int:
        if self.d[x] < 0: return x
        return self.find(self.d[x])
    
    def unite(self, x, y :int):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return

        if -self.d[xr] < -self.d[yr]:
            xr, yr = yr, xr

        self.d[xr] += self.d[yr]
        self.d[yr] = xr

    def is_same(self, x, y :int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x :int) -> int:
        return - self.d[self.find(x)]


def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    ab = [[a-1, b-1] for a, b in ab]

    uf = UnionFind(n)

    for a, b in ab:
        uf.unite(a, b)

    mx = 0
    for i in range(n):
        s = uf.size(i)
        if s > mx:
            mx = s

    print(mx)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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)
ans = 0
for i in range(n):
    ans = max(ans, get_size(i))
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数



    # 入力を整数に変換して受け取る
    def input_int():
        return int(input())

    def map_int_input():
        return map(int, input())

    MII = map_int_input

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

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

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

    # 2次元リスト化
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    class UnionFind:
        def __init__(self, n):
            """
            :param n: 人数
            :type n: int
            """
            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 = MII_split()


    # groups = []
    uf = UnionFind(N)

    for _ in range(M):
        A, B = MII_split()
        uf.union(A-1, B-1)  # unionfindを使い、結合の計算量を減らす
        # is_in_groups = False
        # for group in groups:
        #     if A in group and B not in group:
        #         group.append(B)
        #         break
        #     elif B in group and A not in group:
        #         group.append(A)
        #         break
        #     elif A in group and B in group:
        #         is_in_groups = True
        #         break
        # if not is_in_groups:
        #     groups.append([A, B])

    print(max(uf.size(x) for x in range(uf.group_count())))
    
resolve()

Submission status: Accepted

Solution code:
import collections

def searchRoot(n):
    par = parList[n]
    if n == par:
        if len(q) > 0:
            rootIn(q,n)
        return n
    else:
        q.append(n)
        return(searchRoot(par))

def rootIn(q,root):
    while len(q) > 0:
        parList[q.popleft()] = root

n,m = list(map(int,input().split()))
q = collections.deque()

parList = [i for i in range(n+1)]

for i in range(m):
    a,b = list(map(int,input().split()))
    aRoot = searchRoot(a)
    bRoot = searchRoot(b)
    if aRoot != bRoot:
        parList[max(aRoot,bRoot)] = min(aRoot,bRoot)
    
#print(parList)

ansDic = dict()
rootSet = set()
for i in range(1,n+1):
    root = searchRoot(i)
    if root in rootSet:
        ansDic[root] += 1
    else:
        rootSet.add(root)
        ansDic[root] = 1

ans = 1
for i in rootSet:
    if ansDic[i] > ans:
        ans = ansDic[i]

print(ans)