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:
from sys import exit, stdin

input = stdin.readline
import copy
from collections import deque, Counter

# import numpy as np


class BIT:
    def __init__(self, a=0):
        self.n = a
        self.d = [0] * (a + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.d[i] += x
            i += i & (-i)

    def sum(self, *i):
        if len(i) == 1:
            x = 0
            i += 1
            while i:
                x += self.d[i]
                i -= i & (-i)
            return x
        else:
            return sum(self, i[1] - 1) - sum(self, i[0] - 1)


class UnionFind:
    def __init__(self, N):
        # N = data size
        self.n = N
        self.parents = [-1] * N

    def find(self, x):
        # find x's root
        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):
        # unite x and y
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return False
        if -(self.parents[rx]) < -(self.parents[ry]):
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx
        return True

    def size(self, x):
        # size of group of x's root
        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 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()))

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


D = UnionFind(N)

for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    D.union(a, b)

num = [D.size(r) for r in D.roots()]

print(max(num))

Submission status: Accepted

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

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

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


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

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

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


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.root[x] += self.root[y]
        self.root[y] = x

    def size(self, x):
        return -1 * self.root[self.find(x)]


union_find = UnionFind(n)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
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():
    
    N, M = NMI()
    
    uf = UnionFind(N)
    
    for m in range(M):
        A,B = NMI()
        uf.union(A-1, B-1)
 
    ans = 0
    for n in range(N):
        ans = max(ans,uf.size(n))
    print(ans)
 
 

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
Union Find 木クラス
参考URL：https://note.nkmk.me/python-union-find/

parents
各要素の親要素の番号を格納するリスト
要素が根（ルート）の場合は-(そのグループの要素数)を格納する
例：
    parents[2] = 0 → 要素2の親は0
    parents[0] = -3 → 要素0は根であり、そのグループの要素数は3個
"""
class UnionFind():
    # 初期化（初期状態は全要素が根）
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            # 経路圧縮も同時に行う
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        # 根が同じならx,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)]

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    # グループの数を返す
    def group_count(self):
        return len(self.roots())

    # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    # print()での表示用
    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline
def r_map(): return map(int, readline().rstrip().split())

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

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

    def unite(self, x, y) -> bool:
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
        self.max_size = max(self.max_size, self.size(x))
        return True

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

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

    def is_same(self, x, y) -> bool:
        return self.root(x) == self.root(y)

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

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


def main():
    N, M = r_map()
    uf = UnionFind(N)
    for _ in range(M):
        a, b = r_map()
        uf.unite(a, b)
    print(uf.max_size)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


def resolve():
  N, M = map(int, input().split(" "))
  connections = []
  for _ in range(N):
    connections.append(deque())
  checked = [False] * N
  prev = [None] * N

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

  max_count = 0
  for i in range(N):
    if checked[i]:
      continue

    checked[i] = True
    count = 1 # 自身が入ってるので 1 から count 開始
    current = i
    # 根に戻ってくるまでループする
    while current != i or len(connections[current]) != 0:
      checked[current] = True
      # 次のノードを見つける
      next_node = connections[current].pop()
      # チェック済みのノードにぶつかった時は next_node を入れ替える。
      while checked[next_node]:
        if len(connections[current]) != 0:
          next_node = connections[current].pop()
        else:
          # チェック済みじゃ無いノードが見つからなかった場合は Break する。
          next_node = None
          break


      # チェックしながら行けるところまで行く
      while next_node is not None:
        prev[next_node] = current
        current = next_node
        # 移動した瞬間に count をインクリメントする。
        count += 1
        checked[current] = True
        # next_node　が見つからなかった場合は Break. 遡る処理に入る。
        if len(connections[current]) == 0:
          break

        next_node = connections[current].pop()
        # チェック済みのノードにぶつかった時は next_node を入れ替える。
        while checked[next_node]:
          if len(connections[current]) != 0:
            next_node = connections[current].pop()
          else:
            # チェック済みじゃ無いノードが見つからなかった場合は Break する。
            next_node = None
            break
      
      # 行き止まりにまで到達してることが保証されているので一旦 1 つ戻る
      if prev[current] is None:
        continue
      current = prev[current]

      # 次の分岐が来るまで遡る
      while len(connections[current]) == 0:
        if prev[current] is not None:
          current = prev[current]
        else:
          break

    max_count = max(count, max_count)
  # print(prev)
  print(max_count)

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
t = [-1] * N

import sys
sys.setrecursionlimit(10 ** 6)
def find(e):
    if t[e] < 0:
        return e
    else:
        t[e] = find(t[e])
        return t[e]


def unite(a, b):
    a_root = find(a)
    b_root = find(b)
    if a_root == b_root:
        return
    t[a_root] += t[b_root]
    t[b_root] = a_root


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


def size(x):
    x = find(x)
    return -t[x]


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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
root=[-1]*n
def r(x):
  if root[x]<0:
    return x
  else:
    root[x]=r(root[x])
    return root[x]
def unite(x,y):
  x=r(x)
  y=r(y)
  if x==y:
    return
  root[x]+=root[y]
  root[y]=x
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  unite(a,b)
ans=0
for i in range(n):
  ans=max(ans,-root[i])
print(ans)

Submission status: Accepted

Solution code:
# Union Find
#0オリジン以下注意

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x, y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きい方がx
        if par[x] > par[y]:
            x, y = y, x
        par[x] += par[y] #ここで集合の個数を更新している
        par[y] = x
        return True
    
#xとyが同じ集合に含まれているかどうかを判定(同じ集合にあればTrue)
def same(x, y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size, 子なら親の頂点
n, m = map(int, input().split())
par = [-1]*n
for i in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
M = 0
for i in range(n):
    M = max(M, size(i))
print(M)

################以下にコードを書く
######2次元配列が与えられたら１次元に直す必要あり

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
grid = [set() for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    grid[u].add(v)
    grid[v].add(u)

cnt = 0
best = 0
visited = set()

import sys
sys.setrecursionlimit(1000000)

def dfs(x):
    global cnt
    if x in visited:
        return
    cnt += 1
    visited.add(x)
    for i in grid[x]:
        dfs(i)


for i in range(n):
    cnt = 0
    dfs(i)
    best = max(best, cnt)

print(best)

Submission status: Accepted

Solution code:
def INT():
    return int(input())

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

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

class UnionFind:
    def __init__(self, N):
        self.root = [_ for _ in range(N)]
        self.rank = [0] * N
        self.size = [1] * N
        
    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            #パス圧縮
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        else:
            if self.rank[x] > self.rank[y]:
                self.size[x] += self.size[y]
                self.root[y] = x
            else:
                self.size[y] += self.size[x]
                self.root[x] = y
                if self.rank[x] == self.rank[y]:
                    self.rank[y] += 1
            
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def getSizeOfSet(self, x):
        return self.size[self.find(x)]

import sys
sys.setrecursionlimit(10**9)

N, M = MI()
friend = UnionFind(N)

for _ in range(M):
    A, B = MI()
    friend.union(A - 1, B - 1)
    
ans = 0
for i in range(N):
    ans = max(ans, friend.getSizeOfSet(i))
    
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

p = []
sz = []

def find(x):
    if(p[x] == x):
        return x
    p[x] = find(p[x])
    return p[x]

def join(u, v):
    u = find(u)
    v = find(v)
    if(u == v):
        return

    if(sz[u] > sz[v]):
        u ^= v
        v ^= u
        u ^= v

    sz[v] += sz[u]
    p[u] = v

for i in range(n+1):
    p.append(i)
    sz.append(1)

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

mx = 0
for i in range(1, n+1):
    if(p[i] != i):
        continue
    mx = max(mx, sz[i])

print(mx)

Submission status: Accepted

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

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
        return self.root[x]

    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if (x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        #rnkが大きい方に結合
        elif (self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
        # rnkが同じ（深さに差がない場合）は1増やす
        if(self.rnk[x] == self.rnk[y]):
            self.rnk[y] += 1

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

uni=UnionFind(N)

for i 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.Count(i))

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0

    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)

    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1

    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)
for a,b in AB:
    a,b = a-1,b-1
    if uf.is_same(a,b): continue
    uf.unite(a,b)

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

Submission status: Accepted

Solution code:
#写経
#https://atcoder.jp/contests/abc177/submissions/16326133
# Union Find 木
from sys import setrecursionlimit, stdin
 
def find(parent, i):
    #print("f:" + str(i))
    #print(parent)
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t
 
def unite(parent, i, j):
    i = find(parent, i)
    #print("i:" + str(i) )
    j = find(parent, j)
    #print("j:" + str(j))
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j
    #print(parent)
 
readline = stdin.readline
setrecursionlimit(10 ** 6)

def resolve(): 
    N, M = map(int, readline().split())
    parent = [-1] * N
    for _ in range(M):
        A, B = map(lambda x: int(x) - 1, readline().split())
        unite(parent, A, B)
    print(-min(parent))

resolve()

Submission status: Accepted

Solution code:
def bfs(d,visit,i):
    q=[i]
    visit[i]=1
    count=1
    while(len(q)!=0):
        val=q.pop()
        for k in d[val]:
            if(visit[k]==0):
                count+=1
                visit[k]=1
                q.append(k)
    return count
    

n,m=map(int,input().split())
d=dict()
for i in range(1,n+1):
    d[i]=set()
for i in range(m):
    l,r=map(int,input().split())
    d[l].add(r)
    d[r].add(l)

visit=[0]*(n+1)

count=0
for i in range(1,n+1):
    if(visit[i]==0 and len(d[i])!=0):
        count=max(count,bfs(d,visit,i))
if(count==0):
    print(1)
else:
    print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
 
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
 
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
 
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
 
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
 
n, m = map(int, input().split())
uf = UnionFind(n)
 
for i in range(m):
    a, b = map(int, input().split())
    uf.Unite(a, b)
 
ans = 0
 
for i in range(n):
    ans = max(ans, uf.Count(i))
 
print(ans)

Submission status: Accepted

Solution code:
class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

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

M = 1
u = Unionfind(n+1)
for i in range(m):
    a,b = map(int,input().split())
    u.union(a,b)
    M = max(M,u.size(a))
print(M)

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

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

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 

        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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

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

ans = 0

for i in range(n):
    ans = max(ans, uf.Count(i))

print(ans)

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

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

    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 

        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

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)

ans = 0

for i in range(n):
    ans = max(ans, uf.Count(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)

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

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

uf = UnionFind(n)

for a,b in friends:
    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:
from sys import stdin
input = stdin.readline

class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parent = [-1]*n
    
    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

uf = Unionfind(N)
for i in range(M):
    a,b = map(lambda x: int(x) - 1, input().split())
    uf.union(a,b)
lis = uf.parent
print(-min(lis))

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)
result=[uf.size(i) for i in range(N)]
print(max(result))

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
import sys
sys.setrecursionlimit(1000000)

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = self.id

N, M = [int(i) for i in input().split()]
P = [Node(i) for i in range(N)]

def root(a):
    if a.id == a.parent:
        return a.id
    else:
        id = root(P[a.parent])
        a.parent = id
        return id

def union(a, b):
    p = root(a)
    q = root(b)
    if p == q:
        return
    else:
        P[q].parent = p

for i in range(M):
    A, B = [int(i)-1 for i in input().split()]
    union(P[A], P[B])

c = defaultdict(int)
for i in range(N):
    c[root(P[i])] += 1
    maxc = 0
for key in c.keys():
    if maxc < c[key]:
        maxc = c[key]
print(maxc)

Submission status: Accepted

Solution code:
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
#    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

def main():
    N, M = map( int, input().split())
    U = [ i for i in range(N)]
    AB = [ tuple( map( lambda x: int(x)-1, input().split())) for _ in range(M)]
    for a, b in AB:
        union(U, a, b)
    T = [0]*N
    for i in range(N):
        T[find(U, i)] += 1
    print(max(T))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def find(n):
    if parent[n] < 0:
        return n
    else:
        parent[n] = find(parent[n])
        return parent[n]


def union(x, y):
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y:
        return
    if parent[root_x] > parent[root_y]:
        root_x, root_y = root_y, root_x
    parent[root_x] += parent[root_y]
    parent[root_y] = root_x


def get_size(x):
    return -parent[find(x)]


n, m = map(int, input().split())
parent = [-1 for _ in range(n)]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
l=[]
par=[-1]*n
def root(x):
    if par[x]<0:
        return x
    else:
        par[x]=root(par[x])
        return par[x]

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:
        return
    if par[x]>par[y]:
        temp=x
        x=y
        y=temp
    par[x]+=par[y]
    par[y]=x
def size(x):
    x=root(x)
    return -par[x]
for a,b in l:
    unite(a,b)

for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    unite(x,y)
ans=max(map(size,range(n)))
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
AB = [list(map(int,input().split())) for x in range(M)]

parents = [-1]*(N+1)

def find(x):
    global parents
    if parents[x] < 0:
        return x
    else:
        return find(parents[x])

def union(x,y):#xにyを合体させる
    global parents
    X = find(x)
    Y = find(y)
    if X == Y:
        return
    if X > Y:
        X,Y = Y,X

    parents[X] += parents[Y]
    parents[Y] = X



for p in range(M):
    union(AB[p][0],AB[p][1])



print(min(parents)*-1)














"""
F = [[]]
L = []

for x in range(N+1):
    F += [[x+1]]

for p in range(M):
    F[AB[p][0]] += [AB[p][1]]
    F[AB[p][1]] += F[AB[p][0]]

for q in range(N+1):
    F[q] = list(set(F[q]))

for r in range(N+1):
    L += [len(F[r])]

print(L)
print(max(L))
"""