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:
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())
    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:
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """要素xを含む集合の要素数を求める"""
        return -self.parent[self.root(x)]

    def get_cnt(self):
        """集合の個数を求める"""
        return self.cnt


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


uf = UnionFind(n)
for u, v in edges:
    u -= 1
    v -= 1
    uf.merge(u, v)

ans = 0
for i in range(n):
    ans = max(uf.get_size(i), ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n,m=map(int,input().split())
f=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)
g=[0]*(n+1)
p=[0]*(n+1)
for i in range(1,n+1):
    if p[i]==0:
        p[i]=i
        data=[i]
        data=deque(data)
        while len(data)>0:
            pos=data.popleft()
            p[pos]=i
            for j in f[pos]:
                if p[j]==0:
                    data.append(j)
            f[pos]=[]
for i in range(n):
    g[p[i+1]]+=1
print(max(g))

Submission status: Accepted

Solution code:
from _collections import deque

n,m=map(int,input().split())
f=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)
g=[0]*(n+1)
p=[0]*(n+1)
for i in range(1,n+1):
    if p[i]==0:
        p[i]=i
        data=[i]
        data=deque(data)
        while len(data)>0:
            pos=data.popleft()
            p[pos]=i
            for j in f[pos]:
                if p[j]==0:
                    data.append(j)
            f[pos]=[]
for i in range(n):
    g[p[i+1]]+=1
print(max(g))

Submission status: Accepted

Solution code:
#D - Friends
N,M = map(int,input().split())
par = [i for i in range(N)]
rank = [1] * (N)

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def size(x):
    return par.count(find(x))

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y : return 0
    if par[x] > par[y]:
        x,y = y,x
    par[y] = x
#    par[x] = x
    if par[x] == par[y]:
        rank[x] += rank[y]
#        rank[y] += rank[x]
#print(par)
#print(rank)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
#    print(par)
#    print(rank)
group_count = 0

group_count = max(rank)

# 出力
print(group_count)

Submission status: Accepted

Solution code:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque, defaultdict
from fractions import gcd
from functools import reduce
from itertools import groupby, combinations
from heapq import heapify, heappush, heappop

#sys.setrecursionlimit(30000)

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return list(map(lambda x: x + d, A))
def ldec(A, d=1): return list(map(lambda x: x - d, A))

N, M = nn()
T = nm(M)

for i in range(M):
    T[i][0] -= 1
    T[i][1] -= 1

dic = defaultdict(list)

m = {}
for i in range(M):
    if (T[i][0], T[i][1]) in m:
        continue
    m[(T[i][0], T[i][1])] = True
    dic[T[i][0]].append(T[i][1])
    dic[T[i][1]].append(T[i][0])

def search(n):
    ret = 1
    deq = deque()

    memo[n] = 1
    for t in dic[n]:
        if memo[t] == 0:
            memo[t] = 1
            deq.append(t)

    while len(deq) != 0:
        d = deq.pop()
        ret += 1
        for t in dic[d]:
            if memo[t] == 0:
                memo[t] = 1
                deq.append(t)

    return ret

memo = array1(N)

ans = 0
for i in range(N):
    if memo[i] == 1:
        continue

    ans = max(search(i), ans)

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 = list(map(int,input().split()))
Network = UnionFind(N)

out = 0
for i in range(M):
    a, b = list(map(int,input().split()))
    Network.union(a-1, b-1)
print(-1*min(Network.parents))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep  3 20:46:45 2020

@author: liang
"""


class UnionFind():
    def __init__(self, N):
        self.N = 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, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return self
        if self.par[a] > self.par[b]:
            a, b = b, a
        self.par[a] += self.par[b]
        self.par[b] = a
    
    def same(self, a, b):
        a = self.find(a)
        b = self.find(b)
        return a == b
    
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 = -min(uf.par)
print(ans)

Submission status: Accepted

Solution code:
import numpy

class UnionFind:
    def __init__(self, N):
        self.N = N

        # the parent of all node is itself
        # self.parent = list(range(N))
        self.parent = [-1] * N

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

        r = self.root(self.parent[i])
        self.parent[i] = r
        return r

    def unite(self, i, j):
        # print('root {}, {} = '.format(i, j), end='')
        i = self.root(i)
        j = self.root(j)
        # print(i, j)

        if i == j:
            return

        if i > j:
            i, j = j, i

        self.parent[i] += self.parent[j]
        self.parent[j] = i
        # print(self.parent)

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def size(self, i):
        return -self.parent[self.root(i)]

N, M = map(int, input().split())
R = numpy.array([[int(r) for r in input().split()] for _ in range(M)]) - 1

forest = UnionFind(N)
for p1, p2 in R:
    forest.unite(p1, p2)

s = [forest.size(i) for i in range(N)]
print(max(s))

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
##########################################################
from collections import Counter
# c=sorted((i,int(val))for i,val in enumerate(input().split()))
import heapq
# c=sorted((i,int(val))for i,val in enumerate(input().split()))
# n = int(input())
# ls = list(map(int, input().split()))
#n=int(input())
#arr = list(map(int, input().split()))

#for _ in range(int(input())):

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


def unioin(x,y):
    uroot=find(u,root)

    vroot=find(v,root)

    if uroot!=vroot:
        if rank[uroot]>rank[vroot]:
            root[vroot]=root[uroot]
            rank[uroot]+=rank[vroot]
        elif rank[vroot]>rank[uroot]:
            root[uroot]=root[vroot]
            rank[vroot]+=rank[uroot]
        else:
            rank[uroot]+=rank[vroot]
            root[vroot]=root[uroot]




n,m= map(int, input().split())
rank=[1]*(n+1)
root=[i for i in range(n+1)]
for i in range(m):
    u,v = map(int, input().split())
    unioin(u,v)
ans=0
print(max(rank))

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
par = [-1 for i in range(n + 1)]
par[0] = 0
def find(x):
    if (par[x] < 0):
        return x
    else:
        x = par[x]
        return find(x)
def unit(x, y):
    if (find(x) == find(y)):
        pass
    else:
        x = find(x)
        y = find(y)
        if (x > y):
            x, y = y, x
        s = par[y]
        par[y] = x
        par[x] = par[x] + s

for i in range(m):
    a, b = map(int,input().split())
    unit(a, b)

par.sort()
print(-par[0])

Submission status: Accepted

Solution code:
def root(x):
  if F[x] < 0:
    return x
  else:
    F[x] = root(F[x])
    return F[x]

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

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

for m in range(M):
  a, b = map(int, input().split())
  unite(a - 1, b - 1)
ans = 0
for f in F:
  ans = min(ans, f)
print(-ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
r = [i for i in range(N+1)]
n = [0 for i in range(N+1)]
buf = []

def root(x):
  if x==r[x]:
    return x
  else:
    r[x] = root(r[x])
    return r[x]

def unite(x, y):
  rx = root(x)
  ry = root(y)
  if rx < ry:
    r[ry] = rx
  elif rx > ry:
    r[rx] = ry
    

for _ in range(M):
  a, b = map(int, input().split())
  unite(a, b)

for x in range(1, N+1):
  if r[x] != x and r[r[x]] != r[x]:
    _ = root(x)
  
  
for x in r[1:]:
  n[x] += 1
    
ans = max(n[1:])

print(ans)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in 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())

uf = UnionFind(n)
for i in range(m):
    a, b = [int(i) for i in input().split()]
    uf.union(a-1, b-1)

print(-1 * min(uf.parents))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
f = [[] for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    f[A-1].append(B-1)
    f[B-1].append(A-1)
from collections import deque
d = deque()
x = [-1]*N
for i in range(N):
    if x[i] == -1:
        x[i] = i
        d.append(f[i])
    while len(d) > 0:
        z = d.popleft()
        for j in z:
            if x[j] == -1:
                x[j] = i
                d.append(f[j])
import collections
ans = collections.Counter(x)
print(ans.most_common()[0][1])

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 _ in range(m):
        a, b = map(int, input().split())
        uf.union(a, b)
    ans = -min(uf.parents)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
 
N, M = map(int, input().split())
g = {i:set() for i in range(N)}
v = [-1 for i in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  g[a].add(b)
  g[b].add(a)
  
Q = deque()
ans = 0
for a in g:
  if v[a]==-1:
    v[a] = 1
    ans_tmp = 1
    Q.append(a)
    while len(Q)>0:
      na = Q.popleft()
      for nb in g[na]:
        if v[nb] == -1:
          v[nb] = 1
          ans_tmp += 1
          Q.append(nb)
    ans = max(ans, ans_tmp)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (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 x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            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 i in range(m):
    a,b = map(int,input().split())
    uf.union(a,b)
print(max(uf.size))

Submission status: Accepted

Solution code:
# D - Friends
def add_to_graph(A, B):
  global graph

  graph.setdefault(A, [])
  graph[A].append(B)


def add_to_group(p):
  global que
  global group
  global is_finished

  que.append(p)
  group.add(p)
  is_finished[p] = True


from collections import deque

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

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

# その人を探索したかどうかのフラグ
is_finished = [False] * (N + 1)
groups = []

for i in range(1, N + 1):
  que = deque()
  group = set()

  if not is_finished[i]:
    add_to_group(i)

    while len(que) > 0:
      p = que.popleft()
  
      if p in graph.keys():
        for v in graph[p]:
          if not is_finished[v]:
            add_to_group(v)
    
      groups.append(group)

ans = 0

for g in groups:
  ans = max(ans, len(g))

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

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

Submission status: Accepted

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).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())

N, M = map(int,input().split())
uf = UnionFind(N)
for k in range(M):
    A, B = map(int,input().split())
    uf.union(A-1,B-1)
ans = 1
for k in range(N):
    ans = max(ans,uf.size(k))
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
    else:
      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
    else:
      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 -1*self.r[self.root(x)]
  
  def print(self):
    print(self.r)


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

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
par = [-1]*(n+1)
for i in range(m):
    a, b = map(int, input().split())
    unite(a, b)
ans = 0
for i in range(1,n+1):
    ans = max(ans, size(i))
print(ans)

Submission status: Accepted

Solution code:

class unionfind():

    def __init__(self,n):
        #親番号<0なら根
        #根の場合、数値の絶対値が要素数
        self.par=[-1 for i in range(n)]
        
    def root(self,x):
        
        par=self.par
        if par[x]<0:
            return x
        else:
            self.x = self.root(par[x])
            return self.x
        
    def unite(self,x,y):
        #高いほうに低いほうをくっつける
        rx=self.root(x)
        ry=self.root(y)
        
        if rx==ry:
            return
        else:
            if self.par[rx]>self.par[ry]:
                rx,ry = ry,rx
                
            self.par[rx]+=self.par[ry]
            self.par[ry] = rx

            
    def same(self, x,y):
        return self.root(x) == self.root(y)
    
    def par_print(self):
        print(self.par)
        
    def count(self, x):
        return -self.root(x)
    
n,m = map(int,input().split())

friend = unionfind(n)

for i in range(m):
    a,b = map(int,input().split())
    friend.unite(a-1,b-1)
    # print(friend.par_print())
    
# print(friend.par_print())

ans = -min(friend.par)

print(ans)

Submission status: Accepted

Solution code:
import sys
import re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

class UnionFind:

    def __init__(self,n):
        self.n = n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

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

    def unite(self,x,y):
        x=self.findRoot(x)
        y=self.findRoot(y)
        if x==y:
            return
        if self.rank[x] > self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def isSameGroup(self,x,y):
        return self.findRoot(x)==self.findRoot(y)

    def count(self,x):
        return -self.root[self.findRoot(x)]


def main():
    N,M=i_map()
    A = []
    B=[]

    for i in range(0,M):
        tmp1,tmp2 = i_map()
        A.append(tmp1-1)
        B.append(tmp2-1)

    u = UnionFind(N)

    for i in range(0,M):
        u.unite(A[i],B[i])

    max = 0
    for i in range(0,N):
        if(max<=u.count(i)):
            max = u.count(i)

    print(max)

    return

if __name__ == '__main__':
    main()

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)