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,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def NLI(n):return [[int(i) for i in input().split()] for i in range(n)]
def NLI_(n):return [[int(i)-1 for i in input().split()] for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
#mo=998244353
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans=0


n,m=LI()
g,_=GI(n,m)

v=[-1]*n
for i in range(n):
    if v[i]!=-1:
        continue
    q=[i]
    v[i]=i
    while q:
        c=q.pop()
        for nb,d in g[c]:
            if v[nb]==-1:
                q.append(nb)
                v[nb]=i

c=[0]*n
for i in range(n):
    c[v[i]]+=1
print(max(c))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n = n
        self.par = [-1]*(n+1)
    
    def find(self,x):
        if self.par[x] < 0:
            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:
            return
        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())
uf = UnionFind(N)

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

ans = -min(uf.par)
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())
INF=float('inf')
uf=UnionFind(n)
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  
ans=-INF
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.p, self.d = [-1] * n, [0] * n

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

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

    def unite(self, x, y):
        if self.isSame(x, y):
            return
        x, y = self.find(x), self.find(y)

        if self.d[x] > self.d[y]:
            self.p[x] += self.p[y]
            self.p[y] = x
        else:
            self.p[y] += self.p[x]
            self.p[x] = y
            if self.d[x] == self.d[y]:
                self.d[y] += 1

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

    def numTree(self):
        return sum([1 for p in self.p if p < 0])


N, M = map(int, input().split())
F = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    F.unite(A - 1, B - 1)
print(max([abs(F.p[i]) for i in range(N) if F.p[i] < 0]))

Submission status: Accepted

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

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

Submission status: Accepted

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

def dfs(u, g, visited):
    if (visited[u]): return 0
    visited[u] = True

    res = 1
    for v in g[u]:
        res += dfs(v, g, visited)

    return res


def main():
    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)

    visited = [False] * (n+1)
    ans = 0;
    for i in range(1, n+1):
        if (visited[i]): continue
        ans = max(ans, dfs(i, g, visited))

    print(ans)

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())
alist,blist = [],[]
for i in range(m):
    a,b=map(int,input().split())
    alist.append(a)
    blist.append(b)

uf = UnionFind(n)
for i in range(m):
    uf.union(alist[i]-1,blist[i]-1)

roots = uf.roots()
rootsize = [uf.size(rt) for rt in roots]
print(max(rootsize))

Submission status: Accepted

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

    def root(self, x):
        rx = self.r[x]
        if (rx) < 0:
            return x

        return self.root(rx)

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

        if x == y:
            return False
        r = self.r

        if r[x] > r[y]:
            x, y = y, x

        r[x] += r[y]
        r[y] = x

        return True

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

    def debug(self):
        print(self.r)


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


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

max_ = -1
for i in range(N):
    max_ = max(relations.size(i), max_)

print(max_)

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(lambda x:int(x)-1, input().split())
  uf.union(a,b)
  
rlt = 0
for i in range(N):
  rlt = max(rlt, uf.size(i))
print(rlt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(m)]
root=[-1]*n

def find(x):
    if root[x]<0:
        return x
    else:
        root[x]=find(root[x])
        return root[x]
    
def unite(x,y):
    parent_x=find(x)
    parent_y=find(y)
    
    if parent_x==parent_y:
        return

    if parent_x>parent_y:
        parent_x,parent_y=parent_y,parent_x

    root[parent_x]+=root[parent_y]
    root[parent_y]=parent_x

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

for i in range(m):
    unite(AB[i][0]-1,AB[i][1]-1)

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

print(ans)

Submission status: Accepted

Solution code:
class Node():
    def __init__(self,index):
        self.index = index
        self.parent = self 
        self.size = 1

    @staticmethod
    def find_set(node):
        if node.parent == node:
            return node 
        root = Node.find_set(node.parent)
        node.parent = root
        return root

    @staticmethod
    def union(node_a,node_b):
        root_a = Node.find_set(node_a)
        root_b = Node.find_set(node_b)
        if root_a != root_b:
            if root_a.size < root_b.size:
                root_a.parent = root_b
                root_b.size == root_a.size
            else:
                root_b.parent = root_a
                root_a.size += root_b.size



if __name__ == "__main__":
    n,m = [int(val) for val in input().split()]
    
    persons = []
    count = []
    for i in range(n):
        persons.append(Node(i))
        count.append(0)
    
    for i in range(m):
        a,b = [int(val) for val in input().split()]
        if a > b:
            Node.union(persons[a-1],persons[b-1])
        else:
            Node.union(persons[b-1],persons[a-1])


    for idx,person in enumerate(persons):
        count[Node.find_set(person).index] += 1
    
    # print(count)
    result = max(count)
    print(result)

Submission status: Accepted

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

Submission status: Accepted

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


# in[]:
NM = input()
N = int(NM.split()[0])
M = int(NM.split()[1])

info = [input() for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    AB = info[i].split()
    A = int(AB[0]) - 1
    B = int(AB[1]) - 1
    uf.union(A, B)

roots = uf.roots()
rootsize = [uf.size(rt) for rt in roots]
print(max(rootsize))

Submission status: Accepted

Solution code:
from collections import deque

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

conn = [[] for _ in range(N + 1)]
for i in range(M):
    A, B = [int(x) for x in input().split()]
    conn[A].append(B)
    conn[B].append(A)

ans = 0
q = deque([])
check = [False] * (N + 1)
for u in range(1, N + 1):
    if check[u] == False:
        check[u] = True
        q.append(u)
        size = 1
        while q:
            v = q.popleft()
            for w in conn[v]:
                if check[w] == False:
                    check[w] = True
                    q.append(w)
                    size += 1
    ans = max(ans, size)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

# 入力
n, m = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    path[a].append(b)
    path[b].append(a)

# BFSで大きさの最大を求める
## DFSでもよい
ans = 0
visited = [0] * n
queue = deque()
for i in range(n):
    if visited[i]: continue
    now = i
    queue.append(now)
    visited[now] = 1
    size = 0
    while queue:
        now = queue.popleft() # popleft()をpop()に変えるとDFSになる
        size += 1
        for nxt in path[now]:
            if visited[nxt]: continue
            queue.append(nxt)
            visited[nxt] = 1
    ans = max(ans, size)

# 出力
print(ans)

Submission status: Accepted

Solution code:
# UnionFind
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
        self.size = [1] * n

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            self.size[y] += self.size[x]
            return True
        else:
            return False

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

# 入力
n, m = map(int, input().split())

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

# 連結部分の大きさの最大が答え
ans = 0
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.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

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

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

Submission status: Accepted

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


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

UF = UnionFind(N)
for i in range(M):
    A, B = map(int, input().split())
    A, B = A - 1, B - 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
sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
root = [-1] * N

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


def union(x, y):
    x_parent = parent(x)
    y_parent = parent(y)
    if x_parent == y_parent:
        return
    root[x_parent] += root[y_parent]
    root[y_parent] = x


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

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


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

print(max_size)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, node):
        self.parent = [-1 for _ in range(node)]

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]


def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)
    ans = 0
    for i in range(n):
        ans = max(ans, uf.get_size(i))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]

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):
    a, b = AB[i]
    uf.union(a, b)

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

print(ans)

Submission status: Accepted

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

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:
            return self.find(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
        return
    
    def size(self, x):
        x = self.find(x)    
        return self.parents[x]*(-1)

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

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

if  __name__ == "__main__":
     main()

Submission status: Accepted

Solution code:
# Union find
# かっつぱさんの解説と公式のスライドみた
# https://www.youtube.com/watch?time_continue=916&v=zxor0DdwoXA&feature=emb_logo
# https://www.slideshare.net/chokudai/union-find-49066733

import sys
sys.setrecursionlimit(10 ** 9)

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

root = [-1]*n

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

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

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

for a, b in AB:
    a -= 1
    b -= 1
    unite(a, b)

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

Submission status: Accepted

Solution code:
from collections import *
n,m = map(int,input().split())
par = [-1 for _ in range(n)]#par<0なら自身が親で要素の個数、>0なら子で親の位置示す

def root(i):
    if par[i] < 0:
        return i
    else:
        return root(par[i])

def size(a):
    return -par[root(a)]

def union(a,b):
    a = root(a)
    b = root(b)
    if a == b:#親が等しい
        return False
    if size(a) < size(b):#サイズが大きい方に繋げる
        a,b = b,a
    par[a] += par[b]
    par[b] = a
    return True

for i in range(m):
    a = [int(j)-1 for j in input().split()]#数字を一つ減らして足を揃える
    if root(a[0]) != root(a[1]):
        union(a[0],a[1])
print(max([ size(i) for i in par]))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import Counter


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

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

def dfs(now):
    connected_component[now] = cc
    for next in graph[now]:
        if connected_component[next]:
            continue
        dfs(next)

connected_component = [0] * N
cc = 1
for i in range(N):
    if connected_component[i]:
        continue
    dfs(i)
    cc += 1

ans = max(Counter(connected_component).values())

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
par=[-1 for i in range(n+1)]
def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(m):
    a,b=map(int,input().split())
    connect(a-1,b-1)
ans=0
for i in par:
    if i<0:
        ans=max(ans,-i)
print(ans)

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


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)
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):
    ans = max(ans, uf.size(i))
    
print(ans)

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

print(max_size)