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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, m = LI()
    ab = LIR(m)
    par = [i for i in range(n)]
    size = [1] * n
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(a, b):
        a = root(a)
        b = root(b)
        if a == b:
            return
        if size[a] < size[b]: a, b = b, a
        par[b] = a
        size[a] += size[b]
    for a, b in ab:
        a -= 1
        b -= 1
        unite(a, b)
    
    print(max(size))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
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())
uf = UnionFind(N)
for _ in range(M):
  a,b = map(int,input().split())
  uf.union(a-1,b-1)
ans = 0
for i in range(N):
  if uf.size(i) > ans:
    ans = uf.size(i)
print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

ab_list = []
ans =0
for i in range(M):
    a,b = map(int, input().split())
    a, b = a-1, b-1
    uf.union(a, b)

ans = 0
ans_list = uf.roots()
for i in range(len(ans_list)):
    ans = max(ans, uf.size(ans_list[i]))

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n,m = list(map(int,input().split()))
N = [[] for _ in range(n)]
V = [0] * n

for _ in range(m):
  a,b = list(map(int,input().split()))
  a -= 1
  b -= 1
  N[a].append(b)
  N[b].append(a)
  
for i in range(n):
  N[i] = list(set(N[i]))
ans = 0

for i in range(n):
  if V[i] == 0:
    cnt = 1
    Q = [i]
    V[i] = 1
    
    while Q:
      node = Q.pop()
      for child in N[node]:
        if V[child]==0:
          Q.append(child)
          V[child] = 1
          cnt += 1
    ans = max(ans, cnt)
          
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n, m = map(int, input().split())

friend = [set() for i in range(n)]

for i in range(m):
  a = list(map(int, input().split()))
  a.sort()
  x, y = a[0]-1,a[1]-1
  friend[x].add(y)
  friend[y].add(x)

def dfs(s):
  if vis[s] == False:
    vis[s] = True
    ary.append(s)
    for j in friend[s]:
      dfs(j)
vis = [False for i in range(n)]
ans = 0
for i in range(n):
  ary = []
  dfs(i)
  ans = max(ans,len(ary))
print (ans)

Submission status: Accepted

Solution code:
from collections import deque

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

directcount = [0] * n # node_iが直接接続しているノードの数
visited = [-1]  * n # nodeの色,
colorcount = [-1] * n # 各色が何個のノードを持つか
# グラフの初期化
g = []
for _ in range(n):
    g.append(deque(list()))

# グラフの生成
for i in range(m):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1 # 1origin -> 0 origin
    g[a].append(b)
    g[b].append(a)
    # 直接接続されているノードの数
    directcount[a] += 1
    directcount[b] += 1

# dfs 連結したグラフごとにそのグラフの最初に探索したnodeの色に染める
q = deque(list()) #探索キュー
for i in range(n):
    q.append(i)
    color = i
    #cnt = []
    cnt = 1
    while len(q) > 0:
        nextnode = q.popleft() # 次の探索
        if visited[nextnode] != -1:
            continue
        visited[nextnode] = color
        q.extend(g[nextnode]) # nextnodeの辺を足す
        #cnt.append(color)
        cnt += 1
    # 探索が終わったらその色のノードの数を記録
    colorcount[color]  = cnt -1

print(max(colorcount))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ex = [0 for i in range(n)]
fri = {}

for i in range(m):
    a, b = map(int, input().split())
    if ex[a-1] == 0 and ex[b-1] == 0:
        if a > b:
            a, b = b, a
        ex[a-1] = a
        ex[b-1] = a
        fri[a] = [a, b]
    elif ex[a-1] == 0:
        ex[a-1] = ex[b-1]
        fri[ex[b-1]].append(a)
    elif ex[b-1] == 0:
        ex[b-1] = ex[a-1]
        fri[ex[a-1]].append(b)
    elif ex[a-1] == ex[b-1]:
        continue
    else:
        shozoku = min(ex[a-1], ex[b-1])
        mu = max(ex[a-1], ex[b-1])
        for j in range(len(fri[mu])):
            ex[fri[mu][j]-1] = shozoku
        fri[shozoku].extend(fri.pop(mu))

ans = 1
for key in fri:
    ans = max(ans, len(fri[key]))
print(ans)

Submission status: Accepted

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

    def find(self,a):
        if self.parent[a] == a:
            return a
        else:
            return self.find(self.parent[a])

    def unite(self,a,b):
        a_root = self.find(a)
        b_root = self.find(b)
        if a_root == b_root:
            return
        else:
            if self.size_of(b_root) > self.size_of(a_root): 
                self.parent[a_root] = self.parent[b_root]
                self.size[b_root] += self.size[a_root]
            else:
                self.parent[b_root] = self.parent[a_root]
                self.size[a_root] += self.size[b_root]
                
    def size_of(self,a):
        return self.size[self.find(a)]
    
    def is_same(self,a,b):
        return self.find(a) == self.find(b)

N,M = map(int,input().split())
tree = UnionFind(N)
for i in range(M):
    X, Y = map(int,input().split())
    tree.unite(X-1,Y-1)

print(max([tree.size_of(x) for x in range(N)]))

Submission status: Accepted

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

friends = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    friends[a].add(b)
    friends[b].add(a)
# print(friends)

visited = [0]*N #グループを作って合ったら
ans = 0
for i in range(N):
    if visited[i]:
        continue
    tmp = list(friends[i])
    ans_tmp = 1
    visited[i] = 1
    while tmp:
        t = tmp.pop()
        if not visited[t]:
            visited[t] = 1
            ans_tmp += 1
            for j in friends[t]:
                tmp.append(j)

    ans = max(ans, ans_tmp)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

    def is_same(self, x, y):  # x, y が同じ集合に属するか判定する
        return self.find(x) == self.find(y)

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]


N, M = map(int, input().split())
A, B = [0] * M, [0] * M  # 入力時に 0-index に合わせる

direct =[[] for _ in range(N)]  # 同じ集合の友達もしくはブロック関係の人
uf = UnionFind(N)  # 友達関係をまとめた UnionFind 木

for i in range(M):
    A[i], B[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1
    direct[A[i]].append(B[i])
    direct[B[i]].append(A[i])
    uf.unite(A[i], B[i])

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

Submission status: Accepted

Solution code:
N,M = [int(x) for x in input().split()]
#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+1)
for i in range(M):
    a,b = [int(x) for x in input().split()]
    unite(a,b)
ans = 0
for i in range(1,N):
    ans = max(ans,size(i))
print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

uf = UnionFind(n)

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

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

Submission status: Accepted

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

def int_list():
    return list(map(int,input().split()))

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import collections as col

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix


# main code
N,M = int_map()

i = []
j = []

for z in range(0,M):
    a,b = int_map()
    i.append(a-1)
    j.append(b-1)
    
d = [1]*M

csr = csr_matrix((d,(i,j)),(N,N))


n, labels = connected_components(csr)

ll = list(labels)
aa = col.Counter(ll)
print(aa.most_common()[0][1])

Submission status: Accepted

Solution code:
#Uses python3
import sys
import threading

# This code is used to avoid stack overflow issues
sys.setrecursionlimit(10**7) # max depth of recursion
threading.stack_size(2**29)  # new thread will get stack of such size

visited = set()

def explore(adj, x, comp, cc):
    visited.add(x)
    if not(cc in comp):
        comp[cc] = []
    comp[cc].append(x)
    for w in adj[x]:
        if not (w in visited):
            explore(adj, w, comp, cc)

def number_of_components(adj, n):
    #visited = [False for _ in range(n)]
    cc = 0
    comp = dict()
    for v in range(n):
        if not(v in visited):
            explore(adj, v, comp, cc)
            cc += 1
    return comp


def main():
    n, m = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    res = number_of_components(adj, n)
    max_ = 0
    for value in res.values():
        max_ = max(max_, len(value))
    print(max_)
    #print(n - number_of_components(adj, n) - 1)


threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
def resolve():
    from collections import defaultdict, deque
    N, M = [int(i) for i in input().split()]
    AABB = [[int(i) - 1 for i in input().split()] for _ in range(M)]
    dic = defaultdict(set)
    for a, b in AABB:
        dic[a].add(b)
        dic[b].add(a)
    groups = [-1 for _ in range(N)]
    group = 0
    groupmemcnt = [0 for _ in range(N)]
    for i in range(N):
        if groups[i] != -1:
            continue
        groups[i] = group
        groupmemcnt[group] += 1
        que = deque(list(dic[i]))
        while len(que) > 0:
            j = que.popleft()
            if groups[j] != -1:
                continue
            groups[j] = group
            groupmemcnt[group] += 1
            que.extend(list(dic[j]))
        group += 1
    print(max(groupmemcnt))
    return

resolve()

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


uf = UnionFind(N)

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

maxSize = 0
for x in range(N):
    maxSize = max(maxSize, uf.size(x))
print(maxSize)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
set_dict = {}
chech_list = [0] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    if a in set_dict:
        set_dict[a].add(b)
    else:
        set_dict[a] = {b}
    if b in set_dict:
        set_dict[b].add(a)
    else:
        set_dict[b] = {a}
    chech_list[a] = 1
    chech_list[b] = 1

ans = 1
for i in range(1, n + 1):
    if chech_list[i] == 0:
        continue
    count = 0
    temp_set = set_dict[i]
    while len(temp_set) > 0:
        x = temp_set.pop()
        count += 1
        chech_list[x] = 0
        for y in set_dict[x]:
            if chech_list[y] == 1:
                temp_set.add(y)
    ans = max(count, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


N, M = map(int, input().split())
C = [set([]) for i in range(N)]


def dfs(n, y):
    seen[n] = True
    y += 1
    for c in C[n]:
        if seen[c]:
            continue
        else:
            y = dfs(c, y)
    return y


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

ans = 0
seen = [False] * N
for i in range(N):
    if seen[i]:
        continue
    x = 0
    x = dfs(i, x)
    ans = max(ans, x)

print(ans)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, M, ABs):
    f_map = [[] for _ in range(N + 1)]
    for A, B in ABs:
        f_map[A].append(B)
        f_map[B].append(A)
    group = [-1] * (N + 1)
    latest_gnum = 1
    for i in range(1, N  + 1):
        if group[i] != -1:
            continue
        group[i] = latest_gnum
        latest_gnum += 1
        dq = deque([i])
        while dq:
            n = dq.popleft()
            for f in f_map[n]:
                if group[f] != -1:
                    continue
                group[f] = group[n]
                dq.append(f)
    group_sum = [0] * latest_gnum
    for g in group[1:]:
        group_sum[g] += 1
    print(max(group_sum))


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    N, M = map(int, input().split())
    ABs = [[int(i) for i in input().split()] for _ in range(M)]
    # Bs = [int(i) for i in input().split()]
    solve(N, M, ABs)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A, B = [], []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

friends = [-1] * (N+1)
number = [1] * (N+1)

for i in range(M):
    k = A[i]
    l = B[i]
    while True:
        if friends[k] == -1:
            break
        k = friends[k]

    while True:
        if friends[l] == -1:
            break
        l = friends[l]
    if k == l:
        continue
    if number[k] >= number[l]:
        friends[l] = k
        number[k] += number[l]
        number[l] = 0
    else:
        friends[k] = l
        number[l] += number[k]
        number[k] = 0

print(max(number))

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
REL = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    REL[a-1].add(b-1)
    REL[b-1].add(a-1)
REL = [list(s) for s in REL]

ans = 0
todo = []
done = set()
pdone = set()
for s in range(N):
    if s in done:
        continue
    pdone.clear()
    todo.append(s)
    while todo:
        p = todo.pop()
        pdone.add(p)
        done.add(p)
        for np in REL[p]:
            if np in pdone:
                continue
            todo.append(np)
    ans = max(ans, len(pdone))
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
        
        # 根のparentsはそのグループの要素数 * (-1) がはいる
        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)
ans = 1

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
    ans = max(ans, uf.size(a))

print(ans)

Submission status: Accepted

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


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

G=[[] for i in range(n)]

for i in range(m):
    a,b=input().split()
    G[int(a)-1]+=[int(b)-1]
    G[int(b)-1]+=[int(a)-1]

#print(G)

dist=[-1 for i in range(n)]
# que=deque([0])
# dist[0]=0

count=0
def bfs(G):
    global count
    #print(que)
    if not que:
        return
    v = que.popleft()

    for nv in G[v]:
        if dist[nv] != -1:
            continue
        dist[nv]=dist[v]+1
        que.append(nv)
    count+=1
    
    bfs(G)

ans=0
for i in range(n):
    count=0
    if dist[i] != -1:
        continue
    else:
        que=deque([i])
        dist[i]=0
        bfs(G)
        if ans < count:
            ans=count

print(ans)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
par=[i for i in range(n)]
ro=dict()

for i in range(n):
    ro[i]=1
def root(i):
    if par[i]==i:
        return i
    else:
        a=root(par[i])
        par[i]=a
        return a

def unite(x,y):
    rx=root(x)
    ry=root(y)
    if rx!=ry:
        par[rx]=ry
        ro[ry]+=ro[rx]
        ro[rx]=0

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

print(max(ro.values()))

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(Q)]
par = [i for i in range(N+1)]
rank = [0]*(N+1)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x]==rank[y]:rank[x]+=1

for a,b in ab:
    unite(a,b)
for a,b in ab:
    unite(a,b)

from collections import*
C=Counter(par)
A=max(C.values())
print(A)

Submission status: Accepted

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

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

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

            if x == y:
                return

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

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
def findgraphs(nodes):
    graphs = []
    while nodes:
        graph = set()
        queue = set([next(iter(nodes))])
        while queue:
            nextq = set()
            graph.update(queue)
            for q in queue:
                nextq.update(n for n in nodes[q] if n not in graph)
                del nodes[q]

            queue = nextq

        graphs.append(graph)

    return graphs




friends = dict()
N, M = map(int, input().split())
nodes = {x : set() for x in range(1, N+1)}
for _ in range(M):
    A, B = map(int, input().split())
    nodes[A].add(B)
    nodes[B].add(A)
graphs = findgraphs(nodes)

m = max(len(g) for g in graphs)
print(m)

Submission status: Accepted

Solution code:
from collections import Counter
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def getParent(self):
        return [self.find(i) for i in range(N)]

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

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

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

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))


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

friend = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    friend.unite(a-1, b-1)

roots = friend.getParent()
counts = Counter(roots)

ans = max(counts.values())
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import networkx as nx

def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G=nx.Graph()

    if M == 0 :
        print(1)
        return

    for a, b in zip(A,B):
        G.add_edge(a, b)

    Gc = max(nx.connected_components(G), key=len)
    print(len(Gc))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

friendsetlist = [set([]) for _ in range(n)]

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

    friendsetlist[a].add(b)
    friendsetlist[b].add(a)

dq = deque([])

checked = [0 for _ in range(n)]

ans = 0

for i in range(n):
    if checked[i] == 0:
        dq.append(i)
        checked[i] = 1
        tmpans = 1
        while len(dq) != 0:
            now = dq.popleft()
            for nxt in friendsetlist[now]:
                if checked[nxt] == 0:
                    tmpans += 1
                    dq.append(nxt)
                    checked[nxt] = 1
        if ans < tmpans:
            ans = tmpans

print(ans)