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


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:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,m=map(int,input().split())
    f=[set() for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        f[a-1].add(b-1)
        f[b-1].add(a-1)
    chk=[False]*n
    q=[]
    ans=0
    for i in range(n):
        if chk[i]==True:
            continue
        q.append(i)
        chk[i]=True
        cnt=1
        while q:
            x=q.pop()
            for nx in f[x]:
                if chk[nx]==True:
                    continue
                q.append(nx)
                chk[nx]=True
                cnt+=1
        ans=max(ans,cnt)
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------


n,m = mapi()
gr = defaultdict(list)
sz = [1]*(n+1)
par = {i:i for i in range(n+1)}
def find(a):
    if par[a]==a:return a
    par[a] = find(par[a])
    return par[a]
def union(a,b):
    a = find(a)
    b = find(b)
    if a==b:return
    if sz[a]>sz[b]:a,b = b,a
    sz[b]+=sz[a]
    par[a] = b

for i in range(m):
    x,y = mapi()
    union(x,y)
    # gr[x].append(y)
    # gr[y].append(x)
res = 0
for i in range(1,n+1):
    res = max(res,sz[i])
print(res)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, M = iim()
    it = map(int, sys.stdin.read().split())

    dp = [-1] * N

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

        ans = dp[x] = find(dp[x])
        return ans

    def union(x, y):
        x1 = find(x)
        y1 = find(y)

        if x1 == y1:
            return

        xr = dp[x1]
        yr = dp[y1]
        if xr <= yr:
            dp[y1] = x1
            dp[x1] += yr
        else:
            dp[x1] = y1
            dp[y1] += xr

    for ai, bi in zip(it, it):
        union(ai-1, bi-1)

    d1 = [0]*N
    for i in range(N):
        d1[find(i)] += 1
    print(max(d1))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

R = lambda: map(int, input().split())

n, m = R()
g = [None] + [set() for _ in range(n)]

for _ in range(m):
  u, v = R()
  g[u].add(v)
  g[v].add(u)

V = [None] + [False] * n
q = deque()

def bfs(u):
  r = 0
  V[u] = True
  q.append(u)
  while(q):
    u = q.popleft()
    r += 1
    for v in g[u]:
      if not V[v]:
        V[v] = True
        q.append(v)
  return r

print(max(bfs(u) for u in range(1, n + 1) if not V[u]))

Submission status: Accepted

Solution code:
# abc177_d.py
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

for i in range(M):
    A, B = map(int,input().split())
    uf.Unite(A, B)
M = 0
for i in range(N):
    cnt = uf.Count(i)
    if cnt>M:
        M = cnt

print(M)

Submission status: Accepted

Solution code:
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

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

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


uf = UnionFind()


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

g = list(uf.grouper())

ans = 1
for i in g:
    ans = max(ans, len(i))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードを示す。負は自身が親ということ。親だった場合は−(その集合のサイズ)
        self.parent = [-1] * N

    def root(self, A):
        # Aがどのグループに属しているか調べる
        # ノード番号を受けとって一番上の親ノードの番号を返す
        # print(A)
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        # 自分のいるグループの頂点数を調べる
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # AとBをくっつける
        # AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False  # すでにくっついてるからくっつけない

        if self.size(A) < self.size(B):
            # 大きい方(A)に小さいほう(B)をくっ付けたい
            # 大小が逆だったらひっくり返しちゃう。
            A, B = B, A

        # Aのサイズを更新する
        self.parent[A] += self.parent[B]
        # Bの親をAに変更する
        self.parent[B] = A

        return True

    def same(self, A, B):
        return self.root(A) == self.root(B)


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)

fri = [0] * N
for i in range(N):
    fri[i] = uf.size(i)
# print(fri)
print(max(fri))

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
nm=[[] for _ in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    nm[a].append(b)
    nm[b].append(a)
for i in range(n):
    nm[i]=list(set(nm[i]))
visited=[0]*(n+1)
count=0
for i in range(n):
    if visited[i]==0:
        stack=deque()
        stack.append(i)
        visited[i]+=1
        temp=1
        while stack:
            x=stack.pop()
            
            for j in nm[x]:
                if visited[j]==0:
                    visited[j]+=1
                    stack.append(j)
                    temp+=1
        count=max(temp,count)
print(count)

Submission status: Accepted

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

global fri
fri=[]
global tab
tab=[0]*n
def run(nn):
  #print(tab)
  global cnt
  if tab[nn]:
    return
  tab[nn]=1
  cnt+=1
  for i in fri[nn]:
    que.append(i)
for i in range(n):
  fri.append([])
for i in range(m):
  a,b=map(int,input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
i=0
mx=0

while i<n:
  if tab[i]:
    i+=1
    continue
  que=[i]
  cnt=0
  while len(que)!=0:
    run(que.pop())
  mx=max(cnt,mx)
  i+=1
print(mx)

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

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
INF = float("inf")


def dfs(G, visited, v, cnt):
    visited[v] = True

    for nv in G[v]:
        if visited[nv]:
            continue
        cnt = dfs(G, visited, nv, cnt + 1)
    
    return cnt


# 処理内容
def main():
    N, M = map(int, input().split())

    if M == 0:
        print(1)
        return

    P = set()
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        if a > b:
            a, b = b, a
        P.add((a, b))

    G = [[] for _ in range(N)]
    for pair in P:
        a, b = pair
        G[a].append(b)
        G[b].append(a)

    visited = [False] * N
    ans = 1
    for i in range(N):
        if visited[i]:
            continue
        tmp = dfs(G, visited, i, 1)
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
n, m = map(int, input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
for i in range(m):
    a[i], b[i] = map(int, input().split())

for i in range(m):
    a[i] -= 1
    b[i] -= 1

# union find
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 False
    else:
        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)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

for i in range(m):
    unite(a[i], b[i])

ans = 0
for i in range(n):
    tmp = size(i)
    if ans <= tmp:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a_list=[list(map(int,input().split())) for _ in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n # 各要素の親要素の番号を格納するリストparents 
                                # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    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): # 要素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): # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]
    def same(self, x, y): # 要素x, yが同じグループに属するかどうかを返す
        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) == 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): # print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(n+1)

for i in range(m):
    uf.union(a_list[i][0], a_list[i][1])

max =0
for i in range(n+1):
    if max < uf.size(i):
        max = uf.size(i)
print(max)

Submission status: Accepted

Solution code:
from collections import defaultdict

N,M = map(int,input().split())
fr = [[0]*2 for _ in range(M)]
for i in range(M):
    fr[i][:] = list(map(int,input().split()))
    fr[i][0] -= 1
    fr[i][1] -= 1

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 in range(self.n) if self.parents[i] < 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())

d = UnionFind(N)

for i in range(M):
    a,b = map(int,fr[i])
    d.union(a,b)

M = 0
for i in range(N):
    M = max(M,-d.size(i))
print(M)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N, M = MI()
    relations = [set([]) for i in range(N)]
    for i in range(M):
        a, b = MI()
        a -= 1
        b -= 1
        relations[a].add(b)
        relations[b].add(a)

    grouped = [-1] * N
    group_num = [0] * N

    group = -1

    for i in range(len(grouped)):
        if grouped[i] != -1:
            continue
        deque = cl.deque(relations[i])
        group += 1

        while len(deque) > 0:
            target = deque.popleft()
            friends = relations[target]
            for friend in friends:
                if grouped[friend] != -1:
                    continue
                grouped[friend] = group
                group_num[group] += 1
                deque.append(friend)

    ans = max(group_num)
    print(max(ans, 1))


main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*n
        self.rank = [0]*n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.rank[x-1] > self.rank[y-1]:
            self.root[x-1] += self.root[y-1]
            self.root[y-1] = x
        else:
            self.root[y-1] += self.root[x-1]
            self.root[x-1] = y
            if self.rank[x-1] == self.rank[y-1]:
                self.rank[y-1] += 1

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

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

N,M=map(int,input().split())
T=[tuple(map(int,input().split())) for i in range(M)]
u=UnionFind(N)
for a,b in T:
    u.union(a,b)
ans=0
for i in range(1,N+1):
    ans=max(ans,u.count(i))
print(ans)

Submission status: Accepted

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

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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

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

u = UnionFind(n)

for _ in range(m):
    a,b = map(int, input().split())
    u.unite(a-1,b-1)

print(-min(u.d))

Submission status: Accepted

Solution code:
import sys
import math

N, M = map(int ,sys.stdin.readline().strip().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()}


uf = UnionFind(N)
for m in range(M):
    A, B = map(int, sys.stdin.readline().strip().split())
    A -= 1
    B -= 1
    uf.union(A, B)

ans = 0

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

print(ans)

Submission status: Accepted

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


def search(tree, visited, key):
    visited[key] = True
    sum = 1
    for i in range(len(tree[key])):
        if not visited[tree[key][i]]:
            sum += search(tree, visited, tree[key][i])
    return sum


def main(input, print):
    N, M = map(int, input().split())
    visited = [False] * N
    tree = [[] for _ in range(N)]
    for i in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        tree[A].append(B)
        tree[B].append(A)

    ans = 0
    for i in range(N):
        if visited[i]:
            continue
        ans = max(ans, search(tree, visited, i))

    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

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

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


visited = [-1] * n
lst = []
k = 0
for i in range(n):
    if visited[i] != -1: continue
    visited[i] = k
    temp = [i]
    cnt = 1
    while temp:
        p = temp.pop()
        for q in g[p]:
            if visited[q] != -1: continue
            visited[q] = k
            temp.append(q)
            cnt += 1
    lst.append(cnt)
print(max(lst))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

par=[i for i in range(n)]

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

def union(x,y):
  x=find(x)
  y=find(y)
  if x!=y:
    par[x]=y
 
f=lambda x:int(x)-1
for i in range(m):
  x,y=map(f,input().split())
  union(x,y)
  
for j in range(n):
  find(j)
from collections import Counter
c=Counter(par)
cv=c.values()
print(max(cv))

Submission status: Accepted

Solution code:
from collections import defaultdict

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())
AB = [list(map(int, input().split())) for _ in range(m)]
  
uf = UnionFind(n)
for a, b in AB:
  a -= 1
  b -= 1
  uf.union(a, b)

ans = 0
for v in uf.roots():
  ans = max(ans, uf.size(v))
  
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
from collections import deque 


def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

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 = inpl()
graph = [set() for i in range(N)]
uf = UnionFind(N)
for i in range(M):
    A, B = inpl()
    A, B = A - 1, B - 1 
    uf.union(A, B)

ans = 0
ls = uf.roots()
for i in ls:
    ans = max(ans, uf.size(i))
print(ans)


# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = []
B = []
for i in range(M):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)

par = [-1]*N
#xの根を求める
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)]



for i in range(M):
    unite(A[i]-1, B[i]-1)

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

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
edge=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
visited=[0]*n
def bfs(s):
    q=deque([s])
    visited[s]=1
    cnt=1
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==0:
                visited[nx]=1
                cnt+=1
                q.append(nx)
    return cnt
ans=0
for i in range(n):
    if visited[i]==0:
        ans=max(ans,bfs(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())


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

uf = UnionFind(N)

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


print(-min(uf.parents))


# 2darray [[0] * 4 for i in range(3)]
# import itertools

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)
# print(uf)

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