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:
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):
		ret = defaultdict(list)
		for i in range(self.n):
			ret[self.find(i)].append(i)
		return ret

	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+1)

for _ in range(m):
	a,b = map(int, input().split())
	uf.union(a, b)
MA = 0
for i in range(n+1):
	if MA <= uf.size(i):
		MA = uf.size(i)
print(MA)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
tree = [[] for _ in range(N)]
happend = set()
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    if (a, b) not in happend and (b, a) not in happend:
        tree[a].append(b)
        tree[b].append(a)
        happend.add((a, b))
        happend.add((b, a))
visited = [False]*N
q = deque()
ans = 0
for i in range(N):
    if visited[i]:
        continue
    visited[i] = True
    q.append(i)
    tmp = 1
    while len(q):
        v = q.popleft()
        for e in tree[v]:
            # print("v , e", v, e)
            if visited[e]:
                continue
            visited[e] += 1
            tmp += 1
            q.append(e)
            # print("tmp : ", tmp)
    ans = max(tmp, ans)
# print(tree)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append([a, b])
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):
    uf.union(ab[i][0] - 1, ab[i][1] - 1)
    
ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]

for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
ans = 1
check = [0]*(N+1)
for i in range(1,N+1):
  st = deque([i])
  check[i] = 1
  cnt = 1
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        check[t] = 1
        st.append(t)
        cnt += 1
  ans = max(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す(経路圧縮)
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y: return

        if self.parents[x] > self.parents[y]: x, y = y, x

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

    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x,yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if 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)

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

ans = 0
for c in UF.roots():
    ans = max(ans, UF.size(c))

print(ans)

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self,size):
        self.rank = [None]*size
        self.size = [None]*size
        self.p = [None]*size
        for i in range(size):
            self.make_set(i)
        return
    
    def make_set(self,x):
        self.p[x] = x
        self.rank[x] = 0
        self.size[x] = 1
        return
    
    def same(self,x,y):
        return self.find_set(x) == self.find_set(y)
        
    def unite(self,x,y):
        self.link(self.find_set(x),self.find_set(y))
        return
    
    def link(self,x,y):
        if self.rank[x]>self.rank[y]:
            self.p[y] = x
            self.size[x] += self.size[y]
        else:
            self.p[x] = y
            self.size[y] += self.size[x]
            if self.rank[x]==self.rank[y]:
                self.rank[y] += 1
                
    def find_set(self,x):
        if x != self.p[x]:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]
    

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

for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    if not djs.same(a,b):
        djs.unite(a,b)

print(max(djs.size))

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int,input().split())
par = []
rank = [0] * N
for i in range(N): par.append(i)
def find(x):
    if par[x] == x: 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 0
    if rank[x] < rank[y]: par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]: rank[x] += 1

for i in range(M):
    A, B = map(int,input().split())
    A -= 1
    B -= 1
    unite(A,B)
for i in range(N):find(i)    
print(Counter(par).most_common()[0][1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-08-29 21:38:12 +0900
# LastModified: 2020-08-29 21:54:27 +0900
#


import os
import sys
sys.setrecursionlimit(900000)
# import numpy as np
# import pandas as pd
from collections import Counter


def dfs(u, color, path, n, d):
    color[u] = d
    for v in path[u]:
        if color[v] == -1:
            dfs(v, color, path, n, d)



def main():
    n, m = map(int, input().split())
    path = [[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int, input().split())
        path[a].append(b)
        path[b].append(a)
    color = [-1]*(n+1)
    d = 0
    for i in range(1, n+1):
        if color[i] == -1:
            dfs(i, color, path, n, d)
            d += 1
    color = color[1:]
    color_cnt = Counter(color).values()
    print(max(color_cnt))



if __name__ == "__main__":
    main()

Submission status: Accepted

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

def dfs(G, v, p):
    seen[v] = True
    for nv in G[v]:
        if nv == p: continue
        if seen[nv]: continue
        dfs(G, nv, v)
    
    for c in G[v]:
        if c != p: continue
        sz[p] += (sz[v]+1)

n, m = map(int, input().split())
ab = []
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if a > b:
        a, b = b, a
    ab.append((a, b))
ab = set(ab)

G = [[] for _ in range(n)]
for a, b in ab:
    G[a].append(b)
    G[b].append(a)

seen = [False]*n
sz = [0]*n
for i in range(n):
    if not seen[i]:
        dfs(G, i, -1)

print(max(sz)+1)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l_c=[0 for i in range(N)]
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   l[b].append(a)
from collections import deque
def search(start):
   cnt=1
   que=deque([start])
   l_c[start]=1
   while que:
      A=que.popleft()
      for i in l[A]:
         if l_c[i]==0:
            cnt+=1
            l_c[i]=1
            que.append(i)
   return cnt
ans=0
for i in range(N):
   if l_c[i] ==0:
      ans=max(ans,search(i))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import collections

N, M = map(int, input().split())
edge = np.array([input().split() for _ in range(M)], dtype=np.int64).T

if M == 0:
    print(1)
else:
    tmp = np.ones(M, dtype=np.int64).T
    graph = csr_matrix((tmp, (edge[:] - 1)), (N, N))

    n, labels = connected_components(graph)

    c = collections.Counter(labels)

    print(max(c.values()))

Submission status: Accepted

Solution code:
from collections import Counter 

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

    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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

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

for _ in range(M):
    x, y = map(int, input().split())
    uf1.union(x-1,y-1)

for i in range(N):
    uf1.find(i) 
c = list(Counter(uf1.par).values())
print(max(c))

Submission status: Accepted

Solution code:
#Union Find

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

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

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

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

arr = []
for i in range(n):
    if par[i]<0:
        arr.append(-par[i])
        
arr=sorted(arr)
ans=0
div=0
k=len(arr)
for j in range(k):
    if j!=k-1:
        if arr[j]-div!=0:
            ans+=arr[j]-div
            div+=arr[j]-div
    elif j==k-1:
        if arr[j]-div!=0:
            ans+=arr[j]-div


print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

class Graph():
    def __init__(self):
        """ ノードのつながりを辞書型で表現する """
        self.adjacency_dict = {}

    def add_vertex(self, v):
        """ ノードを追加する """
        self.adjacency_dict[v] = []
    def add_edge(self, v1, v2):
        """ ノード同士をつなぐ。"""
        # 無向グラフの場合は双方向。もし有向グラフなら片側のみ。
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)
    def next_vertices(self, v):
        """ 隣接したノードを返す """
        return self.adjacency_dict[v]

def bfs(start):
    visited[start] = True
    q = deque()
    q.append(start)

    group_size = 1
    while q:
        v_now = q.popleft()
        for v_next in graph.next_vertices(v_now):
            if visited[v_next] == False:
                visited[v_next] = True
                q.append(v_next)
                group_size += 1

    return group_size
    

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

graph = Graph()
for i in range(1, N+1):
    graph.add_vertex(i)
for v1, v2 in AB:
    graph.add_edge(v1, v2)

visited = [False] * (N+1)

max_group_size = 1
for i in range(1, N+1):
    if visited[i] == False:
        group_size = bfs(i)
        max_group_size = max(max_group_size, group_size)
    
print(max_group_size)

Submission status: Accepted

Solution code:
import sys


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


input = sys.stdin.buffer.readline
N, M = map(int, input().split())

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

# print(uf)

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

Submission status: Accepted

Solution code:
from collections import Counter
N,M = (int(T) for T in input().split())
def FindParent(X):
    if Parent[X]==X:
        return X
    else:
        Parent[X] = FindParent(Parent[X])
        return Parent[X]

def IsSameParent(X,Y):
    return FindParent(X)==FindParent(Y)

def UniteParent(X,Y):
    X = FindParent(X)
    Y = FindParent(Y)
    if X==Y:
        return 0
    if Rank[X]<Rank[Y]:
        Parent[X] = Y
    else:
        Parent[Y] = X
        if Rank[X]==Rank[Y]:
            Rank[X] += 1
Parent = [I for I in range(N+1)]
Rank = [0]*(N+1)
for TM in range(0,M):
    A,B = (int(T) for T in input().split())
    UniteParent(A,B)
for TN in range(1,N+1):
    FindParent(TN)
print(Counter(Parent[1:]).most_common()[0][1])

Submission status: Accepted

Solution code:
#再帰の限度を拡張
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())

parent_dict = dict() #key:子 value:親

#接続追加
def add_connect(A,B):
    A_parent = get_parent(A)
    B_parent = get_parent(B)
    
    if A_parent != B_parent:
        parent_dict[B_parent] = A_parent

#接続有無判断
def judge_connection(A,B):
    A_parent = get_parent(A) #未更新状態でも、ここで更新される
    B_parent = get_parent(B)
    
    if A_parent != B_parent:
        return False
    else:
        return True

#親の取得
def get_parent(child):
    if child not in parent_dict: #初出なら自分自身を親として追加
        parent_dict[child] = child
    
    parent = parent_dict[child]
    
    if parent == child: 
        return parent
    else: #最上位の親なら上の等式が成り立つ。不成立ならさらに上位の親を辿る。
        parent_dict[child] = get_parent(parent) 
        return parent_dict[child]


##注意!!　全入力完了後にget_parentをしないと、正しい親が得られない
#ex 12 23 13 56 61 43→{1: 5, 2: 1, 3: 5, 5: 4, 6: 5, 4: 4}になる
for i in range(M):
    A,B = map(int, input().split())
    add_connect(A,B)

for i in range(1,N+1):
    get_parent(i)

#print(parent_dict)

#最も子が多い親を求めるために、親:子の辞書を作る
child_dict = dict() #key:親 value:子

for i in range(1,N+1):
    if parent_dict[i] not in child_dict:
        child_dict[parent_dict[i]] = set()
    child_dict[parent_dict[i]].add(i)


ans = 1
for parent in child_dict:
    if len(child_dict[parent]) > ans:
        ans = len(child_dict[parent])

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 solve():
    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)
    rt_l = UF.roots()
    ans = 0
    for _rt in rt_l:
        _len = UF.size(_rt)
        if ans < _len:
            ans = _len

    print(ans)


solve()

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(max([uf.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 _ in range(M):
    a,b=[int(e)-1 for e in input().split()]
    uf.union(a,b)
ans=max([uf.size(i) for i in range(N)])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.par = list(range(n))
        self.rank = [0] * n

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

    def unite(self, x: int, y: int) -> None:
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        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(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


def resolve(in_):
    N, M = map(int, next(in_).split())
    AB = tuple(tuple(map(int, line.split())) for line in in_)

    tree = UnionFindTree(N + 1)
    for a, b in AB:
        tree.unite(a, b)
    
    c = Counter(tree.find(i) for i in range(1, N + 1))
    return c.most_common(1)[0][1]
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gp(u,parent):
	if parent[u] != u: parent[u] = gp(parent[u], parent)
	return parent[u] 
n,m = map(int, raw_input().split())
parent = {i:i for i in range(1,n+1)}
size = {i:1 for i in range(1,n+1)}
for _ in range(m):
	u,v = map(int, raw_input().split())
	pu,pv = gp(u,parent), gp(v,parent)
	if pu != pv:
		parent[pv] = pu
		size[pu] += size[pv]
print max(size.values())

Submission status: Accepted

Solution code:
n, m = (int(x) for x in input().split())
par = [-1]*(n+1)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
def size(x):
    return -par[find(x)]
g = [[] for _ in range(n+1)]
for _ in range(m):
    s,t = map(int,input().split())
    unite(s,t)
    g[s].append(t)
    g[t].append(s)
ma = 0
for i in range(1,n+1):
    ans = size(i)
    if ma<ans:
        ma = ans
print(ma)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, 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
N,M = map(int,input().split())
uf = UnionFind(N)
for m in range(M):
    temp = [int(i)-1 for i in input().split()]
    uf.union(temp[0],temp[1])
print(-min(uf.parents))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
from collections import defaultdict, deque

# 標準入力を取得
N, M = list(map(int, input().split()))
G = defaultdict(set)
for m in range(M):
    A_i, B_i = list(map(int, input().split()))
    G[A_i - 1].add(B_i - 1)
    G[B_i - 1].add(A_i - 1)

# 求解処理
seen = [False for i in range(N)]

ans = 0
for i in range(N):
    if seen[i]:
        continue
    friends = 0
    que = deque()

    seen[i] = True
    que.append(i)
    friends += 1

    while len(que) > 0:
        v = que.popleft()
        for w in G[v]:
            if not seen[w]:
                seen[w] = True
                que.append(w)
                friends += 1

    ans = max(ans, friends)

# 結果出力
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M = LI()
    par = [i for i in range(N + 1)]
    par_size = [1 for _ 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):
        if same(x, y):
            return 0
        par_size[find(y)] += par_size[find(x)]
        par[find(x)] = find(y)
    for _ in range(M):
        A, B = LI()
        unite(A, B)
    ans = 0
    for p in par_size:
        ans = max(ans, p)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]

if m == 0:
    print(1)
    exit()
    
g = [[] for _ in range(n)]
visited = [-1] * n
for a, b in ab:
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)
# print(g)
def dfs(start):
    global visited
    if visited[start] != -1:
        return 1
    stack = []
    stack.append(start)
    visited[start] = start
    while stack:
        root = stack.pop()
        for j in g[root]:
            if visited[j] == -1:
                visited[j] = start
                stack.append(j)

for i in range(n):
    dfs(i)
# print(visited)
tmp = Counter(visited)
# print(tmp)
p = sorted([v for i, v in tmp.items() if v != 1])
island = len(p)
# print(island)
if island == 1:
    print(n)
else:
    print(p[-1])