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

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
        self.X = [1]*(n+1)

    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)

    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.X[x] += self.X[y]


N,M = MI()
UF = UnionFind(N)
for i in range(M):
    a,b = MI()
    if not UF.same_check(a, b):
        UF.unite(a,b)

print(max(UF.X))

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())
UFT = UnionFind(N)
 
for _ in range(M):
    A, B = map(int,input().split())
    UFT.union(A-1, B-1)
 
ans = 0
for i in range(N):
    ans = max(ans, UFT.size(i))
print(ans)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template

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


N,M = inputlist()
uf = UnionFind(N+1)
for i in range(M):
    A,B = inputlist()
    uf.union(A,B)

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

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

used = [-1]*N
for i in range(N):
    if used[i] >= 0:
        continue
    q = deque()
    q.append(i)
    used[i] = i
    while q:
        temp = q.popleft()
        for e in E[temp]:
            if used[e] == i:
                continue
            used[e] = i
            q.append(e)

L = [0]*N
for c in used:
    L[c] += 1
ans = max(L)
print(ans)

Submission status: Accepted

Solution code:
class Unionfind():
  def __init__(self, n=10**6):
    self.n=n
    self.root=[-1]*(n+1)
    self.rnk=[0]*(n+1)
  def find(self, x):
    if(self.root[x]<0):
      return x
    else:
      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
    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 same(self, x, y):
    return self.find(x)==self.find(y)
  def count(self, x):
    return -self.root[self.find(x)]
uf=Unionfind()
n,m=map(int,input().split())
for _ in range(m):
  a,b=map(int,input().split())
  uf.unite(a,b)
print(max([uf.count(i+1) for i in range(n)]))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
par = []
for i in range(n):
    par.append(i)  #初期親
rank = [1 for i in range(n)] #初期ランク
cut = []
def find(n): #親検索andランク短縮
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
        return n
    else:
        cut.append(n)
        find(par[n])
        return find(par[n])
def shorten(n): # 根に直接接続する
    global cut
    if par[n] == n:
        for i in range(len(cut)):
            par[cut[i]] = n
        cut = []
    else:
        cut.append(n)
        shorten(par[n])
def unite(a,b): #グループ併合
    x = find(a)
    y = find(b) #根っこ同士をくっつける
    if x == y: 
        return    #既に同一ユニオンなら何もしない
    if rank[x] < rank[y]:
        par[x] = y 
    elif rank[x] == rank[y]:
        par[y] = x
        rank[x] += 1
    else:
        par[y] = x
def judge(a,b):
    return par[a] == par[b]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
for i in range(n):
    shorten(i)
import collections
c = collections.Counter(par)
ans = 0
for i in range(n):
    ans = max(ans,c[i])
print(ans)

Submission status: Accepted

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

lst=[[] for i in range(N+1)]

for a,b in AB:
    lst[a].append(b)
    lst[b].append(a)



used=set(list(range(1,N+1)))
value=-10**18
while used:
    a=used.pop()
    stack=[a]

    visited={a}
    while stack:
        a=stack.pop()
        for p in lst[a]:
            if p in used:
                used.remove(p)
            if not p in visited:
                visited.add(p)
                stack.append(p)
    value=max(len(visited),value)
print(value)

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)
maxn = 0
for i in range(n):
    maxn = max(maxn, uf.size(i))
print(maxn)

Submission status: Accepted

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

par = [-1] * (n+1)
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return x
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return 

for j in range(m):
    unite(ab[j][0], ab[j][1])

m = -1*min(par)
print(m)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
relations = {}
for _ in range(m):
  a, b = list(map(int, input().split()))
  a -= 1
  b -= 1
  if relations.get(a):
     relations[a].append(b)
  else:
    relations[a] = [b]
  if relations.get(b):
    relations[b].append(a)
  else: 
    relations[b] = [a]

from collections import deque
visited = [False for i in range(n)]

groups = 0
def bfs(n, visited):
  global groups
  queue = deque([n])
  group_len = 0
  while queue:
    current = queue.popleft()
    if not visited[current]:
      visited[current] = True
      if relations.get(current):
        for neighbor in relations[current]:
          queue.append(neighbor)
        group_len += 1

  groups = max(groups, group_len)
    

if m == 0:
  print(1)
else:
  for i in range(n):
    if not visited[i]:
      bfs(i, visited)

  print(groups)

Submission status: Accepted

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

if M==0:
  print(1)
  exit()
else:
  A = [list(map(int,input().split())) for m in range(M)]
  G = Graph()
  G.add_edges_from(A)
  print(len(max(connected_components(G),key=len)))

Submission status: Accepted

Solution code:
from sys import stdin


input = stdin.readline


N, M = map(int, input().split())
friends = [tuple(map(int, inp.strip().split())) for inp in stdin.read().splitlines()]
father = [-1] * N


def getfather(x):
    if father[x] < 0: return x
    father[x] = getfather(father[x])
    return father[x]


def union(x, y):
    x = getfather(x)
    y = getfather(y)
    if x != y:
        if father[x] > father[y]:
            x,y = y,x
        father[x] += father[y]
        father[y] = x;


for a, b in friends:
    union(a - 1, b - 1)
# print(max(Counter([getfather(i) for i in range(N)]).values()))
print(max([-father[getfather(i)] for i in range(N)] or [0]) )

Submission status: Accepted

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


mod = 1000000007


def combinations_count_mod(n, r):
    r = min(r, n - r)
    numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1), 1)
    denom = pow(reduce(lambda x, y: x * y % mod, range(1, r + 1), 1), mod - 2, mod)
    return numer * denom % mod


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 solve():
    pass


def main():
    n, m = map(int, input().strip().split())

    uf = UnionFind(n)

    ans = 1
    for i in range(m):
        a, b = map(lambda x: int(x)-1, input().strip().split())
        if a > b:
            c = a
            a = b
            b = c
        uf.union(a,b)
        ans = max(ans,uf.size(a))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

setrecursionlimit(10**9+7)

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 = 0
for i in range(n):
    max_size = max(max_size,size(i))

print(max_size)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
r = [-1] * (N + 1)

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

for i in range(M):
        x, y = map(int, input().split())
        x = root(x)
        y = root(y)
        if x == y:
                continue
        if r[x] > r[y]:
                x, y = y, x
        r[x] += r[y]
        r[y] = x 

print(-min(r))

Submission status: Accepted

Solution code:
from collections import deque

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

group=[]
seen=[0]*N
ans=0
for i in range(N):
    if seen[i]: continue
    que=deque()
    seen[i]=1
    cnt=0
    que.append(i)
    while que:
        cnt+=1
        v=que.popleft()
        for nv in G[v]:
            if seen[nv]: continue
            seen[nv]=1
            que.append(nv)
    ans=max(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
import queue
N, M = map(int, input().split())
l = [[] for i in range(N)]
for i in range(M):
        a, b = map(int, input().split())
        l[a - 1].append(b - 1)
        l[b - 1].append(a - 1)
c = [0] * N 
ans = 1
q = queue.Queue()
for j in range(N):
        q.put(l[j])
        u = 0 
        while not q.empty():
                temp = q.get()
                for k in temp:
                        if c[k]:
                                continue
                        c[k] = 1 
                        u += 1
                        q.put(l[k])
        ans = max(ans, u)
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())

n, m = map(int, input().split())
u = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    u.union(a - 1, b - 1)
print(max(u.size(i) for i in range(n)))

Submission status: Accepted

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

  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())
  
N,M = map(int,input().split())
UF = UnionFind(N)
for i in range(M):
  x, y = map(int, input().split())
  UF.union(x,y)

ans = 0
for i in UF.roots():
  ans = max(ans, UF.size(i))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self,x):
        return -self.parents[self.find(x)]

N,M=map(int,input().split())
X=[]
for i in range(M):
    X.append(list(map(int,input().split())))
UF=UnionFind(N)
for i in range(M):
    UF.union(X[i][0]-1,X[i][1]-1)
print(max(UF.size(i) for i in range(N)))

Submission status: Accepted

Solution code:
def find(x):
    if parent[x]<0:
        return x
    else:
        parent[x]=find(parent[x])
        return parent[x]

def 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 i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    union(a,b)

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

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

uni = Union(n)
for a, b in ab:
    uni.unite(a-1, b-1)
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.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)]
  
uf = UnionFind(n)
ans=0

for i in range(m):
  a, b = map(int,input().split())
  a -= 1
  b -= 1
  uf.union(a, b)
  
for i in range(n):
  ans = max(ans, uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.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 False

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

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

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

UF = UnionFind(N)

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

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind(): # 0インデックス
    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)]


if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

n,m=map(int,input().split())
UFa=UF(n)
for i in range(m):
  x,y=map(int,input().split())
  UFa.unite(x-1,y-1)
ans=[]
for i in range(n):
  ans.append(UFa.size(i))
print(max(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
dic = defaultdict(list)
N, M  = map(int, input().split())
for i in range(M):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)
ans = 0
now = 1
seen = [-1]*N
queue = deque()

for i in range(N):
    if seen[i]!=-1:
        continue
    queue.append(i+1)
    seen[i]=now
    temp=0
    while queue:
        temp+=1
        q = queue.popleft()
        for j in dic[q]:
            if seen[j-1]!=-1:
                continue
            queue.append(j)
            seen[j-1]=now
    now+=1
    ans = max(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
# coding:UTF-8

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.rank = [0] * 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
        elif self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

if __name__ == '__main__':
    # ------ 入力 ------#
    # 1行入力
    n, m = list(map(int, input().split()))     # スペース区切り連続数字

    # 定数行入力
    x = m
    abList = sorted([list(map(int, input().split())) for _ in range(x)])     # スペース区切り連続数字(行列)

    # ------ 処理 ------#
    uf = UnionFind(n)
    for i in range(m):
        uf.union(abList[i][0]-1, abList[i][1]-1)

    out = max(uf.size(r) for r in uf.roots())
    # ------ 出力 ------#
    print("{}".format(out))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

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

visited=[0]*N
frnds=[[] for i in range(N)]

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

for i in range(N):
    frnds[i]=list(set(frnds[i]))

def saiki(num):
    value=1
    visited[num]=1
    for f in frnds[num]:
        if visited[f]!=1:
            value+=saiki(f)
    return value

ans=0
for i in range(N):
    if visited[i]!=1:
        ans=max(saiki(i),ans)

print(ans)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
par = [-1]*(N+1)
def find(x):
    if par[x] < 0:
        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
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
def size(x):
    return -par[find(x)]


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

M = 0 
for i in range(N):
    M = max(size(i),M)
print(M)

Submission status: Accepted

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

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

mp = [False]*n
mcnt = 0
for i in range(n):
    if mp[i]:
        continue
    queue = [i]
    cnt = 0
    mp[i] = True
    while(queue):
        num = queue.pop()
        cnt += 1
        target = set(l[num])
        for x in target:
            if mp[x]:
                continue
            mp[x]=True
            queue.append(x)
    mcnt = max(cnt,mcnt)

print(mcnt)