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:
# coding: utf-8
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        # xの根を探索
        if self.parents[x] < 0:
            return x
        else:
            # 再帰的に根を探索
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        # 2つの木をマージする。
        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 are_same(self, x, y):
        # 2つの要素の根が同じかどうかを調べる
        return self.find(x) == self.find(y)

    def members(self, x):
        # xと同じ根の要素をリストで出力
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == self.n]

    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)
ans = 0
for v in uf.parents:
    if v < 0:
        ans = max(ans, abs(v))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
inp = lambda : stdin.readline().strip()


def dfs_iter(n):
    stack = [n]
    ans = 0
    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            ans += 1
            for child in adj[node]:
                if not visited[child]:
                    stack.append(child)
    return ans

n, m = [int(x) for x in inp().split()]
adj = [set() for i in range(n)]
visited = [False]*n
for i in range(m):
    u, v = [int(x) for x in inp().split()]
    adj[u - 1].add(v - 1)
    adj[v - 1].add(u - 1)
ans = 0
for i in range(n):
    if not visited[i]:
        ans = max(ans, dfs_iter(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())

class UnionFind():
  par = []
  sizes = []

  def __init__(self, N):
    self.par = [i for i in range(N)]
    self.sizes = [1 for _ in range(N)]

  def root(self, x: int)-> int:
    if (self.par[x] == x):
      return x
    self.par[x] = self.root(self.par[x])
    return self.par[x]

  def unite(self, x: int, y: int):
    rootX = self.root(x)
    rootY = self.root(y)
    if rootX == rootY:
      return
    self.par[rootX] = rootY
    self.sizes[rootY] += self.sizes[rootX]

  def maxSize(self)-> int:
    return max(self.sizes)

def friends(N, As):
  uf = UnionFind(N)
  setAs = list(set(As))
  for val in setAs:
    uf.unite(val[0]-1, val[1]-1)
  # ans = 0
  ans = uf.maxSize()
  # for i in range(N):
  #   temp = uf.size(i)
  #   if ans < temp:
  #     ans = temp
  return ans

if __name__ == "__main__":
  nm = list(map(int, input().split()))
  As =[tuple(map(int, input().split())) for _ in range(nm[1])]
  print(friends(nm[0], As))

Submission status: Accepted

Solution code:
from collections import defaultdict 

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

dp = [-1]*n

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    
    if rx == ry:
        return False
        
    if dp[rx] > dp[ry]:
        rx,ry = ry,rx
        
    dp[rx] += dp[ry]
    dp[ry] = rx
    return True

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

for i in range(m):
    a,b = map(int, input().strip().split(" "))
    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:
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())

# class UnionFind():
#   par = []
#   sizes = []

#   def __init__(self, N):
#     self.par = [i for i in range(N)]
#     self.sizes = [1 for _ in range(N)]

#   def root(self, x: int)-> int:
#     if (self.par[x] == x):
#       return x
#     return self.root(self.par[x])

#   def unite(self, x: int, y: int):
#     rootX = self.root(x)
#     rootY = self.root(y)
#     if rootX == rootY:
#       return
#     self.par[rootX] = rootY
#     self.sizes[rootY] += self.sizes[rootX]

#   def maxSize(self)-> int:
#     return max(self.sizes)

def friends(N, As):
  uf = UnionFind(N)
  setAs = list(set(As))
  for val in setAs:
    uf.union(val[0]-1, val[1]-1)
  ans = 0
  for i in range(N):
    temp = uf.size(i)
    if ans < temp:
      ans = temp
  return ans

if __name__ == "__main__":
  nm = list(map(int, input().split()))
  As =[tuple(map(int, input().split())) for _ in range(nm[1])]
  print(friends(nm[0], As))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
class dsu:
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.sz = [1] * n
    def find(self,a):
        if self.par[a] == a:
            return a
        self.par[a] = self.find(self.par[a])
        return self.par[a]
    def unite(self,a,b):
        a = self.find(a)
        b = self.find(b)
        if a != b:
            if self.sz[b] > self.sz[a]:
                a,b = b,a
            self.par[b] = a
            self.sz[a] += self.sz[b]
d = dsu(n)            
for i in range(m):
    u,v = map(int,input().split())
    d.unite(u-1,v-1)
    
print(max(d.sz) if m else 1)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [-1 for i in range(n)]
    
    def root(self, x):
        if self.parent[x] <0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    
    def same(self, x, y):
        return (self.root(x) == self.root(y))

    def union(self, x, y):
        p = self.root(x)
        q = self.root(y)
        
        if not p==q :
            if self.parent[p] > self.parent[q]:
                p,q = q,p
            self.parent[p] += self.parent[q]
            self.parent[q] = p
    
    def size(self, x):
        return -self.parent[self.root(x)]



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

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

ans = -1
for i in range(N):
    s = uf.size(i)
    if s > ans:
        ans = s

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n + 1)]
        self.size = [1] * (n + 1)
    def find(self, x):
        y = self.root[x]
        if x == y:
            return x
        else:
            z = self.find(y)
            self.root[x] = z
            return z
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        sx = self.size[rx]
        sy = self.size[ry]
        if rx == ry:
            return 0
        else:
            if sx >= sy:
                self.root[ry] = rx
                self.size[rx] = sx + sy
            else:
                self.root[rx] = ry
                self.size[ry] = sx + sy
        return sx * sy
    def check(self):
        print([self.find(i) for i in range(1, len(self.root))])

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

uf = UnionFind(N)

for a, b in AB:
    uf.union(a, b)

cnt = [0] * (N + 1)
for i in range(1, N + 1):
    cnt[uf.find(i)] += 1
    
print(max(cnt))

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n + 1)]
        self.size = [1] * (n + 1)
    def find(self, x):
        y = self.root[x]
        if x == y:
            return x
        else:
            z = self.find(y)
            self.root[x] = z
            return z
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        sx = self.size[rx]
        sy = self.size[ry]
        if rx == ry:
            return 0
        else:
            if sx >= sy:
                self.root[ry] = rx
                self.size[rx] = sx + sy
            else:
                self.root[rx] = ry
                self.size[ry] = sx + sy
        return sx * sy
    def check(self):
        print([self.find(i) for i in range(1, len(self.root))])

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

uf = UnionFind(N)

for a, b in AB:
    uf.union(a, b)

cnt = [0] * (N + 1)
for i in range(1, N + 1):
    cnt[uf.find(i)] += 1
print(max(cnt))

Submission status: Accepted

Solution code:
'''
Created on 2020/09/03

@author: harurun
'''
from dataclasses import *
@dataclass
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():
  import sys
  pin=sys.stdin.readline

  N,M=map(int,pin().split())
  uf=UnionFind(N)
  for i in range(M):
    A,B=map(int,pin().split())
    A-=1
    B-=1
    uf.union(A, B)

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

main()

#解説AC

Submission status: Accepted

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

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

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

    def union(self, x, y):
        if x > y:
            x, y = y, x
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx

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

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

    def return_par(self):
        return self.par

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)

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=[i for i in range(n+1)]
def r(x):
    if root[x]==x:
        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
    if x>y:
        x,y=y,x
    root[y]=x

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

    unite(x,y)
ans=0
size=[0]*(n+1)
for i in range(n):
    size[r(i+1)]+=1

for i in range(n):
    ans=max(ans,size[i+1])

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
n,m = map(int, input().split())

q = [0]*(n+1)

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

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

# if m == 0:
#     print(1)
#     exit()

d = deque()
a = 0
for l,j in enumerate(q):
    b = set()
    if j == 0:
        d.append(l)
        while d:
            v = d.popleft()
            b.add(v)
            q[v] = -1

            for i in graph[v]:
                b.add(i)
                q[i] = -1

                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
        a = max(a,len(b))
print(a)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
n,m = map(int, input().split())

q = [0]*(n+1)

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

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

if m == 0:
    print(1)
    exit()

d = deque()
a = 0
for l,j in enumerate(q):
    b = set()
    if j == 0:
        d.append(l)
        while d:
            v = d.popleft()
            b.add(v)
            q[v] = -1

            for i in graph[v]:
                b.add(i)
                q[i] = -1

                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
        a = max(a,len(b))
print(a)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

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

ans = max(uf.get_size(i) for i in range(N))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,M=map(int,input().split())
G=UnionFind(N)
for i in range(M):
    a,b=map(int,input().split())
    G.unite(a-1,b-1)
D=dict()
for i in range(N):
    if G.find(i) in D:
        D[G.find(i)]+=1
    else:
        D[G.find(i)]=1
X=[]
for k in D:
    X.append(D[k])
print(max(X))

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    uft = UnionFindTree(N)
    for _ in range(M):
        A, B = map(int, input().split())
        uft.unite(A-1, B-1)
    ans = 0
    for g in uft.groups():
        ans = max(ans, len(g))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return
    
    if rank[a]<rank[b]:
        par[a]=b
        rank[b]+=rank[a]
        rank[a]=rank[b]
    else:
        par[b]=a
        rank[a]+=rank[b]
        rank[b]=rank[a]

    return

def chk(a,b):
    if par[a]==par[b]:
        print('Yes')
    else:
        print('No')

    return

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

par=(list(range(N+1)))
rank=[1]*(N+1)

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

print(max(rank))

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,m=nii()
l=[lnii() for i 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 same(self, x, y):
        return self.find(x) == self.find(y)

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

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

uf=UnionFind(n)
for a,b, in l:
  a-=1
  b-=1
  if uf.same(a,b)==False:
    uf.union(a,b)

ans=0
roots=uf.roots()
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.r = [-1 for _ in range(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 _ in range(m):
    a, b = map(int, input().split())
    uf.unite(a - 1, b - 1)

max_friend = -min(uf.r)

print(max_friend)

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
f=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  f[a].append(b)
  f[b].append(a)
q=deque()

for i in range(n):
  for j in f[i]:
    q.append(j)
  while q:
    p=q.popleft()
    if i!=p:
      f[i]+=f[p]
      for k in f[p]:
        q.append(k)
      f[p]=[]
ans=1
for i in f:
  cnt=len(list(set(i)))
  ans=max(cnt,ans)
print(ans)

Submission status: Accepted

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

N,Q=map(int,input().split())
par=[i for i in range(N+1)]
def find(x):
    if par[x] ==x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x]=y
for i in range(Q):
    a,b=map(int,input().split())
    unite(a,b)
ans=dict()
for i in par:
    tmp=find(i)
    if tmp in ans:
        ans[tmp]+=1
    else:
        ans[tmp]=1
print(max(ans.values()))

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

union = UnionFind(n)
for _i in range(m):
    a, b = map(int, input().split())
    union.union(a-1, b-1)
print(max(union.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

    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)
ans = 0
for j in range(n):
    check = uf.size(j)
    if ans < check:
        ans = check
print(ans)

Submission status: Accepted

Solution code:
#n = int(input())
from collections import deque
n, m = map(int, input().split())
# n=200000
# m=200000
#al = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
adjl = [[] for _ in range(n+1)]
NIL = -1
appear = {}
isalone = {}
for i in range(m):
    a, b = map(int, input().split())
    if appear.get((a, b), False) or appear.get((a, b), False):
        continue
    appear[(a, b)] = True
    appear[(b, a)] = True
    isalone[a] = False
    isalone[b] = False
    adjl[a].append(b)
    adjl[b].append(a)

NIL = -1  # 未発見を示す値
d = [-1 for i in range(n+1)]  # 頂点1からの距離を格納するリスト
color = [NIL for i in range(n+1)]  # 未到達かを示すリスト


def bfs(start_node, color_id):  # uは探索の開始点
    global color, d
    q = deque([start_node])
    d[start_node] = 0
    color[start_node] = color_id
    while len(q) != 0:
        u = q.popleft()
        for v in adjl[u]:
            if color[v] == NIL:
                d[v] = d[u]+1
                color[v] = color_id
                q.append(v)


color_id = 0
for u in range(1, n+1):
    if color[u] == NIL:
        color_id += 1
        bfs(u, color_id)

group = {}
for i in range(1, n+1):
    if isalone.get(i, True):
        continue
    group[color[i]] = group.get(color[i], 0)+1

mx = 1
for k, v in group.items():
    mx = max(mx, v)

print(mx)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
graph = [set() for _ in range(n)]
for _ in range(m):
	a, b = map(int , input().split())
	if (b-1) not in graph[a-1]: graph[a-1].add(b-1)
	if (a-1) not in graph[b-1]: graph[b-1].add(a-1)
clusters = 0
v = [False]*n
for i in range(n):
	if not v[i]:
		v[i] = True
		q = deque([i])
		cluster = 0
		while q:
			node = q.popleft()
			cluster+=1
			for j in graph[node]:
				if not v[j]: v[j] = True; q.append(j)
		clusters = max(clusters, cluster)
print(clusters)