Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
N,M = map(int,input().split())    
uf = UnionFind(N)
for i in range(M):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
    
root = uf.roots()
print( max(uf.size(r) for r in root) )

Submission status: Accepted

Solution code:
#unionfind木_集合の管理_同じ集合の数を数える場合：
#parには集合の数と親の名前を同時にメモ化する（根なら-size, 子なら親）
def find(k):#要素k
    if par[k] < 0:#初期はparがすべて負の値
        return k
    else:
        par[k] = find(par[k])
        return par[k]

def unite(i, j):
    i = find(i)
    j = find(j)
    if i==j:#すでに同じ集合
        return False
    else:
        #sizeが大きい方がi
        if i > j:#sizeはマイナス管理なので、i>jの時jの方がサイズが大きい
            i, j = j, i
        par[i] += par[j] #親は負の値で大きくなる
        par[j] = i
        return True

def size(x):
    return -par[find(x)]

n, m= map(int, input().split())
par = [-1]*n#初めは自分自身が親

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

ans = 0
for i in range(n):
    ans = max(ans, -par[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()) for r in self.roots())


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

uf = UnionFind(n)

for f in F:
    uf.union(f[0] - 1, f[1] - 1)

out = 0

for r in uf.roots():
    out = max(out, uf.size(r))

print(out)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit

def find(par,i):
    if par[i]<0:
        return i
    par[i] = find(par,par[i])
    return par[i]

def unite(par,i,j):
    ri = find(par,i)
    rj = find(par, j)
    if ri==rj:
        return
    par[rj] += par[ri]
    par[ri] = rj
    
setrecursionlimit(10**6)
n,m = map(int,input().split())

parent = [-1]*n
for _ in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    unite(parent,a,b)
    
print(-min(parent))

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])



#UnionFind
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 = inpm()
AB = inplt(m)

uf = UnionFind(n)
for a,b in AB:
    uf.union(a-1,b-1)

print(-min(uf.parents))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        xの属する木の根を返す
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        x, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():
    N, M = map(int, input().split())
    tree = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        tree.union(a - 1, b - 1)
    ans = 0
    for root in tree.roots():
        ans = max(ans, tree.size(root))
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    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)

print(-min(uf.parents))

Submission status: Accepted

Solution code:
from collections import Counter
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())
par = [-1]*n
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
ans = 0
for i in range(n):
    ans = max(size(i),ans)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
a=UnionFind(n)
for i in range(m):
    x,y=map(int,input().split())
    a.union(x-1,y-1)
print(-min(a.parents))

Submission status: Accepted

Solution code:
from collections import deque
n , m = map(int,input().split())
route = [[] for i in range(n)]

for _ in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    route[a].append(b)
    route[b].append(a)
    
visit = [False for i in range(n)]
ans = 0
for i in range(n):
    if visit[i]:
        continue
    cou = 1
    visit[i] = True
    d = deque()
    d.append(i)
    while d:
        now = d.popleft()
        for j in route[now]:
            if not visit[j]:
                visit[j] = True
                cou += 1
                d.append(j)
    ans = max(cou,ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N,M=list(map(int,input().split()))
G = [[] for i in range(N)]
for i in range(M):
    A,B=list(map(int,input().split()))
    G[A-1].append(B-1)
    G[B-1].append(A-1)

done = [0]*N #その人を見たかどうか(通過したかどうか)
out = 0 #最大値を更新していく
for i in range(0,N): #スタート地点の候補
    if done[i]==1:
        continue
    s = i
    dist = 0
    que = deque([s])
    dist += 1
    done[s] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            if done[w]==1:
                continue
            dist += 1
            done[w] = 1
            que.append(w)
    out = max(dist,out)
print(out)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class unionfind:
    """Union-Find"""
    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node
        
        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int):
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
    
    def unite(self, x: int, y: int):
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

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

    def same(self, x: int, y: int):
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)
    
    def size(self, x: int) -> bool:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent):
    global cnt
    children = fr[cur]
    for chi in children:
        if used[chi] != -1:
            continue
        if chi == parent:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur)
    return

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1)
    MAX = max(MAX, cnt)
print(MAX)

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

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

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

ans=0

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

print(ans)

Submission status: Accepted

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

    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
        elif self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

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

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

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

uf = UnionFind(N)
ans = 0

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.num = [1 for i in range(n)]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.parent[x] = y
            self.num[y] += self.num[x]

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

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

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

Submission status: Accepted

Solution code:
from math import gcd, sqrt, cos, radians, pi, floor, ceil
from collections import defaultdict as d
from itertools import combinations as c
from string import ascii_lowercase as a

def bfs(s):
	global dico, visited
	queue = []
	queue.append(s)
	visited[s] = 1
	count = 1
	while queue:
		s = queue.pop(0)
		for i in dico[s]:
			if not visited[i]: 
				queue.append(i) 
				visited[i] = 1
				count += 1
	return count
	

n, m = map(int, input().split())
dico = d(set)
visited = [0] * (n + 1)
for i in range(m):
	a, b = map(int, input().split())
	dico[a].add(b)
	dico[b].add(a)

maxi = 0

for i in range(1, n + 1):
	if not visited[i]:
		maxi = max(maxi, bfs(i))

print(maxi)

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([-i for i in UF.parents]))

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([-i for i in UF.parents]))

Submission status: Accepted

Solution code:
# union-find

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

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

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

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

for i in list:
  unite(i[0]-1, i[1]-1)

max = 0

for i in range(len(par)):
    if max<size(i):
        max = size(i)
print(max)

Submission status: Accepted

Solution code:
def d_friends():
    class UnionFind(object):
        def __init__(self, n):
            """要素番号は 0 スタートを前提とする"""
            self.num_element = n
            self.parents = [-1] * n  # 要素が根の場合は、-(グループの要素数) を格納

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

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

            if u == v:
                return

            # u のグループの方が要素数が少なかった (parents の 定義より)
            if self.parents[u] > self.parents[v]:
                u, v = v, u

            self.parents[u] += self.parents[v]  # u と同グループの要素数を増やす
            self.parents[v] = u  # v は u に繋げる

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

    N, M = [int(i) for i in input().split()]
    uf = UnionFind(N)
    for _ in range(M):
        a, b = [int(i) - 1 for i in input().split()]
        uf.union(a, b)
    return max([uf.get_size(r) for r in range(N)])

print(d_friends())

Submission status: Accepted

Solution code:
# cf. 16315733
N, M = list(map(int, input().split()))
# upperは、根なら-その木の長さを、枝ならその木の根の要素のインデックスを指す。
upper = [-1] * N
# xの根を返す
def root(x):
  # xが根なら
  if upper[x] < 0:
    return x
  # xが枝なら
  else:
    # 根のインデックスをさかのぼる
    upper[x] = root(upper[x])
    # 根のインデックスを返す
    return upper[x]

# x,yが同じグループにあるかどうか判定する
def equiv(x, y):
  return root(x) == root(y)

def unite(x, y):
  x, y = root(x), root(y)
  if x != y:
    if upper[y] < upper[x]:
      #xとyの値をスワップ、必ずupper[y] >= upper[x]とするつまりxのほうが高い
      x,y = y,x
    # 要素の数を足す：結合後の要素の数を求める
    upper[x] += upper[y]
    # yの根をxにする（木が高い方を根にする）
    upper[y] = x
  return x == y

for i in range(M):
  a, b = list(map(int, input().split()))
  unite(a-1, b-1)
print(-min(upper))

Submission status: Accepted

Solution code:
# Python template 
from collections import defaultdict 
import sys
import math 

def get_array(): return list(map(int , sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

sys.setrecursionlimit(10**6) 
g = defaultdict(set)
(n,m) = get_ints()
visited = [0]*n 


def dfs(i,l,par):
    global visited
    visited[i] = True
    l.append(i)
    for j in g[i]:
        if j!=par and not visited[j]:
            dfs(j,l,i)

for i in range(m):
    (u,v) = get_ints()
    g[u-1].add(v-1)
    g[v-1].add(u-1)

ans = 0
for i in range(n):
    if not visited[i]:
        l = []
        dfs(i,l,-1)
        ans = max(ans,len(l))
        
print(ans)

Submission status: Accepted

Solution code:
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+1)
for _ in range(M):
    a,b=map(int,input().split())
    uf.union(a,b)
    
print(abs(min(uf.parents)))

Submission status: Accepted

Solution code:
from collections import deque
 
N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]

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 -= 1
        y -= 1
        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 i in range(len(hint_list)):
    uf.union(hint_list[i][0],hint_list[i][1])
    
print(-min(uf.parents))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
root=[-1]*n
def r(x): #-1の項が何番目かを特定
  if root[x]<0: #x番目が-1ならx(>=0)を返す
    return x 
  else: #x番目が0以上なら-1の項に到達するまで回す
    root[x]=r(root[x]) 
    return root[x] #-1の項に到達したらその項が何番目かを返す
def unite(x,y):
  x=r(x)
  y=r(y)
  if x==y: #同じ項に到達した場合は処理の必要なし
    return
  root[x]+=root[y] #-1ずつ加算していく
  root[y]=x #-1を足した後は適当な数に変える(重複回避)
for i in range(m):
  a,b=map(int,input().split())
  a-=1 #リストの序数に合わせる
  b-=1
  unite(a,b) #各人間がどのくらい友達がいるか
ans=0
for i in range(n):
  ans=max(ans,-root[i]) #最多保有友人数が何人か
print(ans)

Submission status: Accepted

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

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)

        if rx == ry:
            return

        if self.parent[rx] > self.parent[ry]:
            rx, ry = ry, rx
        self.parent[rx] += self.parent[ry]
        self.parent[ry] = rx
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def size(self, x):
        return -self.parent[self.root(x)]

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)

ans = -1
for i in range(n):
    ans = max(ans, uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
f=lambda x:int(x)-1
l=[[] for _ in range(n)]
for i in range(m):
  a,b=map(f,input().split())
  l[a].append(b)
  l[b].append(a)
m=0  
visit=set()
for i in range(n):
  if i in visit:
    continue
  queue=[i]
  visit.add(i)
  cnt=1
  while len(queue)>0:
    now=queue.pop(0)
    for j in l[now]:
      if j not in visit:
        visit.add(j)
        queue.append(j)
        cnt+=1
  m=max(m,cnt)
print(m)