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: Time Limit Exceeded

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):
        d = {}
        for i in range(self.n):
            p = self.find(i)
            d[p] = d.get(p, []) + [i]
        return d

    def __str__(self):
        return '\n'.join('{}: {}'.format(k, v) for k, v in self.all_group_members().items())


def resolve():
    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())
        u.union(a - 1, b - 1)
    ans = 0
    for v in u.all_group_members().values():
        ans = max(len(v), ans)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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)

all_group_members = uf.all_group_members()
ans = 0

for k, v in all_group_members.items():
    ans = max(ans, len(v))

print(ans)

Submission status: Time Limit Exceeded

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

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

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

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

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

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

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


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

UnionFind=UnionFind(n+1)
for a,b in AB:
    UnionFind.Unite(a,b)

A=UnionFind.group_members()
ans=0
for i in A:
    ans=max(ans,len(A[i]))
print(ans)

Submission status: Time Limit Exceeded

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

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

def uff(x):
    while x!=uf[x]:
        x=uf[x]
    return x

for i in range(m):
    a,b=map(int,input().split())
    ua=uff(a)
    ub=uff(b)
    if ua<ub:
        uf[ub]=ua
    else:
        uf[ua]=ub

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

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

ans = 0
for y in uf.all_group_members().values():
    ans = max(ans, len(y))

print(ans)

Submission status: Time Limit Exceeded

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 all_group_size(self):
        return [len(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())
tree = UnionFind(n)
for _ in range(m):
    i,j = map(int, input().split())
    tree.union(i-1,j-1)

print(max(tree.all_group_size()))

Submission status: Time Limit Exceeded

Solution code:
f=lambda:map(int,input().split())
n,m=f()
# Union Find
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]

for i in range(m):
  a,b=f()
  unite(a-1,b-1)
print(max(size(i) for i in range(n)))

Submission status: Time Limit Exceeded

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

class UnionFind:
	"""
	class UnionFind
	https://note.nkmk.me/python-union-find/
	
	order O(log(n))
	
	n = the number of elements
	parents = the list that contains "parents" of x. be careful that it doesn't contain "root" of x.
	"""
	def __init__(self, n):
		"""
		make UnionFind
		:param n: the number of elements
		"""
		self.n = n
		self.parents = [-1] * n
	
	def find(self, x):
		"""
		:param x: an element
		:return: the root containing 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):
		"""
		:param x, y: an element
		"""
		# root
		x = self.find(x)
		y = self.find(y)
		if x == y:
			# already same group so do nothing
			return
		if self.parents[x] > self.parents[y]:
			# the root should be min of group
			x, y = y, x
		# remind that x, y is the root, x < y, then, y unions to x.
		self.parents[x] += self.parents[y]
		# and then y's parent is x.
		self.parents[y] = x
	def size(self, x):
		# return the size of group
		return -self.parents[self.find(x)]
	
	def same(self, x, y):
		# return whether the x, y are in same group
		return self.find(x) == self.find(y)
	
	def members(self, x):
		# return members of group
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]
	
	def roots(self):
		# return all roots
		return [i for i, x in enumerate(self.parents) if x < 0]
	
	def group_count(self):
		# return how many groups
		return len(self.roots())
	
	def all_group_members(self):
		# return all members of all groups
		return {r: self.members(r) for r in self.roots()}

friends = UnionFind(n)

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

ans = 0
for i, j in friends.all_group_members().items():
	ans = max(len(j), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(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()}

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


n,m=mp()
uf = UnionFind(n+1)
for i in range(m):
    a,b=mp()
    uf.union(a,b)
ans=0
for i in list(uf.all_group_members().values()):
    ans=max(ans,len(i))
print(ans)

Submission status: Time Limit Exceeded

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,j in all_group_members().items():
    ans = max(ans,len(j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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 main():
    N, M = map(int, readline().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, readline().split())
        uf.union(a-1,b-1)
    L = uf.all_group_members().values()
    ans = 1
    for l in L:
        ans = max(ans, len(l))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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, readline().split())
    uf = UnionFind(N)

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

    gr = 0
    gm = uf.all_group_members()

    for val in gm.values():
        gr = max(gr, len(val))

    print(gr)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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)
D = uf.all_group_members()
ans = 0
for i in D.values():
    ans = max(ans, len(i))
print(ans)

Submission status: Accepted

Solution code:
def A():
    d, t, s = map(int, input().split())
    print("Yes" if t*s>=d else "No")

def B():
    s = input()
    t = input()
    sa = len(s) - len(t)
    ret = 10000000000
    for i in range(sa+1):
        cnt = 0
        for j in range(len(t)):
            if s[j+i] != t[j]: cnt += 1
        ret = min(ret, cnt)
    print(ret)

def C():
    int(input())
    A = list(map(int, input().split()))
    S = sum(A)
    T = 0
    for e in A:
        T += e*e
    print((S * S - T)//2)

class UF:
    def __init__(self, N):
        self.N = N
        self.sz = [1] * N
        self.par = [i for i in range(N)]
        self.d = [1] * N

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return False
        if self.d[y] > self.d[x]:
            self.par[x] = y
            self.sz[y] += self.sz[x]
        else:
            self.par[y] = x
            self.sz[x] += self.sz[y]
            if self.d[x] == self.d[y]: self.d[x] += 1

def D():
    n, m = map(int, input().split())
    uf = UF(n+1)
    for i in range(m):
        a, b = map(int, input().split())
        uf.unite(a, b)
    print(max(uf.sz))

D()

Submission status: Accepted

Solution code:
import networkx as nx
n,m=map(int, input().split())
uf=nx.utils.UnionFind()
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a, b)
ans=1
for i in uf.to_sets():
    ans=max(ans,len(i))
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())
    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:
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()))
uf = UnionFind(n)

for i in range(m):
    a,b = list(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 issame(self, x, y):
        return self.find[x] == self.find(y)


'''
参考
https://qiita.com/K_SIO/items/03ff1fc1184cb39674aa#d-friends
'''
if __name__ == '__main__':
    N, M = map(int, input().split())
    uf = UnionFind(N)

    for _ in range(M):
        A, B = map(int, input().split())
        uf.union(A-1, B-1)
    
    ans = 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 unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x

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

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

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

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 r in uf.roots():
  s=uf.size(r)
  ans=max(ans,s)
print(ans)

Submission status: Accepted

Solution code:
def find(x):
  if par[x] < 0:
    return x
  else:
    tank = []
    while par[x] >= 0:
      tank.append(x)
      x = par[x]
    for elt in tank:
      par[elt] = x
    return x

def unite(x,y):
  x = find(x)
  y = find(y)
    
  if x == y:
    return False
  else:
    if par[x] > par[y]:
      x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

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

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

N,M=map(int,input().split())
par = [-1]*N
for _ in range(M):
  a,b=map(int,input().split())
  unite(a-1,b-1)
print(-min(par))

Submission status: Accepted

Solution code:
from networkx.utils import UnionFind as UF
n,m=map(int, input().split())
uf=UF()
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a, b)
ans=1
for i in uf.to_sets():
    ans=max(ans,len(i))
print(ans)

Submission status: Accepted

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


class UnionFind(object):
    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]


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

max_ = 0
roots = uf.roots()

for r in roots:
    max_ = max(max_, uf.size(r))

print(max_)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

    def find_max(self):
        return max(self.size)

uf = UnionFind(N)

answer = []
append = answer.append
merge = uf.merge

for i in range(M):
    a,b = map(int, input().split())
    merge(a,b)
print(uf.find_max())

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

# # # # unionfind.py # # # #

# usage: uf = Unionfind(n) ; x = uf.root(y); uf.conn(a,b)

class Unionfind:

  def __init__(s,n):
    s.sz = [1] * n
    s.ances = [i for i in range(n)]

  def root(s,x):
    a = []
    y = x
    while s.ances[y] != y:
      a.append(y)
      y = s.ances[y]
    for z in a:
      s.ances[z] = y
    return y

  def conn(s,x,y):
    i = s.root(x)
    j = s.root(y)
    if i==j:
      return
    #k  = [i,j].min
    k  = j if (s.sz[i]<s.sz[j]) else i
    if k==j:
      s.ances[i] = j
    else:
      s.ances[j] = i
    s.sz[k] = s.sz[i] + s.sz[j]

# # # # end unionfind.py # # # #

n,m = inm()
uf = Unionfind(n)
for i in range(m):
    a,b = inm()
    uf.conn(a-1,b-1)
h = {}
x = 0
for i in range(n):
    r = uf.root(i)
    if r not in h:
        h[r] = 1
    else:
        h[r] += 1
    x = max(x,h[r])
print(x)

Submission status: Accepted

Solution code:
N, M = (int(d) for d in input().split())

C = [set() for i in range(N+1)]
for i in range(M):
    A, B = (int(d) for d in input().split())
    C[A].update([B])
    C[B].update([A])

# BFS
seen = set()
G = []

for i in range(1, N+1):
    if i in seen:
        continue

    # create new group
    G.append(set())

    # create queue
    Q = [i]
    G[-1].update(Q)
    seen.update(Q)

    while len(Q) > 0:
        # queue is not empty

        I = Q.pop(0)
        J = C[I].difference(seen)
        Q += list(J)
        G[-1].update(J)

        seen.update(J)

print(max([len(g) for g in G]))

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    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:
N, M = list(map(int, input().split()))
A = [0] * M
B = [0] * M
R = [0] * N
for i in range(N):
    R[i] = set()

for i in range(M):
    A[i], B[i] = list(map(int, input().split()))
    R[A[i]-1].add(B[i]-1)
    R[B[i]-1].add(A[i]-1)

stack = set()
visited = set()
max_groups = 0

for i in range(N):
    if not i in visited:
        stack.add(i)
        groups = 0
        while True:
            current = stack.pop()
            visited.add(current)
            groups += 1
            stack |= (R[current] - visited)
            if not stack:
                break
        max_groups = max(max_groups,groups)

print(max_groups)