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 deque

N , M = map(int, input().split())
friends = [list() for _ in range(N+1)]
for _ in range(M):
    h1, h2 = map(int, input().split())
    friends[h1].append(h2)
    friends[h2].append(h1)

f_group = [0]*(N+1)
q = deque()
cnt = 0
mem_num_max = 0
while cnt < N:
    for i in range(N):
        mem_num = 0
        if f_group[i] == 0:
            q.append(i)
            f_group[i] = i
            cnt += 1
            mem_num += 1

        while len(q):
            now = q.popleft()

            for h in friends[now]:
                if f_group[h] == 0:
                    f_group[h] = f_group[now]
                    q.append(h)
                    cnt += 1
                    mem_num += 1
        
        mem_num_max = max(mem_num_max, mem_num)

print(mem_num_max)

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n # ノード数
        self.parents = [-1]*n # 各ノードごとのparent

    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 _ in range(M):
    i, j = map(int, input().split())
    i-=1
    j-=1
    uf.union(i,j)

max_size = 0
for i in range(N):
    if uf.parents[i]<0:
        size = uf.size(i)
        if max_size<size:
            max_size = size
print(max_size)

Submission status: Accepted

Solution code:
class uft():
    def __init__(self,n):
        #pは代表元か-1
        self.p=[ -1 for i in range(n)]
        #ランク　木の深さ
        self.r=[ 1 for i in range(n)]
        #要素数
        self.e=[ 1 for i in range(n)]
        
    def find(self,x):
        if(self.p[x]==-1):
            return x
        else:
            self.p[x]=self.find(self.p[x])
            return self.find(self.p[x])
        
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):
            return
        
        if(self.r[x]>self.r[y]):
            tmp=x
            x=y
            y=tmp
        
        if(self.r[x]==self.r[y]):
            self.r[y]+=1
        
        self.e[y]+=self.e[x]
            
        if(x!=y):
            self.p[x]=y
        return
    
    def tsize(self,x):
        return self.e[self.find(x)]
n,m=map(int,input().split())

uf=uft(n)
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    uf.unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,uf.tsize(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
M=set(tuple(map(int,input().split())) for _ in range(m))
d={i:set() for i in range(1,n+1)}
for i,j in M:
    d[i].add(j)
    d[j].add(i)

vis=set()
res = 0
for i in range(1,n+1):
    if i not in vis:
        stack = [i]
        ans = 1
        vis.add(i)
        while stack:
            curr = stack.pop()
            for j in d[curr]:
                if j not in vis:
                    stack.append(j)
                    ans+=1
                    vis.add(j)
        res = max(ans,res)
print(res)

Submission status: Accepted

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

V = [set() for _ in range(n)] # 隣接リスト
for a, b in [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]:
    V[a].add(b)
    V[b].add(a)

from collections import deque
G = [-1] * n # グループ色分け
for s in range(n): # BFS
    dq = deque([s])
    while dq:
        p = dq.popleft()
        if G[p] >= 0: continue
        G[p] = s # 色付け
        for c in V[p]:
            dq.append(c)

C = dict() # グループメンバ数集計
for g in G:
    if not g in C: C[g] = 0
    C[g] += 1

print(max(C.values())) # 最大メンバ数

Submission status: Accepted

Solution code:
def bfs(fd, n):
    visited = set()
    ans = 1
    for i in range(1, n + 1):
        if i in visited: continue
        volume = 1
        queue = fd[i]
        visited.add(i)
        while queue:
            x = queue.pop()
            if x in visited: continue
            visited.add(x)
            volume += 1
            queue |= fd[x]
        ans = max(ans, volume)
    return ans

if __name__ == "__main__":
    n, m = map(int, input().split())
    fd = {i+1:set() for i in range(n)}
    for _ in range(m):
        a, b = map(int, input().split())
        fd[a].add(b)
        fd[b].add(a)
    print(bfs(fd, n))

Submission status: Accepted

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

V = [set() for _ in range(n)]
for a, b in [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]:
    V[a].add(b)
    V[b].add(a)
# print(V)

from collections import deque
G = [-1] * n
for s in range(n):
    dq = deque([s])
    while dq:
        p = dq.popleft()
        if G[p] >= 0: continue
        G[p] = s
        for c in V[p]:
            if G[c] >= 0: continue
            dq.append(c)
# print(G)

C = dict()
for g in G:
    if not g in C: C[g] = 0
    C[g] += 1
# print(C)

print(max(C.values()))

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1 for i in range(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, y = self.find(x), 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())
friend_lis = [list(map(int, input().split())) for i in range(M)]

lis = UnionFind(N)
for i,j in friend_lis:
  lis.union(i-1, j-1)
#print(lis.parents)

ans = -min(lis.parents)
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.sum = [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.sum[y] += self.sum[x]
        else:
            self.par[y] = x
            self.sum[x] += self.sum[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())
A = [0] * M
B = [0] * M

uni = UnionFind(N)

for i in range(M):
    A[i], B[i] = map(int,input().split())
    uni.union(A[i],B[i])


print(max(uni.sum))
















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

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


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


def unite(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return
    if rank[x] < rank[y]:
        x, y = y, x
    par[y] = x
    size[x] += size[y]
    if rank[x] == rank[y]:
        rank[x] += 1


for i in range(M):
    a, b = [int(i) - 1 for i in input().split()]
    unite(a, b)

print(max(size))"""

Submission status: Accepted

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

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

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(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 isConnect(self, x):
        return self.root(x) == self.root(y)

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

N, M = map(int, input().split())
uf = Unionfind(N)
for i in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf.connect(a, b)
ans = 0
for i in range(N):
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

V, E = map(int, input().split())

graph = defaultdict(dict)
for _ in range(E):
  a, b = map(int, input().split())
  graph[a][b] = True
  graph[b][a] = True

components = []				# list of components
visited = set()

for i in range(1, V+1):
  if i in visited:
    continue
  
  # do bfs starting from i
  current_component = set()
  queue = deque([i])
  visited.add(i)

  while queue:
    x = queue.popleft()
    
    current_component.add(x)
    
    for nbr in graph[x]:
      if nbr not in visited:
        queue.append(nbr)
        visited.add(nbr)
  
  components.append(current_component)

print(max(map(len, components)))

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())
    a -= 1
    b -= 1
    uf.union(a, b)
    
ans = [uf.size(i) for i in range(n)]
print(max(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [list(map(lambda x : int(x) - 1, input().split())) for _ in range(M)]

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

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

ans = min(uf.parents)
print(-ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n: int):
        """
        n: ノード数
        """
        self.n = n
        """
        d: UnionFind木のデータ構造
            各要素の根要素を格納するリスト
            根要素の場合は, グループの要素数*-1を格納する
        """
        self.d = [-1] * n

    def find(self, x: int) -> int:
        """
        要素xが属するグループの根を返す
        """
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]

    def unite(self, x: int, y: int) -> bool:
        """
        要素xが属するグループと, 要素yが属するグループを併合する
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False

        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

    def size(self, x: int) -> int:
        """
        要素xが属するグループのサイズ(要素数)を返す
        """
        return -self.d[self.find(x)]

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

    def groups(self) -> list:
        """
        すべての根の要素をリストで返す
        """
        return [i for i, x in enumerate(self.d) if x < 0]

    def group_count(self) -> int:
        """
        グループの数を返す
        """
        return len(self.groups())


def resolve():
    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 uf.groups():
        ans = max(ans, uf.size(i))
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    friends[a].append(b)
    friends[b].append(a)

checked = [False] * N
ans = 0

for i in range(N):
    if checked[i] == False:
        checked[i] = True
        DQ = deque(friends[i])
        tmp = 1
        while DQ:
            f = DQ.popleft()
            if checked[f] == False:
               checked[f] = True
               tmp += 1
               for j in friends[f]:
                   DQ.append(j)
        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
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)]
    

f=lambda:map(int,input().split())
N,M=f()
uf=UnionFind(N+1)
for _ in range(M):
    a,b=f()
    uf.Unite(a,b)
    
print(max([uf.Count(i+1) for i in range(N)]))

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
t = dict()
for i in range(1, n+1):
    t[i] = set()
for a, b in ab:
    t[a].add(b)
    t[b].add(a)

q = deque()
s = set()
ans = 0
for i in range(1, n+1):
    if i not in s:
        q.append(i)
        s.add(i)
        tmp = [i]
        while q:
            v = q.popleft()
            for ti in t[v]:
                if ti not in s:
                    tmp.append(ti)
                    q.append(ti)
                    s.add(ti)
    ans = max(ans, len(tmp))
print(ans)

Submission status: Accepted

Solution code:
# データ構造: Union Find (素集合データ構造)
#  前提
#    グラフ（頂点と辺からなる集合）上の各頂点が、どの連結成分に属しているかを管理するときに使う
#    具体的には、各連結成分ごとに適当な1点を親として、同じ連結成分に属する他の点が子になるように配置する
#  できること
#    1, ある頂点の親を返す (つまり、どの連結成分に属するかがわかる)
#    2, 新たな辺が与えられた時、必要なら連結成分の統合を行う

# 以下、事前準備。(本処理は42行目から)
# 上記1,2を実現する関数を作成する。

# 0, 前提
# par = [-1 for _ in range(n)]
#  配列parの要素par[i]には、
#    頂点iが子の場合に 親頂点の番号
#    頂点iが親の場合に 属する連結成分の頂点数を格納する。(区別のため負数として表記)
#  例: par = [2, 2, -3, -1, 5, -1]
#    点0,1,2からなる連結成分、点3からなる連結成分、点4,5からなる連結成分がある場合。

# 1, 頂点xの親を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
      
# 2, 頂点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

# 以下、本処理
# 求めるもの：各連結成分の頂点数のうち、最大のもの
n, m = map(int,input().split())
par = [-1 for _ in range(n)]
 
for _ in range(m): #各辺について
  a, b = map(int,input().split())
  a -= 1
  b -= 1
  unite(a,b) #辺の両端(頂点aとb)が統合される
  
print(-min(par))
# 各連結成分の頂点数は、配列parの中に負数として記録されている。
# 連結成分の最大の頂点数を求めたければ、そのminをとって-1倍すればよい。

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter


def main():
    N,M = list(map(int, sys.stdin.readline().split()))
    AB_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(M) ]


    ##############################
    # Union Find
    parents = [-1] * (N + 1)

    def find(x :int) -> int:
        if parents[x] < 0:
            return x
        
        parents[x] = find( parents[x] )
        return parents[x]

    def union(x,y):
        root_x = find(x)
        root_y = find(y)

        if root_x == root_y:
            return
        
        depth_x = parents[root_x]
        depth_y = parents[root_y]

        if depth_x <= depth_y:
            parents[root_y] = root_x

            if depth_x == depth_y:
                parents[root_x] -= 1

        else:
            parents[root_x] = root_y
    ##############################


    for a,b in AB_list:
        union(a,b)
    
    group = [ find(num) for num in range(1,N+1) ]
    cnt = Counter(group)
    
    print(cnt.most_common(1)[0][1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


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 solve():
    N, M = Scanner.map_int()
    uni = UnionFind(N)
    for _ in range(M):
        a, b = Scanner.map_int()
        a -= 1
        b -= 1
        uni.union(a, b)
    ls = [0 for _ in range(N)]
    for i in range(N):
        ls[uni.find(i)] += 1
    print(max(ls))


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.d = [-1] * n
    
    def find(self,x):
        if self.d[x] < 0:
            return x
        else:
            return self.find(self.d[x])
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if(-self.d[x] < -self.d[y]):
            x,y = y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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)

print(-min(uf.d))

Submission status: Accepted

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

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

root = [-1] * n

# 親を返す
def r(x):
    if root[x] < 0:
        return x
    else:
        root[x] = r(root[x])
        return root[x]


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


def size(x):
    x = r(x)
    return -root[x]

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

max_size = 0
for i in range(n):
    max_size = max(max_size, size(i))

print(max_size)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def unite(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 find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def size(self, x):
        return -self.parents[self.find(x)]

n, m = map(int,input().split())
uf = UnionFind(n)
for i 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:
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())
  uf.union(a-1,b-1)
root = [0]*n
for i in range(n):
  root[uf.find(i)] += 1
print(max(root))

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)
# AB= [map(int, input().split()) for _ in range(M)]
# A, B = [list(i) for i in zip(*AB)]
def find(x,parent):
    if parent[x]==x:
        return x
    else:
        parent[x]=find(parent[x],parent)
        return(parent[x])
        
def union(x,y,parent,rank):
    xroot=find(x,parent)
    yroot=find(y,parent)
    if rank[xroot]>rank[yroot]:
        parent[yroot]=xroot
    elif rank[yroot]>rank[xroot]:
        parent[xroot]=yroot
    elif rank[yroot]==rank[xroot]:
        parent[yroot]=xroot
        rank[xroot]+=1
    return(parent,rank)

    
parent=[i for i in range(N+1)]
rank=[0]*(N+1)
for i in range(M):
    parent,rank=union(A[i],B[i],parent,rank)
for i in range(N+1):
    find(i,parent)
G=parent[1:]
import collections
c=collections.Counter(G)
print(int(c.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())

n,m = map(int,input().split())
uf = UnionFind(n)
friend = [0]*n
for i in range(m):
    a,b = map(int,input().split())
    a -=1
    b -=1
    uf.union(a,b)
maxfriend = -1
for i in range(n):
    maxfriend = max(maxfriend,uf.size(i))
print(maxfriend)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

print(ans)

Submission status: Accepted

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

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.findRoot(x)
        y = self.findRoot(y)
        # すでに同じ木に属していた場合
        if x == y:
            return 
        # 違う木に属していた場合rankを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

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

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

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

ans = 0

for i in range(n):
    ans = max(union.count(i), ans)

print(ans)