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

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

input = sys.stdin.readline

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

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

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

Submission status: Accepted

Solution code:
### https://note.nkmk.me/python-union-find/

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n 
    # 各要素の親要素の番号を格納するリスト 
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する

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

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

  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())
    #print()での表示用
    #ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す

N, M = map(int, input().split())
friends = UnionFind(N)
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  friends.union(A, B)
x = friends.roots()
ans = 0
for k in x:
  y = friends.size(k)
  ans = max(ans,y)
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]

if m != 0:
  g = [set() for _ in range(n)]
  valid = [-1] * n
  set_list = []
  for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].add(b-1)
    g[b-1].add(a-1)

  j = -1
  for i in range(n):
    if valid[i] == -1:
      set_list.append(set())
      j += 1
      stack = [i]
      while len(stack)!=0:
        v = stack.pop()
        set_list[j].add(v)
        valid[v] = 1
        for i in g[v]:
          if valid[i] == -1:
            stack.append(i)
            set_list[j].add(i)
            valid[i] = 1
  ans = 1
  for i in range(len(set_list)):
    ans = max(len(set_list[i]),ans)

  print(ans)

else:
  print(1)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N)]
        self.siz=[1 for _ 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,a,b):
        a=self.find(a)
        b=self.find(b)
        if a==b:
            return 0
        else:
            if self.rank[a]>self.rank[b]:
                self.par[b]=a
                self.siz[a]+=self.siz[b]
            else:
                self.par[a]=b
                self.siz[b]+=self.siz[a]
                if self.rank[a]==self.rank[b]:
                    self.rank[b]+=1
    def size(self,a):
        return self.siz[self.find(a)]
    def same(self,a,b):
        return self.find(a)==self.find(b)

N,M=map(int,input().split())
UF=UnionFind(N)
for i in range(M):
    A,B=map(lambda x:int(x)-1,input().split())
    UF.union(A,B)
ans=1
for i in range(N):
    ans=max(ans,UF.size(i))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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:
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)
#print(uf.parents)

for i in range(m):
    a,b=map(int,input().split())
    uf.union(a-1, b-1)
    #print(uf.parents)

print(abs(min(uf.parents)))

Submission status: Accepted

Solution code:
import collections
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

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

if m != 0:
    edge = np.array([input().split() for _ in range(m)], dtype = np.int64).T
    tmp = np.ones(m, dtype = np.int64).T
    graph = csr_matrix((tmp, (edge[:] -1)), (n, n))

    cnt = collections.Counter(connected_components(graph)[1])

    print(max(cnt.values()))
else:
    print('1')

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())
    
def main():
    N,M = map(int,input().split())
    A = [0 for i in range(M)]
    B = [0 for i in range(M)]
    for i in range(M):
        A[i],B[i] = map(int,input().split())
        
    uf = UnionFind(max(N,M))
    for i in range(M):
        a = A[i]-1
        b = B[i]-1
        uf.union(a, b)
        
    ans = 1
    for i in range(M):
        ans = max(ans,uf.size(i))
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array
import numpy as np

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = [-1 for _ in range(N)]

    def root(self, N):
        if self.tree[N] < 0:
            return N
        self.tree[N] = self.root(self.tree[N])
        return self.tree[N]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.tree[x] > self.tree[y]:
            x, y = y, x
        self.tree[x] += self.tree[y]
        self.tree[y] = x

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


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

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

    ret = 0
    for n in range(N):
        ret = max(ret, uf.size(n))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def unite(x, y):
  x = find(x)
  y = find(y)
  if x > y:
    par[x] = y
    find(x)
  else:
    par[y] = x
    find(y)

if m > 0:  
  for i in range(m):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
  
  ans = [0] * n
  Max = 0
  for i in range(n):
    find(i)
  for i in par:
    ans[i] += 1
  for i in ans:
    if i > Max:
      Max = i
  
  print(Max)
else:
  print(1)

Submission status: Accepted

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

import numpy as np
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)

# print(par)
print(-min(par))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[set() for _ in range(n+1)]

for i in range(m):
  a,b=map(int,input().split())
  l[a].add(b)
  l[b].add(a)

from collections import deque

vi=[0 for _ in range(n+1)]
st=deque([i,i] for i in range(1,n+1))

while st:
  c,d=st.popleft()

  if vi[c]==0 :
    vi[c]=d
    for m in l[c]:
      st.appendleft([m,d])
from collections import Counter
s=Counter(vi)
mx=0
for m in s.values():
  mx=max(mx,m)
print(mx)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N, M = list(map(int, input().split()))
u = UnionFind(N)
for _ in range(M):
    a, b = list(map(int, input().split()))
    u.union(a-1,b-1)
ans = []
for i in range(N):
    ans.append(u.find(i))
from collections import Counter
c=Counter(ans)
print(max(c.values()))

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int, input().split())
if m == 0:
  print(1)
  exit()
g = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
v = [-1 for i in range(n)]
ans = []
for i in range(n):
  if v[i]!=-1:
    continue
  v[i]=0
  an=1
  d = deque([i])
  while len(d):
    x = d.popleft()
    for i in g[x]:
      if v[i] == -1:
        d.append(i)
        v[i]=1
        an+=1
  ans.append(an)
print(max(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1,b-1
    edge[a].append(b)
    edge[b].append(a)

visited = [0] * N
cnt = 0
def dfs(n):
    global cnt
    if visited[n]: return
    cnt += 1
    visited[n] = True
    for nv in edge[n]:
        dfs(nv)

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
f=[set() for i in range(N)]
v=[False]*N
g=[]

for i in range(0,M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    f[a].add(b)
    f[b].add(a)

for i in range(0,N):
    if v[i]:
        continue
    s=set()
    q=[i]
    while len(q)>0:
        p=q.pop()
        v[p]=True
        s.add(p)
        for x in f[p]:
            if v[x]:
                continue
            q.append(x)
    g.append(s)

z=0
for x in g:
    z=max(z,len(x))

print(z)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
V = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    V[a].append(b)
    V[b].append(a)
    
reach = [0]*(n+1)
ans = 0
for i in range(1,n+1):
    if reach[i] != 0:
        pass
    else:
        q = deque([])
        q.append(i)
        reach[i] = 1
        j = 1
        while q:
            x = q.popleft()
            
            for y in V[x]:
                if reach[y] == 0:
                    reach[y] = 1
                    q.append(y)
                    j += 1
                    
            ans = max(ans, j)
            
print(ans)

Submission status: Accepted

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

# In[1]:


def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

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


# In[3]:


N,M = map(int, input().split())
par = [-1]*N
for _ in range(M):
    A,B = map(int, input().split())
    A -= 1; B -= 1
    unite(A,B)
ans = 0
for i in range(N):
    ans = max(ans, size(i))
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m = map(int, input().split())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
size = [1 for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if not same(a - 1, b - 1):
        unite(a - 1, b - 1)
x = [0] * n
ans = 0
for i in range(n):
    j = get_root(i)
    x[j] += 1
    ans = max(ans, x[j])
print(ans)
"""

from collections import deque

def bfs(s):
    q = deque()
    q.append(s)
    visit[s] = 1
    cnt = 1
    while q:
        p = q.popleft()
        for j in G[p]:
            if visit[j] == 0:
                q.append(j)
                visit[j] = 1
                cnt += 1
    global ans
    ans = max(ans, cnt)
    return

n, m = map(int, input().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
visit = [0] * (n + 1)
ans = 0
for i in range(1, n + 1):
    if visit[i] == 0:
        bfs(i)
print(ans)
"""

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
g = {i:set() for i in range(N)}
v = [-1 for i in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].add(b)
  g[b].add(a)

Q = deque()
ans = 0
for a in g:
  if v[a]==-1:
    v[a] = 1
    ans_tmp = 1
    Q.append(a)
    while len(Q)>0:
      na = Q.popleft()
      for nb in g[na]:
        if v[nb] == -1:
          v[nb] = 1
          ans_tmp += 1
          Q.append(nb)
    ans = max(ans, ans_tmp)
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)]

n,m=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
uf=UnionFind(n)
for i in range(m):
  uf.union(ab[i][0]-1,ab[i][1]-1)
print(max([uf.size(x) for x in range(n)]))

Submission status: Accepted

Solution code:
import numpy as np

class union_find:
    def __init__(self,N):
        self.r = np.ones(N)*-1
    
    def root(self,x):
        if self.r[x]<0:
            return int(x)
        else:
            self.r[x] = self.root(int(self.r[x]))
            return int(self.r[x])
        
    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        else:
            self.r[x] += self.r[y]
            self.r[y] = int(x)
            return True
        
    def size(self,x):
        return -self.r[self.root(x)]


N,M = [int(i) for i in input().split()]

Union = union_find(N)
for i in range(M):
    x,y = [int(i) for i in input().split()]
    Union.unite(x-1,y-1)

Y = - min(Union.r)
print(int(Y))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

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

def main():
    n,m = tuple([int(t)for t in input().split()])

    uf = UnionFind(n)

    for _ in range(m):
        a_i,b_i = tuple([int(t)-1 for t in input().split()])
        uf.unite(a_i,b_i)

    candidates = []

    for i in range(n):
        candidates.append(uf.size(i))

    print(max(candidates))
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


def main():
    #"""
    N, M = [int(n) for n in input().split(" ")]
    friends = []
    for _ in range(M):
        a, b = [int(n) for n in input().split(" ")]
        friends.append([a - 1, b - 1])
    #"""
    """
    N = 200000
    M = 200000
    friends = []
    import random
    for _ in range(M):
        a = random.randint(1, N)
        b = random.randint(1, N)
        while a == b:
            a = random.randint(1, N)
            b = random.randint(1, N)
        if a <= b:
            friends.append([a - 1, b - 1])
        else:
            friends.append([b - 1, a - 1])
    #friends = sorted(friends)
    """
    #print(friends)
    """
    dic = {}
    vdic = {}
    nowg = 0
    for f in friends:
        a = f[0]
        b = f[1]

        if a not in dic and b not in dic:
            dic[a] = nowg
            dic[b] = nowg
            vdic[nowg] = [a, b]
            nowg += 1
        elif a in dic and b not in dic:
            dic[b] = dic[a]
            vdic[dic[a]].append(b)
        elif a not in dic and b in dic:
            dic[a] = dic[b]
            vdic[dic[b]].append(a)
        else:
            aG = dic[a]
            bG = dic[b]
            # b -> a
            if aG == bG:
                continue
            for k in vdic[bG]:
                vdic[aG].append(k)
                dic[k] = aG
            del(vdic[bG])


    score = 0
    for k ,v in vdic.items():
        #print(g)
        s = len(v)
        if score <= s:
            score = s
    print(score)

    """

    X = {}
    for i in range(N):
        X[i] = []

    def show(m):
        for i in range(len(m)):
            print(m[i])

    #show(X)

    for f in friends:
        X[f[0]].append(f[1])
        X[f[1]].append(f[0])

    #show(X)

    groups = []

    vdic = [0 for _ in range(N)]

    for n in range(N):
        already = False
        if vdic[n] == 1:
            continue
        queue = [n]
        group = [n]
        vdic[n] = 1
        while len(queue) > 0:
            #print("now queue:", queue)
            nowNode = queue[0]
            del(queue[0])
            nextQueue = []
            for i in X[nowNode]:
                if vdic[i] == 0:
                    nextQueue.append(i)
                    group.append(i)
                    vdic[i] = 1
            queue += nextQueue
            nextQueue = []
        groups.append(group)

    #print(groups)

    score = 0
    for g in groups:
        #print(g)
        s = len(g)
        if score <= s:
            score = s
    print(score)



if __name__ == "__main__":
    main()

Submission status: Accepted

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


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1] * (n + 1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0] * (n + 1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def main():
    N, M = map(int, input().split())
    UF = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        UF.Unite(a, b)
    ans = 0
    for i in range(N):
        ans = max(ans, UF.Count(i + 1))
    print(ans)


if __name__ == "__main__":
    main()

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 = 1
for i in range(N):
    ans = max(ans,uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        super().__init__()
        self.par = [-1 for i in range(n)]
        self.rank = [0 for i in range(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 is_same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x


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

print(- min(union.par))

Submission status: Accepted

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

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

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)

uf1=UnionFind(n)
ans=[]
for i in range(m):
    a,b=map(int, input().split()) #a,b:つながっている辺
    uf1.union(a-1,b-1)

for i in range(n):
    ans.append(uf1.find(i))
from collections import Counter
c=Counter(ans)
print(max(c.values()))

Submission status: Accepted

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

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

root = [-1]*n

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

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

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

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

max_size = max(map(size,range(n)))

print(max_size)