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

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[(i,1)for i in range(n)]
def find(i):
  if p[i][0]==i:return i
  else:
    c=find(p[i][0])
    p[i]=(c,0)
    return c
def union(i,j):
  pi=find(i)
  pj=find(j)
  if not pi==pj:
    if p[pi][1]>p[pj][1]:
      p[pi]=(pi,p[pi][1]+p[pj][1])
      p[pj]=(pi,0)
    else:
      p[pj]=(pj,p[pi][1]+p[pj][1])
      p[pi]=(pj,0)
      

for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if p[i][0]==i:ans=max(ans,p[i][1])
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict


n,m=map(int,input().split())
d=defaultdict(int)
parent=[-1]*(n+1)
def find(a):
    if parent[a]<0:
        return a
    parent[a]=find(parent[a])
    return parent[a]
    # else:
    #     l = []
    #     while parent[a]>0:
    #         l.append(a)
    #         a=parent[a]
    #     for i in l:
    #         parent[i]=a
    #     return a

def union(a,b):
    parent[a]+=parent[b]
    parent[b]=a
    d[parent[a]]+=d[parent[b]]+1
for i in range(m):
    a,b= map(int, input().split())
    if a>b:a,b=b,a
    a=find(a)
    b=find(b)
    if a!=b:
        union(a,b)
ans=0

for x in parent[1:]:
    x=-x
    ans=max(ans,x)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
INF = float('inf')
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, sys.stdin.readline().rstrip("\n").split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
for _ in range(n):
    edge[_] = list(set(edge[_]))
done = [False]*n
d = deque()
gmax = -INF
for i in range(n):
    if not done[i]:
        done[i] = True
        d.append(i)
        g = 1
        while d:
            cp = d.pop()
            for np in edge[cp]:
                if not done[np]:
                    done[np] = True
                    d.append(np)
                    g += 1
        gmax = max(gmax,g)
print(gmax)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
for i in range(m):
  a,b=f()
  unite(a-1,b-1)
print(-min(p))

Submission status: Accepted

Solution code:
from collections import Counter


class UnionFind:

    def __init__(self, size):
        self.size = size
        self.par = list(range(size))
        self.rank = [0]*size

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

    def unite_tree(self, x, y):
        x, y = self.find_par(x), self.find_par(y)
        if x == y:
            return

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

    def in_the_same(self, x, y):
        return self.find_par(x) == self.find_par(y)


if __name__ == "__main__":
    N, M = map(int, input().split())
    uf = UnionFind(N)
    C = Counter()
    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        uf.unite_tree(a, b)
    for i in range(N):
        C[uf.find_par(i)] += 1
    print(C.most_common()[0][1])

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

n,m=[int(i) for i in input().split()]
data=[1]*m

row=[]
col=[]

for i in range(m):
    one,two=[int(i) for i in input().split()]
    n_one=min(one-1,two-1)
    n_two = max(one - 1, two - 1)
    row.append(n_one)
    col.append(n_two)

graph=csr_matrix((data,(row,col)),shape=(n,n))
num,label=connected_components(graph)

count_num=[0]*n
for i in label:
    count_num[i]+=1

print(max(count_num))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents =[-1 for i in range(n)]
    # どのグループに属しているかを返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

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


N, M = map(int, input().split())
uf = UnionFind(N)
X = [[] for _ in range(M)]
for i in range(M):
    X[i] = list(map(int, input().split()))
    uf.unite(X[i][0]-1, X[i][1]-1)
print(-min(uf.parents))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
S = [set() for i in range(N)]
visited = [-1] * N
colorcount = [-1] * N

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

q = deque()
for i in range(N):
    q.append(i)
    color = i
    cnt = 1
    while len(q):
        nt = q.popleft()
        if visited[nt] != -1:
            continue
        visited[nt] = color
        q.extend(S[nt])
        cnt += 1
    colorcount[color] = cnt - 1

print(max(colorcount))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        データが属するグループのID(と考えて良いはず)を取得する。
        :調査するグループ x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つのデータが属するグループを結合する。
        :結合するデータ(1つ目) x:
        :結合するデータ(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(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:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

    def is_same(self, x, y):
        return self.getroot(x) == self.getroot(y)

    def members(self, x):
        """
        指定したグループに属するデータの一覧を返す。size()と比較して速度が圧倒的に遅いので注意。
        :調査グループ x:
        """
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(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 resolve(test_def_name=""):
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(m)]

    work_abs = []
    for ab in ab_s:
        a = min(ab[0], ab[1])
        b = max(ab[0], ab[1])
        work_abs.append([a, b])

    ab_s = list(map(list, set(map(tuple, work_abs))))

    uf = UnionFind(n + 1)

    for a, b in ab_s:
        uf.union(a, b)

    ans = 0
    for aaa in uf.roots():
        ans = max(ans, uf.size(aaa))

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5 6
1 2
2 1
3 4
1 2
2 1
5 1"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4"""
        output = """4"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10 4
3 1
4 1
5 9
2 6"""
        output = """3"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original(self):
        pass


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

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())
      
    def main(self):
      return max([len(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)
  
print(-min(uf.parents))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

cnt = 0
for pa in uf.par:
    cnt = min(pa, cnt)
print(-cnt)

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

    def max_group_members(self):
        return -min([i for i in self.parents if i<0])
    
N,M = map(int,input().split())

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

print(uf.max_group_members())

Submission status: Accepted

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N, M = map(int, input().split())
    friend = [[] for _ in range(N + 1)]
    for _ in range(M):
        a,b = map(int, input().split())
        friend[a].append(b)
        friend[b].append(a)
    notchecked = set(list(range(1, N+1)))
    group = [0]*(N+1)
    nowgroup = 1
    while len(notchecked) > 0:
        now = collections.deque([notchecked.pop()])
        while len(now) > 0:
            d = now.popleft()
            group[d] = nowgroup
            notchecked.discard(d)
            for f in friend[d]:
                if f in notchecked:
                    group[f] = nowgroup
                    now.append(f)
                else:
                    continue
        nowgroup += 1
    countdic = {}
    for i in group:
        if i not in countdic:
            countdic[i] = 1
        else:
            countdic[i] += 1
    ans = max(countdic.values())
    print(ans)


if __name__ == '__main__':
    solve()

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(-min(uf.parents))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


import sys
from collections import deque
from collections import defaultdict
from collections import Counter
import heapq
import collections
import itertools
import bisect
import copy
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz(): return list(map(int, sys.stdin.readline().split()))


def z(): return int(sys.stdin.readline())


def S(): return sys.stdin.readline()[:-1]


def C(line): return [sys.stdin.readline() for _ in range(line)]


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 = zz()
A = [0]*M
B = [0] * M
tree = UnionFind(N)
# friends = [[0]*N for i in range(N)]
# print(friends)
for i in range(M):
    a, b = zz()
    a -= 1
    b -= 1
    # A[i], B[i] = a, b
    tree.union(a, b)
ans = 0
for p in tree.parents:
    ans = max(ans, tree.size(p))
if (ans == 0):
    print(N)
else:
    print(ans)
# used = [0]*N
# group = UnionFind(N)

# for i in range(N):
#     if (used[i] == 1):
#         # すでに振り分け済み
#         continue
#     for j in range(i + 1, N):
#         if (used[j] == 1):
#             # すでに振り分け済み
#             continue
#         if (tree.same(i, j)):
#             # 友達
#             continue
#         else:
#             used[i] = 1
#             used[j] = 1
#             group.union(i, j)

#     # # 全員と友達
#     # if (used[i] == 0):
# # print(used)
# print(group.group_count())


# 最大でNグループにわければいける
# 素朴にやる

Submission status: Accepted

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

n, m = map(int, input().split())
ans = [0 for _ in range(n)]
trees = [[] for _ in range(n)]

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

visited = [False]*n
def dfs(n):
    visited[n] = True
    global temp
    temp+=1
    for i in trees[n]:
        if visited[i]:
            continue
        dfs(i)

ans=0
for x in range(n):
    if visited[x]:
        continue
    temp=0
    dfs(x)
    ans=max(temp,ans)
print(ans)

Submission status: Accepted

Solution code:
import collections

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

for i in range(M):
    A, B = map(int, input().split())
    tree.unite(A-1, B-1)

roots = [tree.find(p) for p in tree.parent]
count = collections.Counter(roots).most_common(1)[0][1]
print(count)

Submission status: Accepted

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def union(self, a, b):
        self.parent[self.find(b)] = self.find(a)




n , m = map(int , input().split())
#dic = defaultdict(set)
uf = UnionFind(n)
for ii in range(m):
	u,v = map(int , input().split())
	u-=1
	v-=1
	uf.union(u,v)
c = [0]*n
for i in range(n):
	c[uf.find(i)] += 1
print(max(c))



'''
import collections,sys,threading
sys.setrecursionlimit(10**9)
threading.stack_size(10**8)






########################################
def solve():
	n , m = map(int , input().split())
	dic = defaultdict(set)
	for ii in range(m):
		u,v = map(int , input().split())
		dic[u].add(v)
		dic[v].add(u)
	l = []
	visited = [0]*(n+2)
	def f(node):
		visited[node] = True
		temp = 0
		for nei in dic[node]:
			if not visited[nei]:
				temp += f(nei)
				#print("?",node, nei , temp)
		return temp
	for i in range(1,n+1):
		if not visited[i]:
			l.append(f(i)+1)
	#print(dic)
	#print(l)
	print(max(l))


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

'''

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
class UnionFind():
    def __init__(self, n):
        #初期化[-1]*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,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):
        #要素xが所属するグループの人数を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        #要素xとyが同じグループかどうか(同じならTrue)
        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):
        #Find-Treeの頂点
        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 max_members_group(self):
        return max([self.size(r) for r in self.roots()])

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

    #遷移を確認したいときはこちらに書き換えて実行する(for以降の経路圧縮が行われていない)
    #def __str__(self):
    #  return ''.join('{}: {}'.format(r, self.members(r)))

def main():
    n, m = list(map(int,input().split()))
    data = [input().split() for _ in range(m)]
 
    UF = UnionFind(n)
    for i in range(m):
        UF.union(int(data[i][0]) - 1, int(data[i][1]) - 1)
    print(UF.max_members_group())
    
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():

    n,m = map(int,input().split())
    ary = []
    for i in range(m):
        aa, bb = map(int,input().split())

        ary.append((aa-1,bb-1))
    ary_s = list(set(ary))
    a = []
    # b = []
    # Union-Find作る
    uf = UnionFind(n)

    for i in range(len(ary_s)):
        a.append(ary_s[i][0])
        a.append(ary_s[i][1])
        uf.union(ary_s[i][0], ary_s[i][1])
    ans = 1
    for i in a:
        ans = max(ans, uf.size(i))
    print(ans)

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

if __name__=='__main__':
    main()

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()))
friends = []
for i in range(m):
    f = list(map(int, input().split()))
    friends.append(f)

friend_map = UnionFind(n)

for f in friends:
    friend_map.union(f[0]-1, f[1]-1)

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

print(ans)

Submission status: Accepted

Solution code:
N,M=[int(s) for s in input().split()] 
hito=[0 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=set()
  reach.add(start)
  hito[start]=1
  while reach:
    _from=reach.pop()
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==0:
        reach.add(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==0:
    ans.add(dfs(h))
print(max(ans))

Submission status: Accepted

Solution code:
import sys

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

sys.setrecursionlimit(10**7)

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


v_visit = [False for _ in range(N)]

def search(n):
    count = 0
    for n_ in set(v_neighbor[n]):
        if not v_visit[n_]:
            v_visit[n_] = True
            count += 1
            count += search(n_)
    return count

res = 1
for i in range(N):
    if v_visit[i]:
        continue
    search_res = search(i)
    res = max(res, search_res)


print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
d= defaultdict(list)
n,m = [int(i) for i in input().split()]
visited = [False for i in range(n)]
for i in range(m):
    a,b=  map(int,input().split())
    a-=1
    b-=1
    d[a].append(b)
    d[b].append(a)
def dfs(a):
    count = 0
    stack = [a]
    while(stack):
        curr = stack.pop()
        count+=1
        visited[curr]=True
        for i in d[curr]:
            if visited[i]==False:
                visited[i]=True
                stack.append(i)
        #print(count)
    return count
ca=0
for i in range(n):
    if visited[i]==False:
        c= dfs(i)
        ca = max(ca,c)
print(ca)

Submission status: Accepted

Solution code:
#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,input().split())
	d[x].add(y)
	d[y].add(x)


vis={i:False for i in range(1,n+1)}
for u,v in d.items():
	d[u]=list(v)
count=0
que=[]
for i in range(1,n+1):
	if not vis[i]:
		que=[]
		c=1
		vis[i]=True
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if not vis[j]:
					vis[j]=True
					c+=1
					que.append(j)
		count=max(c,count)

print(count)