Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
uf=UnionFind(n+1)
for _ 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.parent = [-1] * n

    def find(self, s):
        if self.parent[s] < 0:
            return s
        self.parent[s] = self.find(self.parent[s])
        return self.parent[s]

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

def search(x, num):
    nodes.remove(x)
#     for y in edge[x]:
    for y in list(edge[x]):
        edge[y].remove(x)
        if y in nodes:
            num = search(y, num)
    return num + 1

(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x in nodes:
        ans = max(ans, search(x, 0))
print(ans)

Submission status: Accepted

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

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

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 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

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

uf1=UnionFind(n)
for i in range(m):
    a,b=map(int, input().split()) #a,b:つながっている辺
    uf1.union(a-1,b-1)

for i in range(n):
    uf1.find(i)
from collections import Counter
c=Counter(uf1.par)
print(max(c.values()))

Submission status: Accepted

Solution code:
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


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

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


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 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 = LI()
    uf = UnionFind(n)
    for i in range(m):
        a, b = LI()
        uf.unite(a - 1, b - 1)
    ans = 0

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


if __name__ == "__main__":
    main()

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 -1 * root[r(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, size(i))
 
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

def search(x, num):
    nodes.remove(x)
    for y in edge[x]:
        edge[y].discard(x)
    for y in list(edge[x]):
        if y in nodes:
            num = search(y, num)
    return num + 1

(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x in nodes:
        ans = max(ans, search(x, 0))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e6))

def search(x, num):
    nodes.remove(x)
#     for y in edge[x]:
#         edge[y].discard(x)
#     for y in list(edge[x]):
    for y in edge[x]:
        if y in nodes:
            num = search(y, num)
    return num + 1

(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x in nodes:
        ans = max(ans, search(x, 0))
print(ans)

Submission status: Accepted

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

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

lis = [[] for _ in range(N+1)]
for i in range(M):
    A,B = map(int,input().split())
    lis[A].append(B)
    lis[B].append(A)
    
cnt = 0
seen = [False]*(N+1)
def dfs(v,graph):
    global cnt
    seen[v] = True
    for next_v in graph[v]:
        if seen[next_v] == True:
             continue
        if seen[next_v] == []:
             continue
        cnt += 1
        dfs(next_v,graph)
    return cnt

ma = 0
for j in range(N):
    cnt = 0
    if seen[j] == True:
        continue
    ma = max(ma,dfs(j,lis))
print(ma+1)

Submission status: Accepted

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

    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):
        x = self.root(x)
        y = self.root(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

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

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.unite(a, b)

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

print(str(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)

def li():
    return [int(x) for x in 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):
        root = self.find(x)
        return -self.parents[root]

    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 = li()
uf = UnionFind(N)
for i in range(M):
    a, b = li()
    uf.union(a-1, b-1)

ans = max(uf.size(x) for x in range(N))
print(ans)

Submission status: Accepted

Solution code:
import queue
import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
readline = sys.stdin.readline


class UnionFind():
    def __init__(self, n=0):
        # 負なら根、非負なら親IDの情報を持たせる。負の値の絶対値で連結成分のサイズを表す（-2なら連結成分サイズ2の根）
        self.d = [-1]*n

    def find(self, x):
        """
        根のIDを返す
        """
        if self.d[x] < 0:
            return x  # 今の頂点が根なら頂点番号を返す
        # 今の頂点が根でないなら親についてfindクエリを投げる. d[x] = find(d[x])で経路縮約できる
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        """
        根同士をくっつける
        """
        x = self.find(x)
        y = self.find(y)  # 根同士をくっつける
        if x == y:
            return False  # 根が同じなら何もする必要はない。Falseを返しているのは、くっつけられたかどうかを返した方が便利なときがあるから（MSTなど）
        if self.d[x] > self.d[y]:
            x, y = y, x  # 小さい方の部分木を大きい方の部分木にくっつけるためにswap。dがマイナスなので不等号が逆になる点に注意
        self.d[x] += self.d[y]  # 連結成分サイズを更新
        self.d[y] = x  # 根をyからxに張り替える
        return True

    def same(self, x, y):
        """
        同じ集合に所属しているかどうか
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        連結成分サイズを返す
        """
        return -self.d[self.find(x)]


uf = UnionFind(n)

for _ in range(m):
    a, b = [int(i) for i in readline().split()]
    a -= 1
    b -= 1
    uf.unite(a, b)

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

lsloop = []
used = [False for i in range(n+1)]

for j in range(1,n+1):
    if used[j]:
        continue        
    ii = 1
    d = deque()
    d.append(j)
    used[j] = True
    while d:
        v = d.popleft()
        for i in graph[v]:
            if used[i]:
                continue
            ii += 1
            d.append(i)
            used[i] = True
    lsloop.append(ii)
print(max(lsloop))

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
rinsetu = [set() for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, (input().split()))
    rinsetu[a].add(b)
    rinsetu[b].add(a)

grp = 0
color = ["white"] * (N + 1)
color_2 = ["white"] * (N + 1)
color[0] = "black"
for i in range(1, N + 1):
    count=1
    if color[i] == "white":
        d = deque()
        d.append(i)
        a = set()
        a.add(i)
        while (d):
            k = d.popleft()
            color[k] = "black"
            color_2[k]="black"
            for j in rinsetu[k]:
                if color[j] == "white" and color_2[j]=="white":
                    color_2[j]="black"
                    d.append(j)
                    count+=1
        grp=max(grp,count)
print(grp)

Submission status: Accepted

Solution code:
class UFTree():
  def __init__(self,n):
    self.N = n
    self.parents = [-1]*n
    
  def root(self,n):
    if self.parents[n]<0: return n
    else:
      self.parents[n] = self.root(self.parents[n])
      return self.parents[n]
      
  def unite(self,x,y):
    rx,ry = self.root(x), self.root(y)
    if rx==ry: return
    if rx>ry: rx,ry = ry,rx
    self.parents[rx] += self.parents[ry]
    self.parents[ry] = rx
      
  def size(self,x):
    return -self.parents[self.root(x)]
  
N,M = map(int,input().split())
uft = UFTree(N)
for i in range(M):
  A,B = map(int,input().split())
  uft.unite(A-1,B-1)
print(max([uft.size(i) for i in range(N)]))

Submission status: Accepted

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

def main():
    #xの根を求める
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #xとyの属する集合の併合
    def unite(x,y):
        x = find(x)
        y = find(y)

        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

    #xとyが同じ集合に属するかの判定
    def same(x,y):
        return find(x) == find(y)

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def find_root(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))


def solve(SOLVE_PARAMS):
    pass


def main():
    global parent, rank
    # parse input
    N, M = map(int, input().split())
    parent = [-1] * N
    rank = [0] * N
    for q in range(M):
        a, b = map(int, input().split())
        unite(a - 1, b - 1)

    xs = list(find_root(x) for x in range(N))
    # debug(": xs", xs)
    # print(len(set(xs)))
    from collections import Counter
    print(max(Counter(xs).values()))


# tests
T1 = """
5 3
1 2
3 4
5 1
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
3
"""

T2 = """
4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
4
"""

T3 = """
10 4
3 1
4 1
5 9
2 6
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
3
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)

N, M = map(int, input().split())
UF = [-1] * (N+1)
def find(x):
    global UF
    if UF[x] == -1:
        return x
    else:
        UF[x] = find(UF[x])
        return UF[x]
def union(x,y):
    global UF
    xx = find(x)
    yy = find(y)
    if UF[x] == UF[y] == -1:
        UF[y] = xx
        return
    elif xx == yy:
        return 
    else:
        UF[yy] = xx
        return 
    
for _ in range(M):
    x, y = map(int, input().split())
    union(x,y)
    
cnt = [0] * (N+1)
for i in range(1,N+1):
    z = find(i)
    cnt[z] += 1

print(max(cnt))

Submission status: Accepted

Solution code:
import sys

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents=[-1 for _ in range(n)]
    
    def find(self,n):
        x=self.parents[n]
        if x<0:
            return n
        else:
            self.parents[n]=self.find(self.parents[n])
            return self.parents[n]
    
    def union(self,n,m):
        x=self.find(n)
        y=self.find(m)
        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

sys.setrecursionlimit(10**9)    
n,m=map(int,input().split())
uf=UnionFind(n)

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

ans=0

for p in uf.parents:
    ans=min(ans,p)

print(abs(ans))

Submission status: Accepted

Solution code:
class union_find:
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]
    
  def root(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
      
  def same(self, x, y):
    return self.par[x] == self.par[y]
        
  def unite(self, x, y):
    x, y = self.root(x), self.root(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        self.par[x] = y
      else:
        self.par[y] = x
        if self.rank[x] == self.rank[y]:
          self.rank[x] += 1

N, M = map(int, input().split())
uf = union_find(N)
for i in range(M):
  a, b = map(int, input().split())
  uf.unite(a-1, b-1)
for i in range(N):
  uf.par[i] = uf.root(i)
D = {}
L = [uf.par[i] for i in range(N)]
for i in range(N):
  if L[i] in D:
    D[L[i]] += 1
  else:
    D[L[i]] = 1
print(max(D[i] for i in D))

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 -1 * root[r(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, size(i))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in 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 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.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)


from collections import Counter
N, M = map(int, input().split())
uf = UnionFind(N)
s = set()
for i in range(M):
    a, b = sorted(map(int, input().split()))
    a -= 1; b -= 1
    if (a, b) in s:
        continue
    s.add((a, b))
    uf.union(a, b)

for i in range(N):
    uf.find(i)

g = [uf.find(i) for i in range(N)]
ans = max(Counter(g).values())
print(ans)

Submission status: Accepted

Solution code:
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:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True
        
def size(x):
    return -par[find(x)]
    
n,m = map(int,input().split())

l =[[] for _ in range(n)]
par = [-1]*n

for i in range(m):
    a,b = map(int,input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)
    unite(a-1,b-1)
    
ans = 0    
for i in range(n):
    ans = max(ans,size(i))
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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


par = [i for i in range(N+1)] #親＝グループ
size = [1 for _ in range(N+1)] #そのグループに属する要素数

def find(x): #親＝グループを出力
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y): #True or False
    return find(x) == find(y)
def unite(x,y): #2グループをまとめる，サイズ管理
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0

for AB in ABs:
    unite(AB[0],AB[1])

print(max(size))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
groups = [x for x in range(n)]
count = [0]*n

def UnionFind(x):
    a = x
    while a != groups[a]:
        a = groups[a]
    groups[x] = a
    return a

for _ in range(m):
    x, y = map(int, input().split())
    x, y = UnionFind(x-1), UnionFind(y-1)
    if x != y:
        groups[y] = x
    
for i in range(n):
    count[UnionFind(i)] += 1
print(max(count))

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
seen=[False]*n
num=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    num[a-1].append(b)
    num[b-1].append(a)
ans=0
for i in range(n):
    if seen[i]==False:
        queue=deque()
        queue.append(i)
        cnt=1
        yn=0
        while yn!=1:
            if len(queue)!=0:
                num01=queue.popleft()
            else:
                yn=1
            seen[num01]=True
            for j in range(len(num[num01])):
                num10=num[num01][j]-1
                if seen[num10]==False:
                    seen[num10]=True
                    cnt+=1
                    queue.append(num10)
        ans=max(ans,cnt)
print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

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

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():

    def __init__(self, n):
        # n個の要素
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        要素xのrootを見つける
        """
        if self.parents[x] < 0:
            return x
        else:
            # 再帰的にrootを求める
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        """
        要素x,要素yについて
        rootが同じ場合そのまま
        異なる場合は要素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のrootが同じか返す
        """
        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 __str__(self):
        return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))


# N人でM個の情報
N, M = map(int, input().split())
# AとBは友達であるという情報がM個
A_B = [list(map(int, input().split())) for _ in range(M)]
union = UnionFind(N)

for a, b in A_B:
    union.unite(a-1, b-1)
ans = 0
for i in range(N):
    ans = max(ans, union.size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys


def main():

    input = sys.stdin.readline

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

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

    UF = UnionFind(N)

    for i in range(M):
        A,B = AB[i]

        A = A - 1
        B = B - 1

        UF.union(A,B)


    ans = 1
    for i in range(N):
        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:
def resolve():
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

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

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

            if x == y:
                return

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

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

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

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

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

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

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

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

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

    n, m = map(int, input().split())
    s = [j for j in range(n)]
    uf=UnionFind(n)
    for _ 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)
resolve()