Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

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

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

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

    # 検索
    def find(self, x):
        if self.par[x]<0:
            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:
            return
        d1=self.par[x]
        d2=self.par[y]
        if d1<=d2:
            self.par[y]=x
            self.sizes[x]=self.sizes[x]+self.sizes[y]
            if d1==d2:
                self.par[x]=self.par[x]-1
        else:
            self.par[x]=y
            self.sizes[y]=self.sizes[x]+self.sizes[y]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    #サイズ
    def size(self,x):
        return self.sizes[self.find(x)]

    #木の数
    def number(self):
        count=0
        for i in self.par[1:]:
            if i<0:
                count=count+1
        return count

U=UnionFind(n)
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    if not U.same_check(a,b):
        U.union(a,b)

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

Submission status: Accepted

Solution code:
LI = lambda: list(map(int, input().split()))

N, M = LI()
AB = [LI() for _ in range(M)]


class Node:

    def __init__(self, num):
        self.num = num
        self.parent = None

    def root(self):
        if self.parent is None:
            return self
        self.parent = self.parent.root()
        return self.parent


class UnionFind:

    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]
        self.groups = {i: 1 for i in range(n)}
    
    def unite(self, x, y):
        x = self.nodes[x].root().num
        y = self.nodes[y].root().num
        if x == y:
            return
        if self.groups[x] < self.groups[y]:
            x, y = y, x
        self.groups[x] += self.groups[y]
        del self.groups[y]
        self.nodes[y].parent = self.nodes[x]
    
    def same(self, x, y):
        a = self.nodes[x].root()
        b = self.nodes[y].root()
        return True if a == b else False


def main():
    uf = UnionFind(N)
    for a, b in AB:
        uf.unite(a - 1, b - 1)
    ans = max(uf.groups.values())
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        """
        x: child
        ret-> node
        xのグループの代表を見つける
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        union (x ,y)
        x,y: node
        ret->None
        """
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        """
        return true if x and y are in same group
        """
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        """
        return size of the group x belong to
        """
        return self.size[self.find(x)]

    def is_connected(self):
        """
        return true is all node is in one group
        """
        return self.connectedNum(0) == len(self.parent)

    def conpomentNum(self):
        """
        return num of component
        """
        par_set=set()
        for p in self.parent:
            par_set.add(self.find(p))
        return len(par_set())


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

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

max_size=max(Un.connectedNum(i) for i in range(N))
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):
        '''
        注意：0-idx
        '''
        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):
        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])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):                                      # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)                                        # xをxの根に置き換える
        y = self.find(y)                                        # yをyの根に置き換える

        if x == y:                                              # 根が同じなら置き換える必要なし
            return

        if self.parents[x] > self.parents[y]:                   # 子がたくさんある方を x とする（出来るだけ浅い木にするため）
            x, y = y, x

        self.parents[x] += self.parents[y]                      # xの子の数を更新
        self.parents[y] = x                                     # yの親を更新

    def same(self, x, y):                                       # xとyが同じ根の子かを判定
        return self.find(x) == self.find(y)

    def size(self, x):                                          # xの根のparent（= 要素数）を返す
        return -self.parents[self.find(x)]

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

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

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

    def all_group_members(self):                                # {根:[根の子のリスト],...}を辞書で返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):                                          # print(self) での返し方を定義
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


##############################################################################################################
import sys
input = sys.stdin.readline

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n, m = 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 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()}

uf = UnionFind(n)

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

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

Submission status: Accepted

Solution code:
class DisjointSets:#Union-Find
    def __init__(self, n):
        self.nodes = [-1] * n #根にサイズを負の値で格納する。
    def find(self, i):
        if self.nodes[i] < 0: #値が負の場合は根
            return i
        else:
            self.nodes[i] = self.find(self.nodes[i]) #縮約
            return self.nodes[i]
    def unite(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j:
            return
        if self.nodes[i] > self.nodes[j]: #サイズ比較してiの方がサイズが大きいようにする
            i, j = j, i
        self.nodes[i] += self.nodes[j] #大きい方に小さい方を統合しサイズを登録する。
        self.nodes[j] = i # jの親はi
    
    def size(self, i): # 所属する集合の大きさを返す
        i = self.find(i)
        return -self.nodes[i]

n, m = map(int, input().split())
ds = DisjointSets(n)
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    ds.unite(a, b)

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

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)

N, M = map(int, input().split())
uf = UnionFind(N)
ans = 0

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

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

print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

n, m = LI()
edges = [[] for _ in range(n)]
par = [i for i in range(n)]
rank = [0] * n
for _ in range(m):
    a, b = LI()
    if root(a-1) != root(b-1):
        union(a-1, b-1)

cnt = [0] * n
for i in range(n):
    cnt[root(i)] += 1
print(max(cnt))

Submission status: Accepted

Solution code:
n,m = 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 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())

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():
    num=uf.size(i)
    ans=max(ans,num)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def unite(x,y):
	rx=root(x);ry=root(y)
	if rank[rx]>rank[ry]:
		parent[ry]=rx
		size[rx]+=size[ry]
	else:
		parent[rx]=ry
		size[ry]+=size[rx]
		if rank[rx]==rank[ry]:
			rank[ry]+=1
def root(x):
	if x!=parent[x]:
		return root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
n,m=map(int,input().split())
parent=list(range(n))
rank=[0]*n
size=[1]*n
for i in range(m):
	a,b=map(int,input().split())
	if same(a-1,b-1)==False:
		unite(a-1,b-1)

print(max(size))

Submission status: Accepted

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

from collections import Counter

class union_find():
    def __init__(self,n):
        self.n=n
        ##親要素のノード番号を格納。par[x]==xのときそのノードは根
        ##親とはその上にノードなし！！　
        self.par=[-1 for i in range(n)]
        self.rank=[0]*(n)

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

        if self.par[x]>self.par[y]:
          x,y=y,x
          
        self.par[x]+=self.par[y]
        self.par[y]=x

    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    def size(self,x):
      return -self.par[self.find(x)]
      
    def members(self,x):
      root=self.find(x)
      return [i for i in range(self.n) if self.find(i)==root]
    
    def roots(self):
      return [i for i, x in enumerate(self.par) if x<0]
    
    def all_group_member(self):
      return {r:self.members(r) for r in self.roots()}
    
uf=union_find(n)
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  
ans=0

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

Submission status: Accepted

Solution code:
from collections import*
class UnionFind():
  def __init__(self, n=10**6):
    self.n=n
    self.root=[-1]*(n+1)
    self.rnk=[0]*(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 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x]+=self.root[y]
      self.root[y]=x
    else:
      self.root[y]+=self.root[x]
      self.root[x]=y
      if(self.rnk[x]==self.rnk[y]):
        self.rnk[y]+=1
  def same(self, x, y):
    return self.find(x)==self.find(y)
  def count(self, x):
    return -self.root[self.find(x)]
n,m=map(int,input().split())
uf=UnionFind(n)
for _ in range(m):
  a,b=map(int,input().split())
  uf.unite(a,b)
a=list(Counter([uf.find(i) for i in range(1,n+1)]).values())
print(max(a))

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
edges = defaultdict(set)

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

ans = 0
visited = [False] * N

def dfs(i):
    stack = [i]
    ans = 0
    while stack:
        i = stack.pop()
        if visited[i]:
            continue
        ans += 1
        visited[i] = True
        for dest in edges[i]:
            stack.append(dest)
    return ans

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def main():
    N, M = LI()
    u = UnionFind(N)
    for i in range(M):
        a, b = LI_()
        u.union(a, b)
    ans = 0
    for i in range(N):
        ans = max(ans, u.size(i))
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict


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 same(self, x, y):
        return self.find(x) == self.find(y)


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)

c = defaultdict(int)
for i in range(N):
    c[uf.find(i)] += 1

print(max(c.values()))

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
n,m = ma()
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n
        self.n = 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.root(x) == self.root(y)

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        for x in range(self.n):
            self.root(x)
        s = set()
        for par in self.par:
            s.add(par)
        return s
uf = unionfind(n)
for i in range(m):
    a,b = ma()
    a-=1;b-=1
    uf.unite(a,b)
ans = 0
for i in range(n):
    ans=max(ans,uf.get_size(i))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,m,*ab = map(int,read().split())

UF = UnionFind(n)

it = iter(ab)
for i,j in zip(it,it):
    UF.merge(i-1,j-1)

from collections import Counter
d = Counter(UF.root(i) for i in range(n))
print(max(d.values()))

Submission status: Accepted

Solution code:
from collections import deque

(N, M) = [int(x) for x in input().split()]

edges = [[int(x) - 1 for x in input().split()] for i in range(M)]  # 0 indexed


def bfs(source, getNbr):
    q = deque([source])
    dist = {source: 0}
    while q:
        node = q.popleft()
        d = dist[node]
        for nbr in getNbr(node):
            if nbr not in dist:
                q.append(nbr)
                dist[nbr] = d + 1
    return dist


graph = [[] for i in range(N)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)


def getNbr(u):
    return graph[u]


best = 0
seen = set()
for root in range(N):
    if root not in seen:
        comp = bfs(root, getNbr)
        best = max(best, len(comp))
        for k in comp:
            seen.add(k)
print(best)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


class UnionFind():
    def __init__(self, n):
        """
        Parameters
        ----------
        n:int
            the number of node
        """
        self.par = [-1] * n  # -self.par[i] means the tree size

    def find(self, x):
        """
        Parameters
        ----------
        x:int
            target node

        Return
        ----------
        res:int
            root node
        """
        if self.par[x] < 0:
            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.par[x] > self.par[y]:  # lesser has many nodes
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

    def size(self, x):
        '''
        Parameters
        ----------
        x:int
            target node

        Return
        ----------
        x:int
            size of  group  to which belongs
        '''
        return - self.par[self.find(x)]


n, m = inpl()
uf1 = UnionFind(n)
for _ in range(m):
    a, b = inpl()
    uf1.union(a - 1, b - 1)
for i in range(n):
    uf1.find(i)  # 一周findすることによって接続漏れをなくす。
dp = [1] * n
for i in uf1.par:
    if i >= 0:
        dp[i] += 1
print(max(dp))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

#最も大きなunionの大きさが答え
#Union Find

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

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

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

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

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

ans = 0
for i in par:
    if i < 0:
        ans = max(ans,-i)
print(ans)

Submission status: Accepted

Solution code:
# Union Find 木
from sys import setrecursionlimit, stdin

def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j

readline = stdin.readline
setrecursionlimit(10 ** 6)

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

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

print(-min(parent))

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N, M = [int(x) for x in input().strip().split()]
    par = [n for n in range(N)]
    rank = [0 for _ in range(N)]

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

    def union(x, y):
        x = find(par[x])
        y = find(par[y])
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    
    for m in range(M):
        a, b = [int(x)-1 for x in input().strip().split()]
        union(a, b)
    
    for n in range(N):
        find(n)
    
    ans = Counter(par)
    print(max(ans.values()))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False
            
# N, Q = map(int, input().split())
# uni = UnionFind(N)
# for _ in range(Q):
#     P, A, B = map(int, input().split())
#     if P == 1:
#         if uni.root(A) == uni.root(B): #親が同じかどうか
#             print ('Yes')
#         else:
#             print ('No')
#     else:
#         uni.connect(A, B)


import sys
input = sys.stdin.readline

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

uni = UnionFind(N + 1)
for _ in range(M):
    A, B = map(int, input().split())
    uni.connect(A, B)

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

print (ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
par = [-1 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
ans = 0
for i in range(n):
    ans = max(ans, size(i))
print(ans)