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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

uf = UnionFind(n)

for i in range(m):
    a,b = map(int, input().split())
    a -=1
    b -=1
    uf.union(a,b)
    
res = [0]
for j in  uf.roots():
    res.append(uf.size(j))
print(max(res))

Submission status: Accepted

Solution code:
class UnionFind():
    '''
    グループ分けを木構造で管理するデータ構造
    以下の二点を高速で行うことができるのがメリット．
    ・要素xと要素yが同じグループに属するかどうかを判定したい
        → 要素xの根と要素yの根が同じならば同じグループ，
          要素xの根と要素yの根が同じでないならば異なるグループ
          にあることが分かる．
    ・要素xと要素yが別のグループに属する場合，
        要素xの属するグループと要素yの属するグループを併合する．
    '''

    def __init__(self, n):
        self.n = n
        # parents[x] = y: xの親がy
        # aが親なら -size(初期値-1)
        self.parents = [-1] * n

    # グループの根を探索
    def find(self, x):
        if self.parents[x] < 0:  # xが木の根の場合
            return x
        # 親へ再帰
        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    # グループの併合
    def unite(self, x, y):
        # x, yの根を探索
        x = self.find(x)
        y = self.find(y)
        if x == y:  # 同じ木に属する場合
            return
        # 計算速度のため、小さい方の根を大きい方の根につける
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]  # サイズを加算
        self.parents[y] = x  # 親の張り替え

    # 同じグループに属するか判定
    def same(self, x, y):
        # 根を比較し同じならtrue
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]  # 負で保存してあるため

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



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 range(n):
        s = uf.size(i)
        if ans < s:
            ans = s

    print(ans)

resolve()

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
#隣接リスト
ad = {}
for n in range(N):
    ad[n+1]=[]

for m in range(M):
    a,b = list(map(int,input().split()))
    ad[a].append(b)
    ad[b].append(a)
    
from collections import deque
    
color = {}
for n in range(N):
    color[n+1] = -1

depth = {}
for n in range(N):
    depth[n+1] = -1
    
group = {}
# for n in range(N):
#     group[n+1] = -1
    
group_= 0
for p in range(1,N+1):
    if color[p] != -1: 
        continue
    elif color[p] == -1: 
        start = p
        color[start] = 0
        que = deque([start])
        visit = deque([])
        group_+=1
        group[group_] = [start]

    depth[start] = 0
    while len(que) > 0:
        start = que[0]
#         print(start,que)
        for v in ad[start]:
#             print(v,color[v])
            if color[v] == -1:
                que.append(v)
                color[v] = 0
                depth[v] = depth[start]+1
                group[group_].append(v)
                
        color[start] = 1
        visit.append(que.popleft())

ans=0
for g in group.keys():
    if len(group[g]) > ans:
        ans=len(group[g])
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 i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)

# print(uf.roots())

max_num = 0
for root in uf.roots():
    max_num = max(max_num, uf.size(root))
print(max_num)

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)

ml = 0
for n in uf.roots():
    ml = max(ml, uf.size(n))

print(ml)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.par = [-1] * n


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


    def root(self, x):
        path = []
        while self.par[x] >= 0:
            path.append(x)
            x = self.par[x]
        for y in path:
            self.par[y] = x
        return x


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


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


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

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

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

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
l = [-1]*N
f = []
cnt = 0
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if l[a] < 0 and l[b] < 0:
        f.append([a, b])
        l[a] = cnt
        l[b] = cnt
        cnt += 1
    elif l[a] >= 0 and l[b] < 0:
        f[l[a]].append(b)
        l[b] = l[a]
    elif l[b] >= 0 and l[a] < 0:
        f[l[b]].append(a)
        l[a] = l[b]
    elif l[b] != l[a]:
        if len(f[l[a]]) > len(f[l[b]]):
            for i in f[l[b]]:
                l[i] = l[a]
                f[l[a]].append(i)
        else:
            for i in f[l[a]]:
                l[i] = l[b]
                f[l[b]].append(i)
ans = 1
for l in f:
    ans = max(ans, len(l))
print(ans)

Submission status: Accepted

Solution code:
import collections as cc
I=lambda:list(map(int,input().split()))
mod=10**9+7
n,m=I()
ds=[i for i in range(n+1)]
r=[1]*(n+1)
def find(a):
    while ds[a]!=a:
        a=ds[a]
    return a
def join(a,b):
    x=find(a)
    y=find(b)
    if x!=y:
        ds[x]=ds[y]=min(x,y)
        r[min(x,y)]+=r[max(x,y)]
for i in range(m):
    x,y=I()
    join(x,y)
temp=cc.Counter(ds[1:])
print(max(r))

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
INF = 10**9
mod = 10**9+7

class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]

N,M = I()
u = UnionFind(N)
for i in range(M):
    a,b = I()
    u.unite(a-1,b-1)
ans = 0
for i in range(N):
    ans = max(ans,u.count(i))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# map(int, input().split())
from collections import deque

class Node():
    def __init__(self, idx):
        self.idx = idx
        self.next_node = []
        self.is_searched = False
    
    def add_node(self, node):
        self.next_node.append(node)

N, M = map(int, input().split())
nodes = {n+1: Node(n+1) for n in range(N)}

for m in range(M):
    A, B = map(int, input().split())
    nodes[A].add_node(nodes[B])
    nodes[B].add_node(nodes[A])

# 幅優先で友達クラスターを作る
clusters = []
for i in range(N):
    que = deque([nodes[i+1]])
    cluster = []
    while len(que) != 0:
        node = que.pop()
        if not node.is_searched:
            cluster.append(node)
            que.extend(node.next_node)
            node.is_searched = True

    clusters.append(cluster)

print(max([len(cluster) for cluster in clusters]))

Submission status: Accepted

Solution code:
def connected_components(n, graph):
    components, visited = [], [False] * n

    def dfs(start):
        component, stack = [], [start]

        while stack:
            start = stack[-1]

            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)

            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)

        return component

    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))

    return components

n,m=map(int,input().split())
adj=[]
for i in range(n+1):
	adj.append([])
for i in range(m):
	a,b=map(int,input().split())
	adj[a].append(b)
	adj[b].append(a)
mat=connected_components(n+1,adj)
ans=0
for i in mat:
	if(len(i)>ans):
		ans=len(i)
print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n, m = (int(x) for x in input().split())

    node___neighs = {x: set() for x in range(1, n + 1)}

    for _ in range(m):
        n1,n2 = (int(x) for x in input().split())
        node___neighs[n1].add(n2)
        node___neighs[n2].add(n1)

    node___comp = {}

    curr_comp = 1
    comp___size = {}
    for node in range(1, n+1):
        if node___comp.get(node, False):
            continue
        stack = [node]
        curr_size = 1
        node___comp[node] = curr_comp

        while stack:
            curr_node = stack.pop()
            for neigh in node___neighs[curr_node]:
                if node___comp.get(neigh, False):
                    continue
                node___comp[neigh] = curr_comp
                curr_size += 1
                stack.append(neigh)
            
        comp___size[curr_comp] = curr_size
        curr_comp += 1
    print(max(comp___size.values()))

Submission status: Accepted

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

g = defaultdict(set)
for a,b in AB:
    g[a].add(b)
    g[b].add(a)

visited = [False] * (N+1)

ans = 0
for s in range(1,N+1):
    if visited[s]:
        continue
    dq = deque([s])
    cnt = 0
    while dq:
        v = dq.popleft()
        if visited[v]:
            continue
        cnt += 1
        visited[v] = True
        for nv in g[v]:
            if not visited[nv]:
                dq.append(nv)
    ans = max(ans,cnt)

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):
    uf.union(*(int(x) - 1 for x in input().split()))
print(max(uf.size(x) for x in range(n)))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n,m=map(int,input().split())
c=UnionFind(n)
for _ in range(m):
    a,b=map(int,input().split())
    c.union(a-1,b-1)
ans=0
for i in range(n):
    ans=max(ans,c.size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

N,M=map(int,input().split())
P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[B]<size[C]:
        P[B]=P[C]
        size[C]+=size[B]
    else:
        P[C]=P[B]
        size[B]+=size[C]

for i in range(M):
    a,b=map(int,input().split())
    if find(a)==find(b):
        P[a]=find(a)
        P[b]=find(b)
        continue
    else:
        union(a,b)
for i in range(N+1):
    P[i]=find(P[i])
#print(P)
D={}
for i in range(1,N+1):
    if P[i] not in D:
        D[P[i]]=1
    else:
        D[P[i]]+=1
ans=0
for k,v in D.items():
    if ans<v:
        ans=v
print(ans)

Submission status: Accepted

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

root = [i for i in range(N + 1)]
size = [1] * (N + 1)
 
def find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = find(y)
    root[x] = z
    return z

def union(x, y):
  rx = find(x)
  ry = find(y)
  sx = size[rx]
  sy = size[ry]
  if rx == ry:
    return 0
  else:
    if sx >= sy:
      root[ry] = rx
      size[rx] = sx + sy
    else:
      root[rx] = ry
      size[ry] = sx + sy
    return sx * sy

cnt = [0] * (N + 1)

for a, b in AB:
    union(a, b)
for i in range(1, N + 1):
    cnt[find(i)] += 1

print(max(cnt))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = MAP()
L = [LIST() for i in range(M)]

tree = UnionFind(N)
friends = defaultdict(list)
for a, b in L:
    friends[a-1].append(b-1)
    friends[b-1].append(a-1)
    tree.union(a-1, b-1)
# print()
# print(tree.group_count())
dic = defaultdict(int)
for i in range(N):
    al = tree.find(i)
    # print(al)
    dic[al] += 1
# print(dic.values())
# exit()
l = list(dic.values())
# print(friends)
# exit()
# l = []
# for key in al:
#     l.append(len(al[key]))
l.sort()
sl = set(l)
tmp = 0
ans = 0
for y in sl:
    # y -= ans
    y -= tmp
    ans += y
    tmp += y

    #  += y
print(ans)

Submission status: Accepted

Solution code:
#ここまでテンプレ
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n,m = map(int,stdin.readline().rstrip().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())

f = UnionFind(n)

for _ in range(m):
    a,b = map(int,stdin.readline().rstrip().split())
    a -= 1
    b -= 1
    f.union(a,b)

ma = 0

for i in range(n):
    ma = max(ma,f.size(i))

print(ma)

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())
if m == 0:
    print(1)
    exit()
uf = UnionFind(n)
ans = 0
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
    ans = max(ans, uf.size(a-1))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

li = []
seen = [False]*n
for i in range(n):
    if seen[i]:
        continue
    q = deque([i])
    seen[i] = True
    cnt = 1
    while q:
        node = q.popleft()
        for i in graph[node]:
            if seen[i]:
                continue
            seen[i] = True
            cnt += 1
            q.append(i)
    li.append(cnt)
print(max(li))

Submission status: Accepted

Solution code:
def find(x):
	while x!=p[x]:
		x=p[x]
	return x

def union(a,b):
	x=find(a)
	global con
	y=find(b)
	if x!=y:
		p[y]=p[x]=min(x,y);con-=1
		r[min(x,y)]+=r[max(x,y)];con=max(con,r[min(x,y)])
n,m=map(int,input().split())
p=[i for i in range(n+1)]
con=1
r=[1]*(n+1)
for i in range(m):
  u,v=map(int,input().split())
  union(u,v)
print(max(r))

Submission status: Accepted

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

N, M = map(int, input().split())
friends = [[] for _ in range(N)]
for k in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  friends[A].append(B)
  friends[B].append(A)
group = []
sgn = [0 for _ in range(N)] #0なら未所属
def make_group(person, groupnum):
  sgn[person] = 1
  for f in friends[person]:
    if sgn[f] == 0:
      group[groupnum].append(f)
      make_group(f, groupnum)
  return None

c = 0
for k in range(N):
  if sgn[k] == 0:
    group.append([k])
    make_group(k, c)
    c += 1
ans = 0
for g in group:
  ans = max(len(g), ans)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

#Union Find
def root(x):
    while par[x]!=x:
        x=par[x]
    return x

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

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[y]<size[x]: x,y=y,x  #yの要素数を大きくする
    size[y]+=size[x]
    par[x]=y #yが親ノード

def getsize(x):
	return size[root(x)]

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)

ans=float("-inf")
for i in range(1,N+1):
    ans=max(ans,getsize(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 = list(map(int, input().split()))
u = UnionFind(N)
for i in range(M):
    a, b = list(map(int, input().split()))
    a, b = a - 1, b - 1
    u.union(a, b)
n_size = 0
for i in range(N):
    n_size = max(n_size, u.size(i))
print(n_size)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
ans=0
friendset=[0]*N
pset=set()#まだどの友人グループにも属していない人
for h in range(N):
    pset.add(h)
    friendset[h]=set()
for p in range(M):
    A,B=map(int,input().split())
    A-=1
    B-=1
    friendset[A].add(B)
    friendset[B].add(A)
#print(friendset)
while(len(pset)!=0):
    kouho=1
    d=deque()
    i=pset.pop()
    d.append(i)
    while(len(d)!=0):
        person=d.popleft()
        for k in friendset[person]:
            if k in pset:
                #print(person,k)
                d.append(k)
                pset.remove(k)
                friendset[k].remove(person)
                kouho+=1
    ans=max(kouho,ans)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
tomodati=[[] for i in range(n+1)]
syozoku=[0]*(n+1)
group_list=[0]*(10**6)
for i in range(m):
    a,b=map(int, input().split())
    tomodati[a].append(b)
    tomodati[b].append(a)

from collections import deque
tomo_que=deque()
group=0
for i in range(1,n+1):
    group+=1
    tomo_que.append(i)
    while tomo_que:
        moto=tomo_que.popleft()
        if syozoku[moto]==0:
            syozoku[moto]=group
            group_list[group]+=1

        for i in tomodati[moto]:
            if syozoku[i]==0:
                syozoku[i]=group
                tomo_que.append(i)
                group_list[group]+=1

print(max(group_list))

Submission status: Accepted

Solution code:
from collections import deque
n, m= map(int, input().split())
lis = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

seen = [False] * n
ans = 1
for i in range(n):
    if seen[i] == False:
        queue = deque([i])
        seen[i] = True
        tmp =0
        while queue:
            now = queue.pop()
            tmp += 1
            for j in lis[now]:
                if seen[j] == True:
                    continue
                else:
                    seen[j] = True
                    queue.append(j)
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def bfs(s):
  q = [s]
  visited[s] = True
  c = 0
  while q != []:
    p = q[0]
    c += 1
    del q[0]
    for node in adj[p]:
      if not visited[node]:
        visited[node] = True
        q.append(node)
  return c

n,m = map(int,input().split())
adj = defaultdict(list)
visited = [False]*(n+1)
ans = 0
for _ in range(m):
  a,b = map(int,input().split())
  adj[a].append(b)
  adj[b].append(a)
for i in range(1,n+1):
  if not visited[i]:
    ans = max(ans,bfs(i))
print(ans)