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:
n, m = map(int, input().split())

class UnionFind:
    def __init__(self, n):
        self.pare = [-1] * n
        self.size = [1] * n
    def root(self, x):
        if self.pare[x] < 0:
            return x
        r = self.root(self.pare[x])
        self.pare[x] = r
        return r
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        self.pare[rx] = ry
        self.size[ry] += self.size[rx]
        return

uf = UnionFind(n)

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

print(max(uf.size))

Submission status: Accepted

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

N, M = map(int, input().split())
edges = {}
for _ in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if a not in edges:
    edges[a] = set()
  if b not in edges:
    edges[b] = set()
  edges[a].add(b)
  edges[b].add(a)

to_check = set(range(N))
max_size = 0
while to_check:
  checked = set()
  s = set()
  s.add(next(iter(to_check)))
  #print(s)
  while s:
    current = s.pop()
    checked.add(current)
    if current in edges:
      for n in edges[current]:
        if n not in checked:
          s.add(n)
  max_size = max(max_size, len(checked))
  #print(checked)
  for c in checked:
    to_check.remove(c)
print(max_size)

Submission status: Accepted

Solution code:
# UnionFind: https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        
    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 False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]

n, m = map(int, input().split())
friends = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    friends.unite(a, b)
print(max(friends.size(i) for i in range(n)))

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:
            li = []
            while self.parents[x] >= 0:
                li.append(x)
                x = self.parents[x]
            for y in li:
                self.parents[y] = x
            return 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())

import sys
input = sys.stdin.buffer.readline
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 uf.roots():
    ans = max(uf.size(i),ans)
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())

import sys
input = sys.stdin.buffer.readline
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 uf.roots():
    ans = max(uf.size(i),ans)
print(ans)

Submission status: Accepted

Solution code:
# input here
_INPUT = """\
5 3
1 2
3 4
5 1
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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



def main():
    n, m = map(int, input().split())
    xy = [list(map(int, input().split())) for i in range(m)]

    uf = UnionFind(n)

    for i in range(len(xy)):
        uf.union(xy[i][0]-1,xy[i][1]-1)
    
    print(-(min(uf.parents)))

    
    
    

            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Accepted

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

#Union-Find木
#par[i]:iの親　deep[i]:iの深さ　size[i]:iの大きさ
par=[i for i in range(n)]
deep=[1]*n
size=[1]*n

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

#二つのグループを統合する
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)


for i in range(m):
  a,b=map(int,input().split())
  unite(a-1,b-1)
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 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())
 
nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
 
ans = 1
 
uf = UnionFind(n)
for i in range(m):
    friends = list(map(int, input().split()))
    uf.union(friends[0]-1,friends[1]-1)
    if ans < uf.size(friends[1]-1):
        ans = uf.size(friends[1]-1)
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())
U=UnionFind(N)
for m in range(M):
  a,b=map(int,input().split())
  U.union(a-1,b-1)
ans=0
for i in U.roots():
  ans=max(ans,U.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)

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def 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 isSame(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    N,M = map(int,input().split())
    uf = UnionFind(N)
    for _ 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(ans)
        
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    G = collections.defaultdict(set)
    for _ in range(M):
        A, B = LI_()
        G[A].add(B)
        G[B].add(A)
    # print(G)

    # 連結成分をすべてバラバラにできればよい→最大の連結成分がわかればよい
    visited = [False] * N
    def dfs(c, cnt):
        visited[c] = True
        cnt[0] += 1
        for n in G[c]:
            if not visited[n]:
                dfs(n, cnt)

    ans = 0
    for i in range(N):
        cnt = [0]
        dfs(i, cnt)
        ans = max(cnt[0], ans)

    print(ans)

if __name__ == '__main__':
    resolve()

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())
A=[]
B=[]
for i in range(M):
    n,a=input().split()
    A.append(int(n))
    B.append(int(a))
uf = UnionFind(N)
for i in range(len(A)):
    uf.union(A[i]-1,B[i]-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):
        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())
ab = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    x, y = ab[i][0], ab[i][1]
    x -= 1
    y -= 1
    uf.union(x, y)
ans = 0
for i in range(n):
    ans = max(uf.size(i), ans)
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)

ans = 0
for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)

for i in range(uf.group_count()):
    if ans < uf.size(i):
        ans = uf.size(i)
print(ans)

Submission status: Accepted

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

class UnionFind():
    def __init__(self, N):
        self.N = N
        self.r = [-1] * (N+1)

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

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

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

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

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        A, B = map(lambda i: int(i)-1, input().split())
        uf.unite(A, B)

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

    print(ans)

main()

Submission status: Accepted

Solution code:
def find(x):
    if par[x]==x:
        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 0
    if x<y:x,y=y,x    
    par[x]=y
n,m=map(int,input().split())
par=[i for i in range(n+1)]
for _ in range(m):
    i,j=map(int,input().split())
    unite(i,j)
ans=[0]*(n+1)
for i in range(n+1):
    find(i)
for i in par:
    ans[i]+=1
print(max(ans))

Submission status: Accepted

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

class UnionFind:

    def __init__(self, n: int) -> None:
        self.p = [-1] * n
        self.r = [1] * n

    def find(self, x: int) -> int:
        if(self.p[x] == -1): return x
        self.p[x] = self.find(self.p[x])
        
        return self.p[x]

    def unite(self, x: int, y: int) -> None:
        x = self.find(x)
        y = self.find(y)
        if(x == y): return
        if(self.r[x] > self.r[y]): x, y = y, x
        if(self.r[x] == self.r[y]): self.r[y] += 1

        self.p[x] = y
    
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    
    

def main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        
        uf.unite(a, b)
    
    group = {}

    res = 0
    for i in range(n):
        g = uf.find(i)
        
        if(group.get(g) is None): group[g] = 1
        else: group[g] += 1

        res = max(res, group[g])
    
    print(res)

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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())    
uf = UnionFind(N)

for i in range(M):
    A,B = map(lambda x:int(x)-1,input().split())
    uf.union(A,B)
    #print(uf.parents)

print(abs(min(uf.parents)))

Submission status: Accepted

Solution code:
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

class UnionFind():
	"""docstring for 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
		# print(self.parents)

		
n,m=input2()
S=[input_array() for _ in range(m)]

uf=UnionFind(n) #uf.parents==[-1]*n

for s in S:
	uf.union(s[0]-1,s[1]-1)
ans=min(uf.parents)

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

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

print(max([u.size(i) for i in range(N)]))

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n, m = map(int, input().split())
    E = [[] for _ in range(n)]

    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)


    cnt = 0
    color = [-1] * n
    def dfs(v):
        if color[v] != -1:
            return False
        color[v] = cnt
        queue = [v]
        for v in queue:
            for nv in E[v]:
                if color[nv] == -1:
                    color[nv] = cnt
                    queue.append(nv)
        return True

    for v in range(n):
        cnt += dfs(v)

    print(Counter(color).most_common()[0][1])
resolve()

Submission status: Accepted

Solution code:
def root(x, root_ls):
  if root_ls[x] < 0:
    return x
  else:
    root_ls[x] = root(root_ls[x], root_ls)
    return root_ls[x]

def unite(a, b, root_ls):
  a = root(a, root_ls)
  b = root(b, root_ls)
  if a != b:
    root_ls[a] += root_ls[b]
    root_ls[b] = a
  
n, m = list(map(int, input().rstrip().split(" ")))
members = [-1 for i in range(n)]
max_idx = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  unite(a-1, b-1, members)
print(max([-m for m in members]))

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:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n, m = map(int, input().split())
    E = [[] for _ in range(n)]

    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)


    cnt = 0
    color = [-1] * n
    def dfs(v):
        if color[v] != -1:
            return False
        color[v] = cnt
        queue = [v]
        for v in queue:
            for nv in E[v]:
                if color[nv] == -1:
                    color[nv] = cnt
                    queue.append(nv)
        return True

    for v in range(n):
        cnt += dfs(v)

    for key, val in Counter(color).most_common():
        print(val)
        return
resolve()

Submission status: Accepted

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10000000)

class UnionFind:
    def __init__(self, N: int) -> None:
        #自身が親なら、その集合に属する頂点数に-1をかけたもの
        #自身が親でないなら、自身の親
        self.par = [-1 for i in range(N)]
    
    def root(self, x: int) -> bool:
        if self.par[x] < 0: #親が自分自身なら頂点
            return x
        else:
            #経路圧縮してから返す
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        else:
            if rx > ry:
                rx, ry = ry, rx
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)
    
    def size(self, x: int) -> int:
        root = self.root(x)
        return -self.par[root]


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ 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.size(i))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

P=[-1]*n

def find(x):
  if P[x]<0:
    return x
  P[x]=find(P[x])
  return P[x]

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return

  if P[x]>P[y]:
    P[y]+=P[x]
    P[x]=y
  else:
    P[x]+=P[y]
    P[y]=x

def size(x):
  return -P[find(x)]

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

print(-min(P))

Submission status: Accepted

Solution code:
class Union:
    def __init__(self, number):
        self.__number = number
        self.parentList = [-1] * number
 
    def getNumber(self):
        return self.__number 

    def getRoot(self, index):
        if self.parentList[index] < 0:
            return index
        root = self.getRoot(self.parentList[index])
        self.parentList[index] = root
        return root
      
    def unite(self, i, j):
        i = self.getRoot(i)
        j = self.getRoot(j)
        if i != j:
            if i > j:
                i, j = j, i
            self.parentList[i] += self.parentList[j]
            self.parentList[j] = i
 
    def getSize(self, i):
        return -self.parentList[self.getRoot(i)]
 
n, m = map(int, input().split())
 
friendUnion = Union(n)
for i in range(m):
  a, b = map(int, input().split())
  friendUnion.unite(a-1, b-1)
 
unionSizes = [friendUnion.getSize(i) for i in range(friendUnion.getNumber())]
print(max(unionSizes))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.r = [-1] * n
    
    def root(self, x):
        if self.r[x] < 0:
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]

    def merge(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.r[x] > self.r[y]:
            x, y = y, x
        self.r[x] += self.r[y]
        self.r[y] = x
        return True

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


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

for _ in range(M):
    A, B = map(lambda x: int(x)-1, input().split())
    uf.merge(A, B)

print(max([uf.size(i) for i in range(N)]))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

out=0
for i in range(M):
    a,b = list(map(int,input().split()))
    Network.union(a-1,b-1)
print(-1*min(Network.parents))