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

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


uf = UnionFind(n)
ans = 0

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

for i in uf.all_group_members():
    ans = max(ans, len(i))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        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 と 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
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]



N,M = map(int,input().split())
A = []; B = []
for i in range(M):
  a,b = map(int,input().split())
  a-=1;b-=1 #0index
  A.append(a);B.append(b)

uf = UnionFind(N)
for i in range(M):
  uf.union(A[i],B[i])

ans = 0
for x in range(N):
  temp = uf.get_size(x)
  ans = max(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))


n,m = input_multiple_number()

#UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        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 getGroupSize(self, x):
        return -self.parents[self.find(x)]

    #要素x, yが同じグループに属するかどうかを返す
    def isSame(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 getNumGroup(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())

re = UnionFind(n)

for _ in range(m):
	a,b = input_multiple_number()
	re.union(a-1,b-1)

mmax = 0
for nood in re.roots():
	g = re.getGroupSize(nood)
	if mmax < g:
		mmax = g
print(mmax)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par = [-1] * n     # 負数は友達の数（自分を含む）初期値は自分-1、0と正数は根を示す

    def root(self,x):   # xの根を返す
        if self.par[x] < 0:    # xが根の時は、xを返す
            return x
        self.par[x] = self.root(self.par[x])    # 根でないときは、par[x]に根の根を代入
        return self.par[x]                      # 根の根を返す

    def union(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:     # par[x]が小さく(友達が多く)なるように交換
            x, y = y, x
        self.par[x] += self.par[y]  # 友達が多い方に少ない方を加える
        self.par[y] = x             # yの根をxにする

    def size(self):
        return -1 * min(self.par)


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)               # 1が0番目、２が1番目・・・

print(uf.size())

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()]
A = list(range(N+1))
for _ in range(M):
  a,b = [int(i) for i in input().split()]
  while A[a] != a:
    a = A[a]
  while A[b] != b:
    b = A[b]
  a,b = [max(a,b),min(a,b)]
  A[a] = b
for i in range(N+1):
  n = A[i]
  while n != A[n]:
    n = A[n]
  A[i] = n
L = [0]*(N+1)
for a in A:
  L[a] += 1
print(max(L))

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

Submission status: Accepted

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

if M == 0:
    print(1)
    exit()

group_list = []
group_index = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    if group_index[a-1] == 0 and group_index[b-1] == 0:
        group_index[a-1] = len(group_list) + 1
        group_index[b-1] = len(group_list) + 1
        group_list.append(set([a, b]))

    elif group_index[a-1] == 0:
        group_index[a-1] = group_index[b-1]
        group_list[group_index[b-1] - 1].add(a)

    elif group_index[b-1] == 0:
        group_index[b-1] = group_index[a-1]
        group_list[group_index[a-1] - 1].add(b)

    elif group_index[a-1] != group_index[b-1]:
        if len(group_list[group_index[a-1] - 1]) > len(group_list[group_index[b-1] - 1]):
            group_id_b = group_index[b-1] - 1
            for p in group_list[group_id_b]:
                group_index[p-1] = group_index[a-1]
                group_list[group_index[a-1] - 1].add(p)
            group_list[group_id_b] = set()
        else:
            group_id_a = group_index[a-1] - 1
            for p in group_list[group_id_a]:
                group_index[p-1] = group_index[b-1]
                group_list[group_index[b-1] - 1].add(p)
            group_list[group_id_a] = set()

print(max([len(g) for g in group_list]))

Submission status: Accepted

Solution code:
import sys
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())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]
#print(info)

uf = UnionFind(N)

for a, b in info:
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
def main():
    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)
    uf_lis = uf.parents
    ans = 0
    for p in uf_lis:
        if p < 0:
            ans = max(ans, -p)
    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            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 all_group_members(self):
        #各ルート要素のグループに含まれる要素のリストの辞書
        return {r: self.members(r) for r in self.roots()}
    def all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
def main():
    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)
    uf_lis = uf.parents
    ans = 0
    for p in uf_lis:
        if p < 0:
            ans = max(ans, -p)
    print(ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
'''
	We can show that if u and v belong to the same connected component, then they are friends w/ each other
	So everyone in a given connected component is friends with one another
	So everyone in a given connected component must be separated into different groups

	If we have a CC of with sz nodes in it, then we need at least sz different groups

	So, the minimum number of groups needed is max sz(CC)
'''
n, m = map(int,input().split())
adj = [[] for u in range(n+1)]
for i in range(m):
	u, v = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for u in range(n+1)]
def bfs(s):
	sz = 0
	queue = [s]
	ptr = 0
	
	while ptr < len(queue):
		u = queue[ptr]
		if not vis[u]:
			vis[u] = True
			sz += 1
			for v in adj[u]:
				queue.append(v) 
		ptr += 1

	return sz

CCs = []
for u in range(1,n+1):
	if not vis[u]:
		CCs.append(bfs(u))

print(max(CCs))

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
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 make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

_INPUT = """\
5 3
1 2
3 4
5 1
"""

def main(*, input=input):
    sr = lambda: input()
    ir = lambda: int(sr())
    lr = lambda: list(map(int, sr().split()))

    n,m = lr()
    uf = UnionFind(n)
    for i in range(m):
        a,b = lr()
        a-=1
        b-=1
        uf.union(a,b)
    ans = min(uf.parents)
    print(-ans)

if __name__ == "__main__":
    import io, sys

    # sys.stdin = io.StringIO(_INPUT)

    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
from heapq import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0] * n
        self.size = [1] * n

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

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N, M = map(int, input().split())
uf = UnionFind(N+1)
for i in range(M):
    a, b = map(int, input().split())
    uf.unite(a, b)
ans = 0
for i in range(N):
    ans = max(ans, uf.getsize(i+1))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):       #(要素数)の分だけリストを作る
        self.n = n               #負の数なら親、正の数なら親のノード番号を入力
        self.parents = [-1]*n    #負の数の絶対値はそのグループに属する要素数を意味する
   
    #xが属する親番号を返す
    def find(self, x):
        if self.parents[x-1] < 0:
            return x
        else:
            self.parents[x-1] = self.find(self.parents[x-1])
            return self.parents[x-1]
    
    #xとyに関係があるとき、xの属するグループとyの属するグループ統合する
    def union(self, x, y):
        x = self.find(x) #xの親番号を返す
        y = self.find(y) #yの親番号を返す

        if x == y: return
        else:
            #xに属するグループ数の方が大きいようにする
            if self.parents[x-1] > self.parents[y-1]:
                x, y = y, x
            self.parents[x-1] += self.parents[y-1]
            self.parents[y-1] = x 

    #xの属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)-1]
    
    #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())

N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    A,B = map(int, input().split())
    uf.union(A,B)
parents = uf.roots()
ans = 0
for p in parents:
    ans = max(ans, uf.size(p))
print(ans)

Submission status: Accepted

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

# 行先記憶用
rooting = [[] for _ in range(N+1)]

for _ in range(M):
    A, B = map(int, input().split())
    rooting[A].append(B)
    rooting[B].append(A)

# グループの最大人数
max_group_num = 1

# 到達判定フラグ（到達していれば1）
visited = [0 for _ in range(N+1)]

# 幅優先探索
for i in range(1, N+1):
    if  visited[i] == 1:
        continue
    visited[i] = 1
    queue = [i]
    group_num = 1

    while not queue == []:
        h = queue.pop(0)
        for n in rooting[h]:
            if visited[n] != 1:
                queue.append(n)
                group_num += 1
                visited[n] = 1

    max_group_num = max(max_group_num, group_num)

print(max_group_num)

Submission status: Accepted

Solution code:
import numpy as np

class UnionFind:
    def __init__(self, sz: int):
        self._par: np.array = np.full(sz + 1, -1)

    def root(self, a: int):
        if self._par[a] < 0:
            return a
        self._par[a] = self.root(self._par[a])
        return self._par[a]
    
    def size(self, a: int):
        return -self._par[self.root(a)]
    
    def unite(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a != b:
            if self.size(a) < self.size(b):
                a, b = b, a
            self._par[a] += self._par[b]
            self._par[b] = a
    
if __name__ == '__main__':
    N, M = map(int, input().split())
    uf = UnionFind(N + 1)
    for i in range(M):
        a, b = map(int, input().split())
        uf.unite(a, b)
    ans = 1
    for i in range(1, N + 1):
        ans = max(ans, uf.size(i))
    print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, sz: int):
        self._par: list[int] = [-1] * sz

    def root(self, a: int):
        if self._par[a] < 0:
            return a
        self._par[a] = self.root(self._par[a])
        return self._par[a]
    
    def size(self, a: int):
        return -self._par[self.root(a)]
    
    def unite(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a != b:
            if self.size(a) < self.size(b):
                a, b = b, a
            self._par[a] += self._par[b]
            self._par[b] = a
    
if __name__ == '__main__':
    N, M = map(int, input().split())
    uf = UnionFind(N + 1)
    for i in range(M):
        a, b = map(int, input().split())
        uf.unite(a, b)
    ans = 1
    for i in range(1, N + 1):
        ans = max(ans, uf.size(i))
    print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    #par[x]でxの親のID，xが根ならその木のサイズに―をつけたもの
    def __init__(self, n):
        #全て根として初期化
        self.par = [-1] * n
    
    #xの根を返す
    def root(self, x):
        #xが根なら終了
        if self.par[x] < 0:
            return x
        #そうでないならxの親について調べる
        self.par[x] = self.root(self.par[x])    #xの根が親になるように更新
        return self.par[x]

    #xとyを結合
    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        #xとyが同じ根を持つ(＝同じ木に属する)なら終了
        if x == y:
            return
        #サイズの大きい木に小さい木を結合
        if self.par[x] > self.par[y]:   #xが大きくなるよう交換
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
    
    #xのサイズを返す
    def size(self, x):
        return -1 * self.par[self.root(x)]


#main
n, m = map(int, input().split())
uf = UnionFind(n)
#Union-FInd木を作る
for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)      #1からではなく0からに
#サイズが最大のものを探す
ans = 0
for i in range(n):
    ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
N,M = tuple(map(int,input().split()))
# matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = list(range(N))
# [所属先,[所属メンバー]]
gplist = [[i] for i in range(N)]

def getgroup(a):
    A = friendlist[a]
    if A == a:
        return a
    else:
        return getgroup(A)

def match(ab):
    A = getgroup(ab[0])
    B = getgroup(ab[1])
    if A==B:
        return
    elif len(gplist[A])<len(gplist[B]):
        gplist[B].extend(gplist[A])
        friendlist[A] = B
    else:
        gplist[A].extend(gplist[B])
        friendlist[B] = A

for i in range(M):
    # print(friendlist)
    # print(gplist)
    match(tuple(map(lambda x:int(x)-1,input().split())))

# print(friendlist)
# print(gplist)

print(max([len(item) for item in gplist]))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
friends = [[] for _ in range(N+1)]
for __ in range(M):
  a, b = map(int, input().split())
  friends[a].append(b)
  friends[b].append(a)
checked = [0 for ___ in range(N+1)]
answer = 1
for i in range(1, N+1):
  friend = deque(friends[i])
  cnt = 0
  while(len(friend) > 0):
    f = friend.popleft()
    if checked[f] != 0:
      continue
    else:
      checked[f] = 1
      cnt += 1
      for ff in friends[f]:
        friend.append(ff)
  answer = max(answer, cnt)
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush
import collections


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

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

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

    count = [0]*n
    for p in par:
        count[find(p)] += 1
    print(max(count))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return 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)]

import sys
input = sys.stdin.buffer.readline
 
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)
 
res = 0
for e in par:
    if e < 0:
        res = max(res,-e)
print(res)

Submission status: Accepted

Solution code:
def main():
    class unionfind():
        # size:要素数,tree：unionfind木
        def __init__(self, size):  # self,要素数
            self.size = size
            self.tree_root = list(range(self.size))
            self.tree_depth = [1]*self.size

        # rootを探す
        def root(self, index):
            temp_list = []
            temp = self.tree_root[index]
            while index != temp:
                temp_list.append(index)
                index = temp
                temp = self.tree_root[index]
            for i in temp_list:
                self.tree_root[i] = index
            return index

        # 結合
        def unite(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            if r1 != r2:
                d1, d2 = self.tree_depth[r1], self.tree_depth[r2]
                if d1 <= d2:
                    self.tree_root[r1] = r2
                    self.tree_depth[r2] = max(d1+1, d2)
                else:
                    self.tree_root[r2] = r1
                    self.tree_depth[r1] = max(d2+1, d1)

        # 同じか判定
        def same(self, index1, index2):
            r1 = self.root(index1)
            r2 = self.root(index2)
            return r1 == r2

        # 連結成分の個数
        def component(self):
            return len({self.root(i) for i in range(self.size)})

    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*m]
    s = [0]*n
    uf = unionfind(n)

    for a, b in ab:
        uf.unite(a-1, b-1)

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


main()

Submission status: Accepted

Solution code:
from collections import Counter

# 再帰回数のエラー？と思われるので再帰上限を変更 10**3 → 10**9
# 変更したら RE がなくなったのでおそらくこれのせいで通らなかった
import sys
sys.setrecursionlimit(10 ** 9)

def main(N, M, C):
    lst = [n for n in range(N)] # 初期値はすべてがそれぞれ根である状態

    def get_root(x):    # 根を得る関数
        if lst[x] == x: # それ自身が根である場合
            return x
        else:   # 根が別のものである場合
            lst[x] = get_root(lst[x])   # 経路圧縮あり (ある種「メモ再帰化」)
            return lst[x]
            # return get_root(lst[x]) # 経路圧縮なし (わかりやすい，ただの再帰関数) → ちなみにこれだとTLEになってしまった．

    def unite(x, y):    # 集合の連結を行う関数
        root_x = get_root(x)
        root_y = get_root(y)
        if root_x != root_y:    # 根が違う (=異なる集合) ならば
            lst[root_x] = root_y
            
    {unite(*c) for c in C}  # 集合の連結を行う．
    print(max(Counter(map(get_root, lst)).values()))    # 一番大きい集合の大きさを得る．


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(lambda x:int(x)-1, input().split())))   # pythonのindexに合わせるために "-1"
    main(N, M, C)

Submission status: Accepted

Solution code:
from collections import Counter

# 再帰回数のエラー？と思われるので再帰上限を変更 10**3→10**9
import sys
sys.setrecursionlimit(10 ** 9)

def main(N, M, C):
    lst = [n for n in range(N)] # 初期値はすべてがそれぞれ根である状態

    def get_root(x):    # 根を得る関数
        if lst[x] == x: # それ自身が根である場合
            return x
        else:   # 根が別のものである場合
            lst[x] = get_root(lst[x])   # 経路圧縮あり (ある種「メモ再帰化」)
            return lst[x]
            # return get_root(lst[x]) # 経路圧縮なし (わかりやすい，ただの再帰関数)

    def unite(x, y):    # 集合の連結を行う関数
        root_x = get_root(x)
        root_y = get_root(y)
        if root_x != root_y:    # 根が違う (=異なる集合) ならば
            lst[root_x] = root_y

    {unite(*c) for c in C}  # 集合の連結を行う．

    print(max(Counter(map(get_root, lst)).values()))


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(lambda x:int(x)-1, input().split())))   # pythonのindexに合わせるために "-1"
    main(N, M, C)

Submission status: Accepted

Solution code:
import sys
from collections import deque
mapin = lambda: map(int, sys.stdin.readline().split())
listin = lambda: list(map(int, sys.stdin.readline().split()))
inp = lambda: sys.stdin.readline()

class UnionFind():
    def __init__(self,n):
        self.N = n
        self.par = [-1] * n
    
    def find(self,n):
        if self.par[n] < 0:
            return n
        else:
            self.par[n] = self.find(self.par[n])
            return self.par[n]
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        else:
            if -self.par[x] < -self.par[y]:
                x,y = y,x
            self.par[x] += self.par[y]
            self.par[y] = x
    
    def size(self,x):
        return -self.par[self.find(x)]
    
    def tree_num(self):
        res = 0
        for i in self.par:
            res += i < 0
        return res
    
    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M = mapin()
UF = UnionFind(N)
for i in range(M):
    a,b = mapin()
    a,b = a - 1,b - 1
    UF.unite(a,b)
ans = 0
for i in UF.par:
    if i < 0:
        if ans < -i:
            ans = -i
print(ans)