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:
from collections import deque

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab_set = []
for i in ab:
    ab_set.append([min(i), max(i)])
ab_set = list(map(tuple, ab_set))
ab_set = list(set(ab_set))
graph = [deque([]) for _ in range(n + 1)]

for i in ab_set:
    graph[i[0]].append(i[1])
    graph[i[1]].append(i[0])

arrive_time = [-1] * (n + 1)  # 到着時刻

def dfs(v):
    time = 1
    stack = [v]
    arrive_time[v] = time
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if arrive_time[w] < 0:
                time += 1
                arrive_time[w] = time
                stack.append(w)
        else:
            stack.pop()
    return arrive_time


for i in range(n):
    if arrive_time[i + 1] < 0:
        ans = dfs(i + 1)

print(max(ans))

Submission status: Accepted

Solution code:
import math

class UnionFind(): # 0インデックス
    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とyは-=1して使う
        '''
        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())

if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
A = list()
B = list()
for i in range(M):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)

class UnionFind():
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            # 経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parents[root_y] = root_x
                self.size[root_x] += self.size[root_y]
            else:
                self.parents[root_x] = root_y
                self.size[root_y] += self.size[root_x]
                if self.rank[root_x] == self.rank[root_y]:
                    self.rank[root_y] += 1

unionfind = UnionFind(N)
for i in range(M):
  unionfind.union(A[i]-1, B[i]-1)
count_list = [0]*N
for i in range(N):
  count_list[unionfind.find(i)] += 1
print(max(count_list))

Submission status: Accepted

Solution code:
from collections import deque

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

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

visited = [False] * N

ans = 1
for i in range(N):
    if visited[i]:
        continue
    visited[i] = True
    d = deque(G[i])
    tmp = 1
    while d:
        v = d.pop()
        if not visited[v]:
            visited[v] = True
            tmp += 1
            for j in G[v]:
                if not visited[j]:
                    d.append(j)
    if tmp > ans:
        ans = tmp

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
if m == 0:
    print(1)
    import sys
    sys.exit()

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

dist = [-1]*n
from collections import deque
q = deque([])

def bfs(vert,num):
    q.append(vert)
    dist[vert]=num
    while q:
        v = q.popleft()
        for i in graph[v]:
            if dist[i]!=-1:
                continue
            dist[i]=num
            q.append(i)

for j in range(n):
    if dist[j]==-1:
        bfs(j,j)

dist = list(dist)
from collections import Counter
e = Counter(dist)
print(e.most_common()[0][1])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

D = defaultdict(set)
R = {}
for _ in range(M):
  a, b = map(int, input().split())
  if a in R:
    if b in R:
      aa, bb = R[a], R[b] 
      if aa == bb:
        pass
      else:
        if len(D[aa]) < len(D[bb]):
          aa, bb = bb, aa
        for x in D[bb]:
          R[x] = aa
        D[aa] |= D[bb]
        del D[bb]
    else:
      R[b] = R[a]
      D[R[a]].add(b)
  else:
    if b in R:
      R[a] = R[b]
      D[R[b]].add(a)
    else:
      R[a] = a
      R[b] = a
      D[a].add(a)
      D[a].add(b)

print(max(len(x) for x in D.values()) if D else 1)

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


import sys

input = sys.stdin.readline
n, m = map(int, input().split())
a = set()
for _ in range(m):
    ab = sorted(map(int, input().split()))
    a.add((ab[0], ab[1]))
par = [-1] * n

for x, y in a:
    unite(x - 1, y - 1)

d = {}
for i in range(n):
    i = find(i)
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
print(max(d.values()))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(400000)
n,m=map(int,input().split())
g=[[] for _ in range(n+1)] #グラフ
for i in range(m):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
for j in range(len(g)):
    g[j]=sorted(list(set(g[j])))
visited=[0]*(n+1)
def dfs(v):
    global ret
    visited[v]+=1
    flag=0
    for i in range(len(g[v])):
        if visited[g[v][i]]==0:
            ret+=1
            flag=1
            dfs(g[v][i])
ans=0
for i in range(1,n+1):
    if visited[i]==0:
        ret=1
        dfs(i)
        length=ret
        if ans<length:
            ans=length
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
def f(p, c):
    if P[p] == 0:
        P[p] = c
        for j in range(len(F[p])):
            f(F[p][j], c)
N, M = map(int, input().split())
F = [[] for _ in range(N)]
P = [0] * N
for i in range(M):
    A, B = map(int, input().split())
    F[A-1].append(B-1)
    F[B-1].append(A-1)
for i in range(N):
    f(i, i+1)
C = [0] * N
for i in range(N):
    C[P[i]-1] += 1
print(max(C))

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 m in range(M):
	i,j = map(int,input().split())
	uf.union(i,j)
print(-min(uf.parents))

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
friend = defaultdict(set)
leader = []
for i in range(M):
    Ai, Bi = map(int, input().split())
    friend[Ai].add(Bi)
    friend[Bi].add(Ai)
already = {}
answer = 0
for i in range(1, N + 1):
    if i in already:
        continue
    if i not in friend:
        continue

    queue = []
    for f in friend[i]:
        already[f] = True
        queue.append(f)
    already[i] = True
    size = 0
    while len(queue) > size:
        item = queue[size]
        size += 1
        if item in friend:
            for f in friend[item]:
                if f not in already:
                    already[f] = True
                    queue.append(f)
    if size > answer:
        answer = size
print(answer + 1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
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())


uf = UnionFind(N+1)
for ab in AB:
    h1 = ab[0]
    h2 = ab[1]
    uf.union(h1, h2)

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

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)


N, M = map(int, input().split())
parent = [-1] * N


def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    parent[x] = y


def find(x):
    if parent[x] == -1:
        return x
    res = parent[x] = find(parent[x])
    return res

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


count = Counter(find(i) for i in range(N))
print(count.most_common(1)[0][1])

Submission status: Accepted

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

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

for m in range(M):
    a, b = map(int, input().split())
    friends_set[a].add(b)
    friends_set[b].add(a)

graphs = [False]*(n+1)
maxC = 0
from collections import deque

for current in range(1, n+1):
    if graphs[current]:
        continue
    graphs[current] = True

    count = 0
    candidate = deque(friends_set[current])
    while len(candidate) > 0:
        f = candidate.popleft()

        if graphs[f]:
            continue
        count += 1
        graphs[f] = True
        candidate += list(friends_set[f])
    maxC = max(maxC , count)

print(maxC + 1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
n, m = map(int, input().split())
g = defaultdict(list)
for i in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

c = 0
a = []
visited = set()
for i in range(1, n+1):
    if i in visited: continue
    c += 1
    visited.add(i)
    q =  deque([i])
    nos = 0
    while q:
        u = q.popleft()
        nos += 1
        for v in g[u]:
            if v in visited: continue
            visited.add(v)
            q.append(v)
    a.append(nos)

a.sort(reverse=True)
s = 0
for i in range(len(a)-1):
    s += a[i]-a[i+1]
print(s+a[-1])

Submission status: Accepted

Solution code:
import sys

def main():
    stdin = sys.stdin
    n, m = map(int, stdin.readline().split())

    par = [i for i in range(n)]
    size = [1] * n
    rank = [1] * n

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

    def unite(x, y):
        x = find(x, par)
        y = find(y, par)

        if x != y:
            # xとyの属している集合が異なる時
            if rank[x] < rank[y]:
                par[x] = y
                size[y] += size[x]
            else:
                par[y] = x
                size[x] += size[y]
                if rank[x] == rank[y]:
                    rank[x] += 1

    for _ in range(m):
        a, b = map(int, stdin.readline().split())
        unite(a-1, b-1)


    print(max(size))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,m = [int(v) for v in input().split()]
    if m==0:
        print(1)
        return
    
    g = [set() for _ in range(n+1)]
    seen = [False] * (n+1)
    for _ in range(m):
        a,b = [int(v) for v in input().split()]
        g[a].add(b)
        g[b].add(a)

    ans = 0
    for i in range(1,n+1):
        if seen[i]: continue
        stack = set([i])
        l = 0
        while len(stack)>0:
            no = stack.pop()
            seen[no] = True
            l += 1
            for nn in g[no]:
                if not seen[nn]:
                    stack.add(nn)
        ans = max(ans, l)

    # print(groups, g)
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import deque

n,m = map(int,input().split())
friend = [[] for i in range(n+1)]
end = [0 for i in range(n+1)]

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

for i in range(1,n+1):
    friend[i] = list(set(friend[i]))

memnum = []
q = deque()

for i in range(1,n+1):
    if end[i] != 0:
        continue
    elif end[i] == 0:
        tmp = 1
        num = 0
        end[i] = 1
        for j in friend[i]:
            end[j] = 1
            q.append(j)
        tmp += len(friend[i])
        while len(q) != 0:
            num = q.popleft()
            for j in friend[num]:
                if end[j] == 0:
                    end[j] = 1
                    q.append(j)
                    tmp += 1
        memnum.append(tmp)

print(max(memnum))

Submission status: Accepted

Solution code:
import sys,math
from collections import deque,defaultdict
import operator as op
from functools import reduce

sys.setrecursionlimit(10**6) 

I=sys.stdin.readline

 #s="abcdefghijklmnopqrstuvwxyz"

"""
x_move=[-1,0,1,0,-1,1,1,-1]
y_move=[0,1,0,-1,1,1,-1,-1]
"""
def ii():
	return int(I().strip())
def li():
	return list(map(int,I().strip().split()))
def mi():
	return map(int,I().strip().split())

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def find(a,par):
	while par[a]>0:
		a=par[a]
	return a




def union(u,v,par,size):
	a=find(u,par)
	b=find(v,par)
	if a!=b:
		if size[a]>=size[b]:
			size[a]+=size[b]
			par[b]=a
		else:
			size[b]+=size[a]
			par[a]=b




	
def main():
	n,m=mi()
	ans=0
	d=defaultdict(int)
	size=[1]*(n+1)
	par=[-1]*(n+1)
	for i in range(m):
		a,b=mi()
		union(a,b,par,size)
		
	#print(grp)
	print(max(size))




			


	

























	
	
	





if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self):
        '''\
Create an empty union find data structure.'''
        self.num_weights = {}
        self.parent_pointers = {}
        self.num_to_objects = {}
        self.objects_to_num = {}
        self.__repr__ = self.__str__
    def insert_objects(self, objects):
        '''\
Insert a sequence of objects into the structure.  All must be Python hashable.'''
        for object in objects:
            self.find(object);
    def find(self, object):
        '''\
Find the root of the set that an object is in.
If the object was not known, will make it known, and it becomes its own set.
Object must be Python hashable.'''
        if not object in self.objects_to_num:
            obj_num = len(self.objects_to_num)
            self.num_weights[obj_num] = 1
            self.objects_to_num[object] = obj_num
            self.num_to_objects[obj_num] = object
            self.parent_pointers[obj_num] = obj_num
            return object
        stk = [self.objects_to_num[object]]
        par = self.parent_pointers[stk[-1]]
        while par != stk[-1]:
            stk.append(par)
            par = self.parent_pointers[par]
        for i in stk:
            self.parent_pointers[i] = par
        return self.num_to_objects[par]
    def union(self, object1, object2):
        '''\
Combine the sets that contain the two objects given.
Both objects must be Python hashable.
If either or both objects are unknown, will make them known, and combine them.'''
        o1p = self.find(object1)
        o2p = self.find(object2)
        if o1p != o2p:
            on1 = self.objects_to_num[o1p]
            on2 = self.objects_to_num[o2p]
            w1 = self.num_weights[on1]
            w2 = self.num_weights[on2]
            if w1 < w2:
                o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1
            self.num_weights[on1] = w1+w2
            del self.num_weights[on2]
            self.parent_pointers[on2] = on1
    def __str__(self):
        '''\
Included for testing purposes only.
All information needed from the union find data structure can be attained
using find.'''
        sets = {}
        for i in range(len(self.objects_to_num)):
            sets[i] = []
        for i in self.objects_to_num:
            sets[self.objects_to_num[self.find(i)]].append(i)
        out = []
        for i in sets.values():
            if i:
                out.append(repr(i))
        return ', '.join(out)

uf = UnionFind()
n, m = map(int, input().split())
uf.insert_objects(range(1, n+1))
for _ in range(m):
    a,b = map(int, input().split())
    uf.union(a,b)
from collections import defaultdict
cnt = defaultdict(int)
for i in uf.objects_to_num:
    cnt[uf.find(i)] += 1
print(max(cnt.values()))

# print(len(set(uf.find(k) for k in uf.objects_to_num)))

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#n,m = int(input())
	#b , c = tin()
	#s = input()	
	n, m = tin()
	
	ll=[[] for _ in range(n)]
	for _ in range(m):
		a, b = tin()
		ll[a-1].append(b-1)
		ll[b-1].append(a-1)
		
	gid=-1
	gg=[-1]*n
	for i in range(n):
		if gg[i] != -1:
			continue
		gid += 1
		gg[i] = gid
		q=collections.deque()
		q.append(i)
		while q:
			p = q.popleft()
			for np in ll[p]:
				if gg[np] != -1:
					continue
				gg[np]=gid
				q.append(np)
				
	cc=collections.Counter(gg)
	ret=0
	for k in cc:
		ret = max(ret, cc[k])
	return ret
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    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

    def same_check(self, x, y):
        return self.find(x) == self.find(y)
N, M = map(int, input().split())
n = [i+1 for i in range(N)]
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
import collections
g = 0
for k, v in collections.Counter([uf.find(i) for i in range(N)]).items():
    g = max(v, g)
print(g)

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)
AB_list = []

for i in range(M):
    A, B = map(int, input().split())
    AB_list.append([A, B])
    uf.union(A, B)
ans=0
for i in range(N):
  q=uf.size(i)
  if ans<=q:
    ans=q
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rf = lambda: map(float, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

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

n, m = rm()
u = UnionFind(n)
for _ in range(m):
    a, b = rm()
    a, b = a-1, b-1
    u.unite(a,b)
for i in range(n):
    u.root(i)
print(max(collections.Counter(u.par).values()))

Submission status: Accepted

Solution code:
import queue

N, M = map(int, input().split())
AB = {}
for i in range(N): AB[i] = set()
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    AB[A].add(B)
    AB[B].add(A)

finish = [False] * N
q = queue.Queue()
ans = 0
for i in range(N):
    if finish[i]: continue
    q.put(i)
    group = set()
    while not q.empty():
        x = q.get()
        group.add(x)
        finish[x] = True
        for friend in AB[x]:
            if finish[friend]: continue
            q.put(friend)
            finish[friend] = True
    tmp = len(group)
    if tmp >= N / 2:
        ans = tmp
        break
    ans = max(ans, len(group))
print(ans)

Submission status: Accepted

Solution code:
import collections
N, M = map(int, input().split())
dic = {i + 1: set() for i in range(N)}

for m in range(M):
    A, B = map(int, input().split())
    dic[A].add(B)
    dic[B].add(A)


vi_n = [i + 1 for i in range(N)]
vi_d = set()
stack = [i+1 for i in range(N)]
while (len(vi_d) < N):
    v = stack.pop()
    if v in vi_d:
        continue
    vi_d.add(v)

    for node in dic[v]:
        stack.append(node)
        vi_n[node - 1] = vi_n[v - 1]


c = collections.Counter(vi_n)
c_l = list(c.values())
#print(c_l)
print(max(c_l))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

graph = defaultdict(set)

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

if m == 0:
    print(1)
    exit()

for _ in range(m):
    a,b = map(int, sys.stdin.readline().split())

    if not b in graph[a]:
        graph[a].add(b)
    if not a in graph[b]:
        graph[b].add(a)

visited = set()
maxi = 0

def dfs(start):
    stk = [start]
    visited.add(start)
    temp = 1

    while stk:
        cur = stk.pop()

        for c in graph[cur]:
            if not c in visited:
                visited.add(c)
                stk.append(c)
                temp += 1

    return temp

for j in graph:
    if not j in visited:
        cnt = dfs(j)
        maxi = max(cnt, maxi)

print(maxi)

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,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())


def do():
    n,m=INTM()
    uf=UnionFind(n)
    for i in range(m):
        a,b=INTM()
        uf.union(a-1,b-1)

    ans=0

    for i in range(n):
        ans=max(ans,uf.size(i))
    
    print(ans)
                
if __name__=='__main__':
    do()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(int(2e5+999))

def solve():
    n,m=map(int,input().split()[0:2])

    fa=list(range(0,n+1))
    sz=[1]*(n+1)
    def gf(x) :
        if x==fa[x] :
            return x
        fa[x]=gf(fa[x])
        return fa[x]

    for i in range(m) :
        a,b=map(gf,map(int,input().split()[0:2]))
        if a!=b :
            fa[a]=b
            sz[b]+=sz[a]

    ans=1
    for i in range(1,n+1) :
        ans=max(ans,sz[gf(i)])
    return ans

print(solve())

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n,m=map(int,input().split())
a=[-1]*(n+1)
st=set()
for i in range(m):
    x,y=map(int,input().split())
    chk=(min(x,y),max(x,y))
    if chk in st: 
        continue
    st.add(chk)
    while a[x]>=0:
        x=a[x]
    while a[y]>=0:
        y=a[y]
    if x==y:
        continue
    if a[x]<a[y]:
        a[x]+=a[y]
        a[y]=x
    else:
        a[y]+=a[x]
        a[x]=y
cnt=0
for i in a[1:]:
    if i<0:
        cnt=max(cnt,-i)
print(cnt)