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:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        self.n_groups = N  # グループ数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる
        self.n_groups -= 1

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


N, M = ints()
uf = UnionFind(N)
for _ in range(M):
    a, b = mina(*ints())
    uf.unite(a, b)

# あとはなるべく別々になるように
# →サイズを1ずつ引いて1グループ
# いやmaxのsizeか

print(-min(uf.parent))

Submission status: Accepted

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

class UnionFind():
    def __init__(self,n): #n:要素数
        self.n=n
        self.parents = [-1]*n 
        #parents:各要素の親要素番号を格納
        #要素が根である場合、-(そのグループの要素数)を格納する
    
    def find(self,x): #xが属する根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y): #xのグループとyのグループを併合する
        x = self.find(x)
        y = self.find(y)
        
        if x==y:
            return
        
        if self.parents[x] > self.parents[y]: #|xのグループ|<|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)]

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

ans=0

for i in range(N):
    if uf.size(i) > ans:
        ans=uf.size(i)
        
print(ans)

Submission status: Accepted

Solution code:
class UFTree:
    def __init__(self, N):
        self.nodes = [Node(i) for i in range(N)]
        self.N = N

    def find_max_child_num(self):
        result = 0
        for i in range(self.N):
            result = max(result, self.nodes[i].child_num)
        return result

class Node:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None
        self.child_num = 0
        self.rank = 1

    def get_root(self):
        if self.parent is None:
            return self
        
        return self.parent.get_root()

    def concat(self, another):
        sr = self.get_root()
        ar = another.get_root()

        # is in a same tree.
        if sr.ID == ar.ID:
            return

        if sr.rank > ar.rank:
            parent, child = sr, ar
        else:
            parent, child = ar, sr

        parent.child_num += child.child_num + 1
        parent.rank = max(parent.rank, child.rank + 1)
        child.parent = parent

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

AB = []
for i in range(M):
    l = list(map(int, input().split()))
    AB.append(l)

for i in range(M):
    a, b = AB[i][0], AB[i][1]
    a -= 1;
    b -= 1;

    tree.nodes[a].concat(tree.nodes[b])

print(tree.find_max_child_num() + 1)

Submission status: Accepted

Solution code:
class UFTree:
    def __init__(self, N):
        self.nodes = [Node(i) for i in range(N)]
        self.N = N

    def find_max_child_num(self):
        result = 0
        for i in range(self.N):
            result = max(result, self.nodes[i].child_num)
        return result

class Node:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None
        self.child_num = 0
        self.rank = 1

    def get_root(self):
        if self.parent is None:
            return self
        
        return self.parent.get_root()

    def is_in_same_tree(self, another):
        return self.get_root().ID == another.get_root().ID

    def concat(self, another):
        if self.is_in_same_tree(another):
            return

        sr = self.get_root()
        ar = another.get_root()

        if sr.rank > ar.rank:
            parent, child = sr, ar
        else:
            parent, child = ar, sr

        parent.child_num += child.child_num + 1
        parent.rank = max(parent.rank, child.rank + 1)
        child.parent = parent

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

AB = []
for i in range(M):
    l = list(map(int, input().split()))
    AB.append(l)

for i in range(M):
    a, b = AB[i][0], AB[i][1]
    a -= 1;
    b -= 1;

    tree.nodes[a].concat(tree.nodes[b])

# # for debug
# for i in range(N):
#     n = tree.nodes[i]
#     if n.parent is None:
#         print(i + 1, "is root")
#     else:
#         print("parent of", i + 1, "is", n.parent.ID + 1)

print(tree.find_max_child_num() + 1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class UnionFind:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.parent = [-1 for i in range(size)]
        self.children = [[i] for i in range(size)]
    
    def Find(self, x):
        parent = self.parent[x]
        while parent >= 0:
            x = parent
            parent = self.parent[x]
        return x
    
    def Union(self, x, y):
        root_x = self.Find(x)
        root_y = self.Find(y)
        if root_x == root_y:
            return
        else:
            if self.rank[root_x] >= self.rank[root_y]:
                self.parent[root_x] += self.parent[root_y]
                self.parent[root_y] = root_x
                self.rank[root_x] = max(self.rank[root_y] + 1, self.rank[root_x])
                self.children[root_x] += self.children[root_y]
            else:
                self.parent[root_y] += self.parent[root_x]
                self.parent[root_x] = root_y
                self.rank[root_y] = max(self.rank[root_x] + 1, self.rank[root_y])
                self.children[root_y] += self.children[root_x]
    def Same(self, x, y):
        return self.Find(x) == self.Find(y)
    def FindRootAndSizeAndChildren(self):
        return [(idx, -val, self.children[idx]) for idx, val in enumerate(self.parent) if val<0 ]
    def print_lists(self):
        print(self.rank)
        print(self.parent)
        print()


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

max_size = 0
for idx, size, children in unionfind.FindRootAndSizeAndChildren():
    if size > max_size:
        max_size = size
print(max_size)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par = {i:i for i in range(1,n+1)}
        self.rank = {i:0 for i in range(1,n+1)}
        self.size = {i:1 for i in range(1,n+1)}

    def find(self,x):
        if x != self.par[x]:
            self.par[x] = self.find(self.par[x])
        return self.par[x]

    def union(self,x,y):
        px,py = self.find(x),self.find(y)
        res = 0
        if px != py:
            if self.rank[px] < self.rank[py]:
                self.par[px] = py
                self.size[py] += self.size[px]
                res = self.size[py]
            else:
                self.par[py] = px
                self.size[px] += self.size[py]
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1
                res = self.size[px]
        return res

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

Submission status: Accepted

Solution code:
def find(x):#xの親を見つける
  if par[x] < 0:
    return x
  else:
    par[x] = find(par[x])
    return par[x]

def unite(x,y):#要素xとｙを併合させる
  x,y=find(x),find(y)#xとyの親の検索
  if x!=y:#親が異なる場合併合させる
    if x>y:
        x,y=y,x#小さい方をxとする. これにより要素の値が小さいものを優先して木の根とする. 
    par[x]+=par[y] #値を無向木の要素数の和にする.
    par[y]=x #枝側は根の位置を格納

def same(x, y):#要素xと要素yが同じ無向木に所属しているかを判定する
  return find(x) == find(y)#同じ値を持つか否か

def size(x):#要素xが所属する無向木の大きさを返す
  return-par[find(x)]

par = [-1] * 200005#parは木の根の情報を持つ配列, xが根元ならpar[x]はその無向木に所属する要素の数を, そうでない場合は所属する根元のparにおける位置を示す数値が格納される. 


def main():
  n, m = map(int, input().split())
  for i in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)
  print(abs(min(par)))
  
if __name__ == "__main__":
  main()

Submission status: Accepted

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

def find(x):

    while par[x] != x:
        par[x] = par[par[x]]
        x = par[x]

    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    if x1 != y1:
        par[x1] = y1


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

s = [0 for i in range(n + 1)]

for k in range(n):
    s[find(k)] += 1


print(max(s))

Submission status: Accepted

Solution code:
### 解説AC ###
def root(x):
    if r[x] < 0:
        return x
    else:
        r[x] = root(r[x])
        return r[x]

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if r[x] > r[y]:
            x,y = y,x
        r[x] += r[y]
        r[y] = x

def size(x):
    return -r[root(x)]
 
n,m = map(int,input().split())
r = [-1] * n 
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,size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M=map(int,input().split())

class union_find():

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

    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.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def same(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x==y:
            return True
        else:
            return False

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

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

ans = 0
for i in range(N):
    tmp = G.count(i)
    ans = max(ans,tmp)

print(ans)

Submission status: Accepted

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

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


def size(x):
    return -r(x)


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

max_size = -min(root)
print(max_size)

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 unite(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 group_members(self):
        return [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+1)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x, y)

ans = 0
for i in range(n+1):
    if ans < uf.size(i):
        ans = uf.size(i)
print(ans)

Submission status: Accepted

Solution code:
import sys

#UnionFindTreeクラスの定義
class UnionFind():
    #クラスコンストラクタ
    #selfはインスタンス自身
    def __init__(self, n):
        #親ノードを-1に初期化する
        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]

    #xとyの木を併合する
    def union(self, x, y):
        #x,yの根をX,Yとする
        X = self.find(x)
        Y = self.find(y)

        #根が同じなら結合済み
        if X == Y:
            return

        #ノード数が多い方をXとする
        if self.parents[X] > self.parents[Y]:
            X, Y = Y, X

        #XにYのノード数を足す
        self.parents[X] += self.parents[Y]
        #Yの根をXとする
        self.parents[Y] = X


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

#UnionFindインスタンスの生成
uf = UnionFind(N)
for a, b in info:
    #インデックスを調整し、a,bの木を結合
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)

Submission status: Accepted

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


root = list(range(n + 1))


# from collections import defaultdict
# d = defaultdict(set)
cnt = [1] * (n + 1)


def find(i):
    if i == root[i]:
        return i
    root[i] = find(root[i])
    return root[i]

def union(u, v):
    fu, fv = find(u), find(v)
    if fu == fv:
        return
    root[max(fu, fv)] = min(fu, fv)
    cnt[min(fu, fv)] += cnt[max(fu, fv)]



for i in range(m):
    u, v = map(int, input().split())
    union(u, v)



# print(d)
print(max(cnt))

Submission status: Accepted

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


root = list(range(n + 1))


# from collections import defaultdict
# d = defaultdict(set)
cnt = [1] * (n + 1)


def find(i):
    if i == root[i]:
        return i
    root[i] = find(root[i])
    return root[i]

def union(u, v):
    fu, fv = find(u), find(v)
    if fu == fv:
        return
    cnt[min(fu, fv)] += cnt[max(fu, fv)]
    root[max(fu, fv)] = min(fu, fv)



for i in range(m):
    u, v = map(int, input().split())
    union(u, v)



# print(d)
print(max(cnt))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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 -self.parents[self.find(x)]

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return -self.parents[self.find(x)]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N+1)
    ans = 1
    if M == 0:
        print(ans)
        return

    for i in range(M):
        x, y = map(int, input().split())
        ans = max(uf.union(x,y), ans)
    print(ans)

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


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

uf = UnionFind(n+1)

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())

class Union_Find():

    def __init__(self,n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [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.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

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

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

    def cnt(self,x):
        return -self.root[self.find_root(x)]

G=Union_Find(N)
ans=0
for i in range(M):
    a,b=map(int,input().split())
    G.unite(a,b)

for i in range(1,N+1):
    ans = max(ans,G.cnt(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(uf.group_count()):
    ans = max(ans, uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
import collections
n, m = map(int, input().split())
par = list(range(2 * n))

# print(par)


# union find(parには0も入れているので、par[1]=1になる)
def find(x):

    while par[x] != x:
        tmp = par[x]
        par[x] = par[par[x]]
        x = par[x]

    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    if x1 != y1:
        par[x1] = y1


# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 5)]

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(n):
    s[find(k)] += 1

print(max(s))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
par=[i for i in range(N)]
size=[1 for i in range(N)]
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return  

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
path = [set() for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1].add(b-1)
    path[b-1].add(a-1)
visited = [0] * N

ans = 1
for u in range(N):
    if visited[u] == 1:
        continue
    curr = 1
    visited[u] = 1
    next_u = path[u]
    while next_u:
        v = next_u.pop()
        if visited[v] == 1:
            continue
        visited[v] = 1
        curr += 1
        for w in path[v]:
            if visited[w] == 0:
                next_u.add(w)
    ans = max(ans, curr)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

#graph = [[] for _ in range(n+1)]
graph = [set() for _ in range(n+1)]


for i in range(m):
    a, b = map(int, input().split())
#    graph[a].append(b)
#    graph[b].append(a)
    graph[a].add(b)
    graph[b].add(a)


dist = [-1] * (n+1)
dist[0] = 0


d = deque()
ans = 1
for j in range(len(dist)):
    if dist[j] != -1:
        continue
    d.append(j)
    cnt = 0
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            dist[i] = dist[v] + 1
            d.append(i)
            cnt = cnt + 1
    ans = max(ans,cnt)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    g = defaultdict(set)

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

    def dfs(u, visited: set):
        stack = [u]
        visited.add(u)
        while stack:
            u = stack.pop()
            for v in g[u]:
                if v not in visited:
                    stack.append(v)
                    visited.add(v)

    count = dict()       
    for u in range(N):
        if u in count:
            continue
        visited = set()
        dfs(u, visited)
        # print(visited)
        count[u] = len(visited)
        for v in visited:
            count[v] = len(visited)

    print(max(count.values()))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
class UnionFind(object):

    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


def main():
    N, M = map(int, input().split())

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

    ans = max(uf.get_size(i) for i in range(N))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


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

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

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

        if x == y:
            return

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

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


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

uf = UnionFind(N)
for a, b in info:
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

# uf = UnionFind(要素数)   で使用
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n     # 各要素の親要素の番号を格納するリスト 要素が根の場合は-(グループの要素数)を格納
    def find(self, x):              # 要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):          # 要素xが属するグループと、要素yが属するグループとを併合する
        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が同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)
    def members(self, x):           # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):                # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):          # グループの数を返す
        return len(self.roots())
    def all_group_members(self):    # {ルート要素: [そのグループに含まれる要素のリスト], ...} の辞書を返す
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M = map(int, input().split())
    A = [0] * M
    B = [0] * M
    for i in range(M):
        A[i], B[i] = map(int, input().split())

    uf = UnionFind(N + 1)
    for i in range(M):
        uf.union(A[i], B[i])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
	We can show that if u and v belong to the same connected component, then they are friends w/ each other
	So everyone in a given connected component is friends with one another
	So everyone in a given connected component must be separated into different groups

	If we have a CC of with sz nodes in it, then we need at least sz different groups

	So, the minimum number of groups needed is max sz(CC)
'''
import sys
sys.setrecursionlimit(2*10**5+5)

n, m = map(int,input().split())
adj = [[] for u in range(n+1)]
for i in range(m):
	u, v = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for u in range(n+1)]
def dfs(u):
	if vis[u]:
		return 0
	vis[u] = True

	sz = 1
	for v in adj[u]:
		sz += dfs(v)
	return sz

CCs = []
for u in range(1,n+1):
	if not vis[u]:
		CCs.append(dfs(u))

print(max(CCs))

Submission status: Accepted

Solution code:
'''
	We can show that if u and v belong to the same connected component, then they are friends w/ each other
	So everyone in a given connected component is friends with one another
	So everyone in a given connected component must be separated into different groups

	If we have a CC of with sz nodes in it, then we need at least sz different groups

	So, the minimum number of groups needed is max sz(CC)
'''
import sys
sys.setrecursionlimit(4*10**5)

n, m = map(int,input().split())
adj = [[] for u in range(n+1)]
for i in range(m):
	u, v = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for u in range(n+1)]
def dfs(u):
	if vis[u]:
		return 0
	vis[u] = True

	sz = 1
	for v in adj[u]:
		sz += dfs(v)
	return sz

CCs = []
for u in range(1,n+1):
	if not vis[u]:
		CCs.append(dfs(u))

print(max(CCs))