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

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


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,ipt().split())
    uf = UnionFind(n+1)
    for i in range(m):
        a,b = map(int,ipt().split())
        uf.union(a,b)

    print(-min(uf.parents))

    return None

if __name__ == '__main__':
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


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,ipt().split())
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,ipt().split())
        uf.union(a-1,b-1)

    print(-min(uf.parents))

    return None

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

ad_sum_array = [0] * n
ad_array = [set() for _ in range(n)]

for ab in ab_array:
    a, b = ab
    ad_array[a - 1].add(b - 1)
    ad_array[b - 1].add(a - 1)

check_array = [False] * n

def bfs(node_num):
    queue = deque([node_num])
    check_array[node_num] = True
    num = 1

    while queue:
        node = queue.popleft()
        for ad in ad_array[node]:
            if not check_array[ad]:
                check_array[ad] = True
                queue.append(ad)
                num += 1
    return num

ans = 0
for i in range(n):
    if not check_array[i]:
        ans = max(ans, bfs(i))

print(ans)

Solution (Python):
N, M = map(int, input().split())

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

def find(x):
  if par[x] == x:
    return x
  else:
    return find(par[x])
  
def unite(x,y):
  x = find(x)
  y = find(y)
  
  if x == y:
    return
  if rank[x]<rank[y]:
    x,y = y,x
  par[y] = x
  size[x] += size[y]
  if rank[x]==rank[y]:
    rank[x]+=1
    
for i in range(M):
  a,b = [int(i)-1 for i in input().split()]
  unite(a,b)
  
print(max(size))

Solution (Python):
N, M = map(int, input().split())

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

def find(x):
  if par[x] == x:
    return x
  else:
    return find(par[x])
  
def unite(x,y):
  x = find(x)
  y = find(y)
  
  if x == y:
    return
  if rank[x]<rank[y]:
    par[x]=y
    size[y]+= size[x]
  else:
    par[y] = x
    size[x] += size[y]
    if rank[x]==rank[y]:
      rank[x]+=1
    
for i in range(M):
  a,b = [int(i)-1 for i in input().split()]
  unite(a,b)
  
print(max(size))

Solution (Python):
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

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 all_group_memberss(self):
        return [self.size(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 = [int(x) for x in input().split()]
    AB = [[int(x) for x in input().split()] for _ in range(M)]

    uf = UnionFind(N)

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

    hq = []
    for k in uf.all_group_memberss():
        heapq.heappush(hq, k)

    ans = 0
    prev = 0
    while hq:
        c = heapq.heappop(hq)
        if prev != c:
            ans += (c - prev)
            prev = c

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline


class UnionFind:

    def __init__(self, N):
        self.parents = list(range(N))
        self.depth = [0] * N

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

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

        if self.depth[x] == self.depth[y]:
            self.depth[x] += 1
            self.parents[y] = x
        elif self.depth[x] > self.depth[y]:
            self.parents[y] = x
        else:
            self.parents[x] = y


def main():
    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)
    num = [0] * N
    for i in range(N):
        p = uf.find(i)
        num[p] += 1
    ans = max(num)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * size
        self.rank = [1] * size
        self.groups = size

    def get_root(self, node):
        parent = self.parent[node]
        if parent == -1:
            root = node
        else:
            root = self.get_root(parent)
            self.parent[node] = root  
        return root

    def in_same_group(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        return root1 == root2

    def unite(self, node1, node2):
        if self.in_same_group(node1, node2):
            return
        main_root = self.get_root(node1)
        sub_root = self.get_root(node2)
        if self.rank[main_root] < self.rank[sub_root]:  
            main_root, sub_root = sub_root, main_root

        self.parent[sub_root] = main_root
        self.rank[main_root] += self.rank[sub_root]
        self.groups -= 1


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

    ans = max(uf.rank)
    print(ans)


if __name__ == "__main__":
    main()

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

N,Q = map(int,input().split())
par = [i for i in range(N)]
rank = [0]*(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
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x]==rank[y]:rank[x]+=1

for _ in range(Q):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  unite(a,b)
from collections import Counter
a=[-1]*N
for i in range(N):
  a[i]=find(i)
ca=Counter(a)
ans=0
for c in ca.values():
  ans=max(ans,c)
print(ans)

Solution (Python):
import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N,M = LI()
AB = [LI() for _ in range(M)]

ans = 0

par = [0]*N


def init(n):
    for i in range(n):
        
        par[i]=-1
        


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

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

    
    
    
    
    
    

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

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

init(N)

for r in AB:
    f = r[0]-1
    t = r[1]-1
    unite(f,t)
    

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

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self._size = [1]*N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_sama(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self._size[rb] += self._size[ra]
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
            self._size[ra] += self._size[rb]
        self.count += 1
    def print_info(self):
        print("parent", self.parent)
        print("rank", self.rank)
        print("count", self.count)
        print("size", self._size)
    def size(self,a):
        return self._size[self.root(a)]

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.unite(a,b)
ans = 0
for i in range(N):
    ans = max(ans,uf.size(i))
print(ans)

Solution (Python):
class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return x
  
  def same(self,x,y):
    return self.root(x)==self.root(y)
  
  def unite(self,x,y):
    x=self.root(x)
    y=self.root(y)
    if x==y:
      return
    if self.size[x]>self.size[y]:
      
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(self.root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)
    
import sys
readline = sys.stdin.readline

N,M = map(int,readline().split())
UF = UnionFind(N)

for i in range(M):
  a,b = map(int,readline().split())
  UF.unite(a - 1, b - 1)
  
roots = UF.get_roots()
ans = 0
for r in roots:
  s = UF.get_group_size(r)
  if ans < s:
    ans = s
    
print(ans)

Solution (Python):





N, M = list(map(int, input().split()))
R = [[] for _ in range(N+1)]
G = [0] * (N+1)
Z = [0] * (N+1)

def grp(R, grpid, i, G, Z):
    stack = [i]
    while len(stack) > 0:
        k = stack.pop()
        if G[k] > 0: continue
        G[k] = grpid
        Z[grpid] += 1
        for l in range(len(R[k])):
            stack.append(R[k][l])
        
for i in range(M):
    a, b = list(map(int, input().split()))

    R[a].append(b)
    R[b].append(a)

grpid = 0
for i in range(1, N+1):
    if G[i] > 0: continue
    grpid += 1
    grp(R, grpid, i, G, Z)
    
Z.sort(reverse=True)
print(Z[0])

Solution (Python):

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

n,m=map(int, input().split())
uf=UnionFind(n)
for _ in range(m):
    ai,bi=map(int, input().split())
    uf.union(ai,bi)

cnt=[0]*(n+1)

for i in range(n+1):
    cnt[uf.find(i)]+=1
print(max(cnt))

Solution (Python):
import sys
import numpy as np
i4 = np.int32
i8 = np.int64


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.types import Array, int64
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', (Array(int64, 2, 'C'), int64))
    def solve(ab, N):
        parents = np.arange(N)
        depth = np.zeros(N, i8)

        def uf_find(x):
            while True:
                if parents[x] == x:
                    return x
                else:
                    x = parents[x]

        def uf_union(x, y):
            x = uf_find(x)
            y = uf_find(y)
            if x == y:
                return

            if depth[x] == depth[y]:
                depth[x] += 1
                parents[y] = x
            elif depth[x] > depth[y]:
                parents[y] = x
            else:
                parents[x] = y

        for i in range(ab.shape[0]):
            uf_union(ab[i, 0], ab[i, 1])
        num = np.zeros(N, i8)
        for i in range(N):
            p = uf_find(i)
            num[p] += 1
        return np.amax(num)

    cc.compile()
    exit(0)
else:
    from my_module import solve


def main(in_file):
    stdin = open(in_file)
    N, M = [int(x) for x in stdin.readline().split()]
    ab = (np.fromstring(stdin.read(), i8, sep=' ') - 1).reshape(-1, 2)
    ans = solve(ab, N)
    print(ans)


if __name__ == '__main__':
    main(0)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.componentCount = size

    def root(self, index):
        if self.parent[index] == index:  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2):  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2:  
            return

        self.componentCount -= 1  

        if self.height[root1] < self.height[root2]:
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else:
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2]:
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2):
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index):
        return self.size[self.root(index)]

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

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

ans = 1
for i in range(N):
    ans = max(ans, tree.sizeOfSameRoot(i))
print(ans)