Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


def main():
    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 i in range(n):
        ans = max(uf.size(i),ans)
    print(ans)
    return 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from networkx import *
n,m = map(int, input().split())
if m == 0: print(1);exit()
G = Graph()
for i in range(m):
    a,b = map(int, input().split())
    G.add_edges_from([(a,b)])

print(len(max(connected_components(G), key=len)))

Submission status: Accepted

Solution code:

import copy
import sys
from collections import deque
N, M = map(int,input().split())
checked = [False for _ in range(N)]
path = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = list(map(lambda x: int(x)-1, s.split()))
    path[a].append(b)
    path[b].append(a)
dq = deque([[i,i] for i in range(N)])
friends = [[i] for i in range(N)]
while dq:
   i, num= dq.popleft()
   if checked[i]:
      continue
   checked[i] = True
   for j in range(len(path[i])):
      h = path[i][j]
      if not checked[h]:
         dq.appendleft([h, num])
         friends[num].append(h)
ans = 0
for i in range(N):
   f = set(friends[i])
   ans = max(ans, len(f))
print(ans)

Submission status: Accepted

Solution code:
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] #x(根)の要素にｙ(根)のグループの要素数をプラスする(要素の値は負の数で表される)
        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 relf.roots()}

    def __str__(self): #ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
        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
roots=uf.roots()

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

print(ans)

Submission status: Accepted

Solution code:
import sys,heapq
input = sys.stdin.buffer.readline

sys.setrecursionlimit(10**7)


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

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

#True:訪問済み False:未訪問
flag = [False]*n

def dfs(now):
    if flag[now]:
        return 0
    
    flag[now] = True

    size = 0
    for nxt in edge[now]:
        if not flag[nxt]:
            size += dfs(nxt)

    return size + 1

res = 0

for i in range(n):
    if flag[i]:
        continue
    res = max(res,dfs(i))

print(res)

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
    else:
        root[x] += root[y]
        root[y] = x


def size(x):
    x = r(x)
    # print(x)
    # print(root[x])
    return -root[x]


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

# print(root)
# max_size = max(map(size, range(N)))
max_size = 0
for i in range(N):
    max_size = max(size(i), max_size)
print(max_size)

Submission status: Accepted

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

    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 find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

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

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

Submission status: Accepted

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


class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    import sys
    input = sys.stdin.readline

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

    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1

        uf.merge_if_needs(ai, bi)

    ans = 0

    for j in range(n):
        ans = max(ans, uf.get_group_size(j))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
fr = [[] for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    fr[a-1].append(b-1)
    fr[b-1].append(a-1)
max_gr = 0
check = [False for _ in range(n)]
ans = 0

for per in range(n):
    if check[per]:
        continue

    else:
        tank = [per]
        count = 0
        while tank:
            now = tank.pop()
            if check[now]:
                continue
            else:
                check[now] = True
                count += 1
                for j in fr[now]:
                    if not check[j]:
                        tank.append(j)

        ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
par = [0]*(n+1)
group = [1]*(n+1)
for i in range(1,n+1): par[i]=i
def root(x):
  if par[x]==x: return x
  return root(par[x])

def union(x,y):
  rx = root(x)
  ry = root(y)
  if rx==ry: return
  par[max(rx,ry)] = min(rx,ry)
  group[min(rx,ry)] += group[max(rx,ry)]

for _ in range(m):
  f1,f2 = map(int, input().split())
  union(f1,f2)
print(max(group))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
friends = [set() for i in range(n)]


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)


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

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

print(max(ans))

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
friends = [set() for i in range(n)]


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)
    return


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

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

print(max(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)
    return


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

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

print(max(ans))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.num = [1] * (n+1)#集合の要素の数
 
    # 検索
    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.num[y]+=self.num[x]
        else:
            self.par[y] = x
            self.num[x]+=self.num[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

n, m = map(int, input().split())
f = [list(map(int, input().split())) for i in range(m)]

uf = UnionFind(n)
  
for i in range(m):
  a, b = f[i]
  if not uf.same_check(a, b):
    uf.union(a, b)
    
print(max(uf.num))

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 main():
    n, m = map(int,input().split())
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,input().split())
        uf.union(a-1,b-1)
    print(-min(list(uf.parents)))
    
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

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

uf = UnionFind(n)

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

for a,b in ab:
    uf.union(a-1,b-1)

ans = -1
for i in uf.parents:
    ans = min(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())
u = UnionFind(n)

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

result = 0
for i in range(n): 
	result = max(result, u.size(i))

print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n,m=map(int,input().split())
root=[-1]*(n+1)
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
    if x>y:
        x,y=y,x

    root[x]+=root[y]
    root[y]=x
def size(x):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())

    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i+1))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
root=[-1]*(n+1)
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
    if x>y:
        x,y=y,x

    root[x]+=root[y]
    root[y]=x
def size(x):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())

    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i+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)]


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

ARR = []

for i in range(M):
    ARR.append(list(map(int,input().split())))

def calculate(n,m,arr):
    unionFind = UnionFind(n)

    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1
        unionFind.union(startNode, endNode)

    result = 0
    for i in range(n):
        result = max(result,unionFind.size(i))
    print(result)



calculate(N,M,ARR)

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
roots = uf.roots()
cnt = []
for r in roots:
    cnt.append(uf.size(r))
cnt.sort(reverse=True)
ans = cnt[0]
print(ans)

Submission status: Accepted

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

for i in range(m):
  a, b = map(int, input().split())
  if a in edges:
    edges[a].append(b)
  else:
    edges[a] = [b]
  if b in edges:
    edges[b].append(a)
  else:
    edges[b] = [a]
    
g = [-1 for i in range(n+1)]

from queue import Queue
ans = 1
for i in range(1, n+1):
  if g[i] != -1:
    continue
  if not i in edges:
    continue
  q = Queue()
  q.put(i)
  g[i] = 0
  tmp = 1
  while not q.empty():
    p = q.get()
    for edge in edges[p]:
      if g[edge] == -1:
        g[edge] = 0
        q.put(edge)
        tmp += 1
  ans = max(tmp, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1<<30)
input = sys.stdin.readline
N, M = map(int, input().split())

e = [-1] * N

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

def join(a, b):
	a, b = find(a), find(b)
	if a == b: return
	if e[a] > e[b]: a, b = b, a
	e[a] += e[b]
	e[b] = a

for _ in range(M):
	x, y = map(int, input().split())
	join(x-1, y-1)

print(-min(e))

Submission status: Accepted

Solution code:
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())

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

    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)]
    
u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])
    
ans = 1
for i in range(1, N+1):
    ans = max(ans, u.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)]

n, m = map(int, input().split())
UF = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    UF.union(a, b)

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

Submission status: Accepted

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

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

  def union(self, u,v):
    p1,p2 = self.find(u),self.find(v)
    if p1==p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def same(self, u,v):
    return self.find(u) == self.find(v)

  def weight(self, u):
    p = self.find(u)
    return -self.parents[p]

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

print(max([ abs(u) for u in uf.parents if u<0 ]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
root=[-1]*(n+1)
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
    if root[x]>root[y]:
        x,y=y,x

    root[x]+=root[y]
    root[y]=x
def size(x):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())

    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i+1))
print(ans)

Submission status: Accepted

Solution code:
p = [i for i in range(200001)]
r = [1 for i in range(200001)]
ans = [1 for i in range(200001)]

def fs(a):
    if p[a] == a: return a
    p[a] = fs(p[a])
    return p[a]

def js(a, b):
    a = fs(a)
    b = fs(b)
    if a == b: return
    if r[a] > r[b]:
        p[b] = a
        ans[a] += ans[b]
    elif r[b] > r[a]:
        p[a] = b
        ans[b] += ans[a]
    else:
        p[b] = a
        ans[a] += ans[b]
        r[a] += 1

n, k = map(int,input().split())
for i in range(k):
    a, b = map(int,input().split())
    js(a, b)

ans1 = 0
for i in range(1, n+1):
    ans1 = max(ans1, ans[fs(i)])

print (ans1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
root=[-1]*(n+1)
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):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())

    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i+1))
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):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i))
print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m=map(int,input().split())
    uf=UnionFind(n)
    for a,b in (map(lambda x: int(x)-1, input().split()) for _ in range(m)):
        uf.union(a,b)
    print(max((uf.size(x) for x in uf.roots())))

class UnionFind():
    '''Union-Find'''
    
    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 is_same(self, x, y) -> bool:
        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 get_root(num):
    if num == root[num]:
        return num
    else:
        root[num] = get_root(root[num])
        return root[num]


def is_same_group(a,b):
    return get_root(a) == get_root(b)


def unite(x,y):
    root_x = get_root(x)
    root_y = get_root(y)

    if root_x == root_y:
        return

    if height[x] > height[y]:

        size[root_x] += size[root_y]
        root[root_y] = root_x 

    elif height[x] < height[y]:

        size[root_y] += size[root_x]
        root[root_x] = root_y

    else:
        size[root_x] += size[root_y]
        root[root_y] = root_x
        height[x] += 1



V,E = map(int,input().split())

root = list(range(V+1))
height = [0]*(V+1)
size = [1]*(V+1)

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

print(max(size))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[]
data=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  ab.append([a,b])
  data[a].append(b)
  data[b].append(a)
flag=[0]*(n+1)
cnt=[0]*(n+1)
for i in range(1, n+1):
  if flag[i]==0:
    cnt[i]+=1
    flag[i]=1
    que=[i]
    while que:
      h=que.pop()
      for u in data[h]:
        if flag[u]==0:
          cnt[i]+=1
          flag[u]=1
          que.append(u)   
print(max(cnt))

Submission status: Accepted

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

#UnionFind木を使う

p = [-1] * N

def find(x):
    #print(x)
    if p[x] < 0:
        return x
    else:
        p[x] = find(p[x])
        return p[x]

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

    if x == y:
        return
    p[y] += p[x] #木のサイズをマイナスの方向に増やして記録していく
    p[x] = y
    return

def size(x):
    return -p[p[x]]

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

    union(a, b)

#print(p)
# xが子の場合，p[x] = 親（根，root）
# xが親の場合，p[x] = -1 * 木のサイズ

ans = max(map(size, range(N)))

print(ans)