Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
    a,b=map(int,input().split())
    d[a].add(b)
    d[b].add(a)

vis=set()
ma=0
for i in range(1,n+1):
    if i not in vis:
        stack=[i]
        ans=1
        vis.add(i)
        while(stack):
            cur=stack.pop()
            for j in d[cur]:
                if j not in vis:
                    vis.add(j)
                    ans += 1
                    stack.append(j)
        ma=max(ma,ans)
print(ma)

Submission status: Accepted

Solution code:
import sys
from typing import List

class UnionFind:
    """
    自身が親であれば、その集合に属する頂点数に-1をかけた物
    そうでなければ、親のid
    """
    def __init__(self, r: int):
        self.r : List[int] = [-1] * r

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

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

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

def main():
    def input(): return sys.stdin.readline()[:-1]
    n, m = map(int, input().split())
    
    # 友達集合を作る
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1; b -= 1
        uf.unite(a, b)

    # 最大の友達集合をもとめる
    ans = 0
    for i in range(n):
        ans = max(ans, uf.size(i))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    def find(self, x):
        while self.parents[x] > 0:
            x = self.parents[x]
        return x

    def union(self, i, j):
        pi, pj = self.find(i), self.find(j)
        if pi == pj:
            return
        if self.parents[pi] < self.parents[pj]:
            pi, pj = pj, pi
            i, j = j, i
        self.parents[pi] += self.parents[pj]
        self.parents[pj] = pi
        self.reconnect(j, pi)

    def reconnect(self, i, j):
        while self.parents[i] > 0:
            t = self.parents[i]
            self.parents[i] = j
            i = t


def main():
    n, m, *ab, = map(int, open(0).read().split())
    uf = UnionFind(n + 1)

    for i, j in zip(ab[::2], ab[1::2]):
        uf.union(i, j)

    print(-min(uf.parents))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n + 1)]
        self.size = [1] * (n + 1)
    def find(self, x):
        y = self.root[x]
        if x == y:
            return x
        else:
            z = self.find(y)
            self.root[x] = z
            return z
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        sx = self.size[rx]
        sy = self.size[ry]
        if rx == ry:
            return 0
        else:
            if sx >= sy:
                self.root[ry] = rx
                self.size[rx] = sx + sy
            else:
                self.root[rx] = ry
                self.size[ry] = sx + sy
        return sx * sy

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

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

cnt = [0] * (N + 1)
for i in range(1, N + 1):
    cnt[uf.find(i)] += 1

print(max(cnt))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import deque
    N, M = MI()
    fri_list = [[] for _ in range(N)]
    for i in range(M):
        a, b = MI()
        fri_list[a - 1].append(b - 1)
        fri_list[b - 1].append(a - 1)

    #print(fri_list)
    group_list = []
    num_list = [0] * N
    for i in range(0, N):
        if num_list[i] == 0:
            num_list[i] = 1
            #print(i, 'i')
            cnt = 1
            queue = deque([i])
            while queue:
                v = queue.popleft()
                #print(v, 'v')
                for j in fri_list[v]:
                    #print(j, 'j')
                    if num_list[j] == 0:
                        num_list[j] = 1
                        queue.append(j)
                        cnt += 1
            group_list.append(cnt)

    ans = max(group_list)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

n, m = map(int, input().split())
if m == 0:
    print(1)
    exit()
if m == 1:
    print(2)
    exit()
boss = list(range(n))

def look_boss(target):
    num = target
    while num != boss[num]:
        num = boss[num]
    boss[target] = num
    return num

for _ in range(m):
    a, b = map(int, input().split())
    boss_a = look_boss(a-1)
    boss_b = look_boss(b-1)
    if boss_a != boss_b:
        boss[boss_b] = boss_a

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

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:
class UnionFind: # simple
    def __init__(self, n):
        self.prsz = [-1] * n # parent ' size
    def find(self, v): # root
        if self.prsz[v] < 0: return v
        self.prsz[v] = self.find(self.prsz[v])
        return self.prsz[v]
    def union(self, v, u): # unite
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.prsz[v] > self.prsz[u]: v, u = u, v # size(v) < size(u)
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True
    def size(self, v): return -self.prsz[self.find(v)]

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m): uf.union(*map(lambda x: int(x)-1, input().split())) # unite
ans = 0
for i in range(n): ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

edge = [[] for i in range(N)]

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

ans = 0
color = [-1] * N
nextcolor = 0
for st in range(N):
	if color[st] != -1:
		continue
	q = deque()
	q.append(st)
	color[st] = nextcolor
	nextcolor += 1
	count = 1
	while len(q) > 0:
		node = q.popleft()
		for child in edge[node]:
			if color[child] != -1:
				continue
			color[child] = color[node]
			count += 1
			q.append(child)
	ans = max(ans, count)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def main4():
    N, M = map(int, input().split())
    pair = [list() for i in range(N)]

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

    dq = deque()
    color = ["w" for i in range(N)]

    ans = 0
    for i in range(N):
        if color[i] == "w":
            dq.append(i)

            con = 1
            while True:
                if len(dq) == 0:
                    break

                idx = dq.popleft()
                color[idx] = "g"

                for j in range(len(pair[idx])):
                    if color[pair[idx][j]] == "w":
                        dq.append(pair[idx][j])
                        color[pair[idx][j]] = "g"
                        con += 1

            ans = max(ans, con)
            
    print(ans)

if __name__ == "__main__":
    main4()

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 1

def dfs(node):
    while len(todo) > 0:
        node = todo.pop()
        if tf[node] == 0:
            tf[node] = 1
            seen.add(node)
            for nextnode in graph[node]:
                todo.append(nextnode)

todo = deque()
done = set()
tf = [0 for _ in range(n+1)]
for i in range(1,n+1):
    if i in done:
        continue
    else:
        todo.append(i)
        seen = set()
        dfs(i)
        #print(i,seen)
        ans = max(ans,len(seen))
        done |= seen
print(ans)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N, M = map(int, input().split())
uf = UnionFind(N+1)

for _ in range(M):
  A, B = map(int, input().split())
  uf.union(A, B)
  # print(uf)
  # print()

print(max([uf.size(r) for r in uf.roots()]))

Submission status: Accepted

Solution code:
from collections import deque
def main4():
    N, M = map(int, input().split())
    pair = [list() for i in range(N)]

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

    dq = deque()
    color = ["w" for i in range(N)]

    ans = 0
    for i in range(N):
        if color[i] == "w":
            dq.append(i)
            # print("start node : {}".format(i))

            con = 1
            while True:

                if len(dq) == 0:
                    break

                idx = dq.popleft()
                color[idx] = "g"

                for j in range(len(pair[idx])):
                    if color[pair[idx][j]] == "w":
                        dq.append(pair[idx][j])
                        color[pair[idx][j]] = "g"
                        con += 1
                        # print("cur : {} / next : {}".format(idx, pair[idx][j]))

            ans = max(ans, con)

    print(ans)

if __name__ == "__main__":
    main4()

Submission status: Accepted

Solution code:
from collections import Counter

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)

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

c = Counter(uf.par)
print(max(c.values()))

Submission status: Accepted

Solution code:
def main():
    n, m, *ab, = map(int, open(0).read().split())
    p = [-1] * (n + 1)

    def find(x):
        while p[x] > 0:
            x = p[x]
        return x

    def union(i, j):
        pi, pj = find(i), find(j)
        if pi == pj:
            return
        if p[pi] < p[pj]:
            pi, pj = pj, pi
            i, j = j, i
        p[pi] += p[pj]
        p[pj] = pi
        reconnect(j, pi)

    def reconnect(i, j):
        while p[i] > 0:
            k = p[i]
            p[i] = j
            i = k

    for i, j in zip(ab[::2], ab[1::2]):
        union(i, j)

    print(-min(p))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


n, m = LI()

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 _ in range(m):
    a, b = LI()
    a -= 1
    b -= 1
    unite(a, b)

ans = max(map(size, range(n)))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind: # simple
    def __init__(self, n):
        self.prsz = [-1] * n # parent ' size
    def find(self, v): # root
        if self.prsz[v] < 0: return v
        else:
            self.prsz[v] = self.find(self.prsz[v])
            return self.prsz[v]
    def union(self, v, u): # unite
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.prsz[v] > self.prsz[u]: v, u = u, v # size(v) < size(u)
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True
    def size(self, v): return -self.prsz[self.find(v)]

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m): uf.union(*map(lambda x: int(x)-1, input().split())) # unite
ans = 0
for i in range(n): ans = max(ans, uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
class UnionFindTree:
	def __init__(self,size):
		"""
		size個の集合を作成
		負の値は、ルートで集合の個数
		正の値は、次の要素
		"""
		self.table=[-1 for _ in range(size)]

	def find(self,x):
		"""
		グループ番号を取得
		"""
		# 本質的には、木を上に辿るだけ
		# ただし、通常、UnionFindでは経路圧縮を行うのが普通らしい
		if self.table[x] < 0:
			# 一個上がルートならば、それを返して終わり
			return x
		else:
			# そうでなければ、ルートまで辿るついでに経路圧縮
			self.table[x] = self.find(self.table[x])
			return self.table[x]
		return x

	# 併合
	def union(self,x,y):
		# s1,s2は正
		# table[s1],table[s2]は負
		s1=self.find(x)
		s2=self.find(y)
		if s1!=s2:
			# 個数が小さい方をルートにくっつける
			# ルートサイズは負なので、ルートが大きい方が個数が小さい?
			if self.table[s2]<=self.table[s1]:
				# s1が小さい
				self.table[s1]+=self.table[s2]
				self.table[s2]=s1
			else:
				# s2が小さい
				self.table[s2]+=self.table[s1]
				self.table[s1]=s2
			return True
		return False

	def maxGroupCount(self):
		"""
		Groupの中で最大のものの数
		"""
		cnt = 0
		for i in range(len(self.table)):
			if self.table[i] < 0:
				cnt = max( cnt, -self.table[i] )
		return cnt


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

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

# for n in range(N):
# 	print(n+1, "さん:",uf.find(n))


print(uf.maxGroupCount())

Submission status: Accepted

Solution code:
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################

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

F=[ [] for i in range(N+1) ]
for i in range(M):
  a,b = map(int, input().split())
  F[a].append(b)
  F[b].append(a)

_pa(F)

from collections import deque

G=[-1]*(N+1)
for i in range(N+1):
  if G[i]>-1: continue
  G[i] = i
  Q = deque()
  Q.append(F[i])
  while Q:
    l = Q.popleft()
    for f in l:
      if G[f]==-1:
        G[f] = i
        Q.append(F[f])

_pa(G)


from collections import Counter
C = Counter(G)
ans = 1
for k,v in C.items():
  ans = max(ans, v)

_p(C)
_p(*C)

print(ans)

Submission status: Accepted

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

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

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

def is_same(x, y):
    return root(x) == root(y)


n, m = map(int, input().split())
par = [i for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    unite(a, b)

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

Submission status: Accepted

Solution code:
class UnionFind: # simple
    def __init__(self, n):
        self.prsz = [-1] * n # parent ' size
    def find(self, v): # root
        if self.prsz[v] < 0: return v
        else:
            self.prsz[v] = self.find(self.prsz[v])
            return self.prsz[v]
    def union(self, v, u): # unite
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.g_size(v) < self.g_size(u): v, u = u, v
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True
    def g_size(self, v): return -self.prsz[self.find(v)]

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m): uf.union(*map(lambda x: int(x)-1, input().split())) # unite
ans = 0
for i in range(n): ans = max(ans, uf.g_size(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


#隣接リスト 1-index
def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N, M = NMI()
    F = [NLI() for _ in range(M)]
    tree = make_adjlist_nond(N, F)

    ans = 0
    seen = [0] * (N + 1)
    for start in range(1, N+1):
        que = deque()
        que.append(start)

        seen[start] = 1
        fri_cnt = 1
        while que:
            now = que.popleft()

            for goto in tree[now]:
                if seen[goto]:
                    continue
                seen[goto] = 1
                fri_cnt += 1
                que.append(goto)
        ans = max(fri_cnt, ans)
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

class UnionFind:
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素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]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属するかどうかを返す
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素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.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()}

    # ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す (print()での表示用)
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def resolve():
    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(ans, uf.size(i))
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
class UnionFind():

    def __init__(self, n):
        self.parent = [i for i in range(0, n)]
        self.rank= [0] * n

    def root(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

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

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

    def rootRank(self, x):
        return self.rank[self.root(x)]

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

uf = UnionFind(N)

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

z=0
c=[0]*N
for i in range(N):
    p=uf.root(i)
    c[p]+=1
    if z<c[p]:
        z=c[p]

print(z)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


#隣接リスト 1-index
def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n+1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def main():
    N, M = NMI()
    F = {}
    for _ in range(M):
        a, b = NMI()
        F[(a, b)] = 1
    tree = make_adjlist_nond(N, list(F.keys()))

    ans = 0
    seen = [0] * (N + 1)
    for start in range(1, N+1):
        que = deque()
        que.append(start)

        seen[start] = 1
        fri_cnt = 1
        while que:
            now = que.popleft()

            for goto in tree[now]:
                if seen[goto]:
                    continue
                seen[goto] = 1
                fri_cnt += 1
                que.append(goto)
        ans = max(fri_cnt, ans)
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#UnionFind
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)
now_max = 0

while True:
    try:
        listA = list(map(int,input().split()))
        uf.union(listA[0] - 1, listA[1] - 1)
    except:
        break
for i in range(N):
    now_max = max(uf.size(i),now_max)
print(now_max)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.node = [-1 for i in range(N)]

    def find(self, i):
        if self.node[i] < 0:
            return i
        else:
            return self.find(self.node[i])

    def size(self, i):
        return -self.node[self.find(i)]
        
    def unite(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i == j: return False

        if self.size(i) < self.size(j):
            i, j = j, i

        self.node[i] += self.node[j]
        self.node[j] = i
        return True

def main():
    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)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# union find, bfs

import sys
from collections import deque
si = sys.stdin.readline


def main():
    [n, m] = [int(e) for e in si().split()]
    if not m:
        print(1)
        return

    visited = [False]*(n+1)
    fm = [set() for _ in range(n+1)]
    mx = 0

    while m:
        m -= 1
        [a, b] = [int(e) for e in si().split()]
        fm[a].add(b)
        fm[b].add(a)

    for i in range(1, n+1):
        if visited[i]:
            continue
        visited[i] = True
        q = deque()
        q.append(i)
        cnt = 1
        while q:
            curr = q.popleft()
            for e in fm[curr]:
                if not visited[e]:
                    visited[e] = True
                    q.append(e)
                    cnt += 1
        mx = max(mx, cnt)
    print(mx)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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 solve():
    N, M = map(int, rl().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(lambda n: int(n) - 1, rl().split())
        uf.union(a, b)
    
    ans = 0
    for i in range(N):
        ans = max(ans, uf.size(i))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    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())
# 負のとき size, 非負のとき parent
par = [-1] * N
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)
ans = -1 * min(par)

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

def resolve():
  N, M = map(int, input().split(" "))
  # friends = [None] * (N + 1)
  friends = UnionFind(N)

  for _ in range(M):
    A, B = map(int, input().split(" "))
    A -= 1
    B -= 1
    friends.union(min(A, B), max(A, B))

  print(min(friends.parents)*(-1))

if __name__ == "__main__":
  resolve()