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

input = sys.stdin.readline


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())
    uf = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        uf.union(A-1, B-1)
    roots = uf.roots()
    cnt = []
    for r in roots:
        cnt.append(uf.size(r))
    cnt.sort(reverse=True)
    ans = cnt[0]
    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 = 0
for i in range(N):
    # print(uf.size(i))
    # print(uf.members(i))
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
def Con(N,Edge):
    L = [0]*N
    max = 0
    for i in range(N):
        if L[i] == 1:
            continue
        else:
            E = [i]
            F = [i]
            L[i] = 1
            while E:
                s = E.pop()
                for e in Edge[s]:
                    if L[e] == 0:
                        E.append(e)
                        L[e] = 1
                        F.append(e)
            if len(F) > max:
                max = len(F)
    return max

if __name__ == "__main__":
    N,M = map(int,input().split())
    Edge = [[] for i in range(N)]
    for i in range(M):
        A,B = map(int,input().split())
        Edge[A-1].append(B-1)
        Edge[B-1].append(A-1)
    print(Con(N,Edge))

Submission status: Accepted

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

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)
result = 0
for i in range(N):
  s = UF.size(i)
  if s>0:
    result = max(result, s)
print(result)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
# n=int(stdin.readline())
def dfs(src):
    global sz
    vis[src]=1
    sz+=1
    for neigh in g[src]:
        if not vis[neigh]:
            dfs(neigh)

n,eg=list(map(int,stdin.readline().split()))
g=defaultdict(list)
for i in range(eg):
    A,B=map(int,stdin.readline().split())
    g[A]+=[B]
    g[B]+=[A]
vis=[0]*(n+1);ans=0
for node in range(1,n+1):
    if not vis[node]:
        sz=0
        dfs(node)
        ans=max(ans,sz)
print(ans)

Submission status: Accepted

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

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

    def maxGroup(self):
        return -min(self.parents)

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)

print(uf.maxGroup())

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:
import sys
from sys import exit
from math import gcd, factorial, ceil, floor, sqrt
from bisect import bisect_left, bisect_right
from copy import deepcopy
from heapq import heapify, heappop, heappush
from itertools import permutations, combinations, product, accumulate
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(10**7)

ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def count(self, x):
        return -self.table[self._root(x)]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


N, M = mi()
ins = UnionFind(N)
for i in range(M):
    a, b = mi()
    a, b = a-1, b-1
    ins.union(a, b)
ans = 0
for i in range(N):
    ans = max(ans, ins.count(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)]
 
    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())
    uf = UnionFind(N+1)

    for i in range(M):
        A, B = map(int, input().split())
        uf.union(A, B)
    # print(uf.all_group_members())
    # print(uf.parents)
    ans = -min(uf.parents)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
f = [i for i in range(n + 1)]
def getF(u):
    i = u
    while f[i] != i:
        i = f[i]
    j = u
    while f[j] != j:
        oj = j
        j = f[j]
        f[oj] = i
    return i
def uniF(u, v):
    u = getF(u)
    v = getF(v)
    if u != v:
        f[u] = v
for i in range(m):
    u, v = map(int, input().split())
    uniF(u, v)
c = [0] * (n + 1)
for i in range(1, n + 1):
    c[getF(i)] += 1
print(max(c))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200001)
mod = 10**9 + 7
def go(v):
    global tmp
    tmp += 1
    used[v] = True
    for i in range(len(g[v])):
        if not used[g[v][i]]:
            go(g[v][i])
def solve():
    n, m = map(int, input().split())
    global g, used, tmp
    tmp = 0
    g = [[] for i in range(n + 1)]
    ans = 0
    d = {}
    used = [False for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        if (x, y) not in d:
            g[x].append(y)
            g[y].append(x)
            d[(x, y)] = 1
    for i in range(1, n + 1):
        if not used[i]:
            tmp = 0
            go(i)
            ans = max(ans, tmp)
    print(ans)
t = 1
while t > 0:
    solve()
    t -= 1

Submission status: Accepted

Solution code:
n,m = 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)]
mx = 0
for _ in range(m):
    s,t = map(int,input().split())
    unite(s,t)
for i in range(1,n+1):
    ans = size(i)
    if ans > mx:
        mx = ans
print(mx)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.setSize = [1] * n
        self.numSets = n
        self.rank = [0] * n
        self.p = [i for i in range(n)]
    def findSet(self, i):
        if self.p[i] == i:
            return i
        else:
            self.p[i] = self.findSet(self.p[i])
            return self.p[i]
    def isSameSet(self, i, j):
        return self.findSet(i) == self.findSet(j)
    def unionSet(self, i, j):
        if not self.isSameSet(i, j):
            self.numSets -= 1
            x = self.findSet(i)
            y = self.findSet(j)
            if self.rank[x] > self.rank[y]:
                self.p[y] = x
                self.setSize[x] += self.setSize[y]
            else:
                self.p[x] = y
                self.setSize[y] += self.setSize[x]
                if self.rank[x] == self.rank[y]:
                    self.rank[y] += 1
    def numDisjointSets(self):
        return self.numSets
    def sizeOfSet(self, i):
        return self.setSize[self.findSet(i)]

n, m = [int(i) for i in input().split()]
uf = UnionFind(n)
for i in range(m):
    a, b = [int(i)-1 for i in input().split()]
    uf.unionSet(a,b)
ans = 0
for i in range(n):
    ans = max(ans, uf.sizeOfSet(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):
        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())

union = UnionFind(N)

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

ans = 0

for children_minus in union.parents:
    if children_minus < 0:
        ans = max(children_minus * -1, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

MOD = 10**9 + 7
def main():
	n, k = read()
	par = defaultdict(int)
	for i in range(1, n+1):par[i] = i
	def find(x):
		while par[x] != x:
			par[x] = par[par[x]]
			x = par[x]
		return(x)
	for q in range(k):
		x, y = read()
		par[find(x)] = find(y)
	size = defaultdict(int)
	for i in range(1, n+1):
		size[find(i)] += 1
	print(max(size.values()))




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 all_group_size(self):
        return [len(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())
tree = UnionFind(n)
ans = 1
for _ in range(m):
    i,j = map(int, input().split())
    tree.union(i-1,j-1)
    ans = max(ans,tree.size(i-1))
print(ans)

Submission status: Accepted

Solution code:
class DisjointSet:
    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, *AB = map(int, open(0).read().split())
ds = DisjointSet(N)
for a, b in zip(*[iter(AB)] * 2):
    ds.union(a - 1, b - 1)
print(-min(p for p in ds.parents))

Submission status: Accepted

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

    def find(self, x):
        while self.root[x] >= 0:
            x = self.root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.root[x] = y
            self.size[y] += self.size[x]
        else:
            self.root[y] = x
            self.size[x] += self.size[y]

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

uf = UnionFind(N)
for m in range(M):
    A, B = [int(_) - 1 for _ in input().split()]
    uf.union(A, B)

print(max(uf.size))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

ad = [set() for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    ad[a].add(b)
    ad[b].add(a)

visited = [0 for i in range(N+1)]
seen = [0 for i in range(N+1)]

def bfs(u):
    stack = deque([u])
    seen[u] = 1
    cl = 0

    while len(stack) > 0:
        v = stack.popleft()
        visited[v] = 1
        cl += 1

        for w in ad[v]:
            if seen[w] == 0:
                stack.append(w)
                seen[w] = 1

    return cl

m = 0
for i in range(1,N+1):
    if visited[i] == 0:
        count = bfs(i)
        m = max(m, count)

print(m)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
connect = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  connect[a].append(b)
  connect[b].append(a)  
  
#print(connect)  
ans = 0
used = [0] * N
for i in range(N):
  if used[i] == 0:
    used[i] = 1
    ans2 = 1
    queue = [i]
    while queue:
      now = queue.pop()
      for j in connect[now]:
        if used[j] == 0:
          used[j] = 1
          queue.append(j)
          ans2 += 1
      #print(queue, used)    
  ans = max(ans, ans2)        
        
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() )
uf = UnionFind( N )
for i in range( M ):
  a, b = map( int, input().split() )
  uf.union( a - 1, b - 1 )
ret = 0
for i in range(N):
  ret = max( ret, uf.size(i))
print( ret )

Submission status: Accepted

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

tree=[set([]) for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    tree[a-1].add(b-1)
    tree[b-1].add(a-1)

group=[-1]*n
num=-1
ans=0
for i in range(n):
    if group[i]==-1:
        ans_tmp=1
        num+=1
        stack=[i]
        group[i]=num
        while len(stack)>0:
            tmp=stack.pop()

            for j in tree[tmp]:
                if group[j]==-1:
                    stack.append(j)
                    group[j]=num
                    ans_tmp+=1
    ans=max(ans,ans_tmp)
print(ans)

Submission status: Accepted

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

    def root(self, index):
        parent = self.parents[index]
        if ( parent < 0):
            return index
        root = self.root(parent)
        self.parents[index] = root
        return root

    def size(self, index):
        return -1 * self.parents[self.root(index)]

    def add(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return
        if (self.size(A) < self.size(B)):
            A, B = B, A
        self.parents[A] += self.parents[B]
        self.parents[B] = A
N, M = [int(x) for x in input().split()]
AB = [[int(x) - 1 for x in input().split()] for _ in range(M)]
uf = UnionFind(N)
for a, b in AB:
    uf.add(a, b)
s = set()
ans = 1
for i in range(N):
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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

    def find(self, x):
        if self.parents[x] == x:
            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:
            if self.size[x] < self.size[y]:
                x,y = y,x
            self.parents[y] = x
            self.size[x] += self.size[y]

def main():
    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 = [None] * N
    for i in range(N):
        ans[i] = uf.find(i)
    
    l = Counter(ans)
    print(max([*l.values()]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)#必要に応じて

class UnionFind:#再帰上限に引っかかることがあるので
    def __init__(self,n):
        self.l=list(range(n))
        self.n=n
        self.size=[1 for i in range(n)]
    def find(self,x):
        if self.l[x]==x:
            return x
        self.l[x]=self.find(self.l[x])
        return self.l[x]
    def union(self,x,y):
        if x==y:return
        if self.size[x]<self.size[y]:
            return self.union(y,x)
        a,b=self.find(x),self.find(y)
        if self.l[a]!=b:
            self.l[a]=b
            self.size[b]+=self.size[a]
    def isSame(self,x,y):
        return self.find(x)==self.find(y)
    def getsize(self,x):
        return self.size[x]

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    u.union(*map(lambda z:int(z)-1,input().split()))
ans=1
for i in range(n):
    ans=max(ans,u.size[i])
    #print("size",u.size[i],i)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

t=UnionFind(n)

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if 0 > x]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
	
N, M = MAP()
AB = [LIST() for _ in range(M)]

tree = UnionFind(N)
for A, B in AB:
	tree.union(A-1, B-1)

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
hist = [0 for _ in range(N+1)]
cnt = 1
for i in range(1,N+1):
    if hist[i]==0:
        que = deque([i])
        hist[i]=cnt
        while que:
            x = que.popleft()
            for y in G[x]:
                if hist[y]==0:
                    que.append(y)
                    hist[y] = cnt
        cnt += 1
C = {}
for i in range(1,N+1):
    c = hist[i]
    if c not in C:
        C[c] = 0
    C[c] += 1
cmax = 0
for c in C:
    cmax = max(cmax,C[c])
print(cmax)