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:
#!/usr/bin/env python3
import sys
import numpy as np


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    parent = [-1] * (N+1)
    rank = [0] * (N+1)
    
    def find(x):
        if parent[x]<0:
            return x
        else:
            parent[x] = find(parent[x])
            return parent[x]
    
    def same(x, y):
        return find(x)==find(y)

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

        if x==y:
            return 0

        if rank[x]>rank[y]:
            parent[x] += parent[y]
            parent[y] = x
        else:
            parent[y] += parent[x]
            parent[x] = y
            if rank[x]==rank[y]:
                rank[y] += 1

    for i in range(M):
        unite(A[i], B[i])

    parent = parent[1:]
    rank = rank[1:]

    ans = 0
    for i in range(len(parent)):
        ans = max(ans, -parent[i])

    print(ans)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

group = [0] * n
color = 1


def dfs(s, c):
    stack = [s]
    group[s] = c
    cnt = 1
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if group[v] == 0:
                group[v] = c
                stack.append(v)
                cnt += 1

    return cnt


ans = 0
for i in range(n):
    if group[i] == 0:
        cnt = dfs(i, color)
        color += 1
        ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
r = [[] for i in range(n)]
for i in range(m):
  x,y = map(int,input().split())
  r[x-1].append(y-1)
  r[y-1].append(x-1)
max = 0  
mark = []
for i in range(n):
  mark.append('t')

for i in range(n):
  if mark[i] == 't':
    s = 0
    mark[i] = 'f'
    stack = [i]
    while stack:
      x = stack.pop() #要素を取り出す
      s += 1
      for j in range(len(r[x])):
        nx = r[x][j]
        if mark[nx] == 't':
            mark[nx] = 'f'
            stack.append(nx) 
    
  if max < s:
    max = s
                     
print(max)

Submission status: Accepted

Solution code:
# Date [ 2020-08-29 21:30:11 ]
# Problem [ d.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

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 Main():
    n, m = read_ints()
    
    uf = UnionFind(n)
    for _ in range(m):
        a, b = read_ints()
        a -= 1; b -= 1
        uf.union(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:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return 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 depth(self):
    	ans = 0
    	for r in self.roots():
    		ans = max(ans,self.size(r))
    	return ans

n,m = readInts()
ab = []
for i in range(m):
	ab.append(readInts())

uf = UnionFind(n+1)
for a,b in ab:
	uf.union(a,b)

print(uf.depth())

Submission status: Accepted

Solution code:
import sys,bisect

from sys  import stdin,stdout

from bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right

from math import gcd,ceil,floor,sqrt

from collections import Counter,defaultdict,deque,OrderedDict

dx=[-1,1,0,0]
dy=[0,0,1,-1]


sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 998244353
mod = 10**9+7

def isPrime(n):
    if (n <= 1) :return False
    if (n <= 3) :return True
    if (n%2 == 0 or n%3 == 0):return False
    for i in range(5,ceil(sqrt(n))+1,6):
        if (n%i==0 or n%(i+2)==0):
            return False
    return True

def st():
    return list(stdin.readline().strip())

def inp():
    return int(stdin.readline())

def li():
    return list(map(int,stdin.readline().split()))

def mp():
    return map(int,stdin.readline().split())

def pr(n):
    stdout.write(str(n)+"\n")

def CC(d,v,i,l):
    v[i]=True
    stack=[i]
    c=1
    while stack:
        a=stack.pop()
        for i in d[a]:
            if not v[i]:
                stack.append(i)
                v[i]=True
                c+=1
    l.append(c)
    
def solve():
    n,m=mp()
    d={i:[] for i in range(1,n+1)}
    for i in range(m):
        a,b=mp()
        d[a].append(b)
        d[b].append(a)

    v=[False for i in range(n+1)]
    x=[]
    for i in range(1,n+1):
        if not v[i]:
            CC(d,v,i,x)
           
    pr(max(x))
        
        
    
for _ in range(1):
    solve()

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N,M = MI()


class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x


U = UnionFind(N)
for i in range(M):
    a,b = MI()
    U.unite(a,b)

A = U.par
for i in range(1,N+1):
    A[i] = U.find(A[i])

del A[0]


from collections import Counter

c = Counter(A)
print(max(c.values()))

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 sizes(self):
        return {x: self.size(x) for x in 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 i in u.sizes().values():
        ans = max(i, ans)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class UnionFind(object):
    def __init__(self, n, recursion = False):
        self._par = list(range(n))
        self._size = [1] * n
        self._recursion = recursion

    def root(self, k):
        if self._recursion:
            if k == self._par[k]:
                return k
            self._par[k] = self.root(self._par[k])
            return self._par[k]
        else:
            root = k
            while root != self._par[root]: root = self._par[root]
            while k != root: k, self._par[k] = self._par[k], root
            return root

    def unite(self, i, j):
        i, j = self.root(i), self.root(j)
        if i == j: return False
        if self._size[i] < self._size[j]: i, j = j, i
        self._par[j] = i
        self._size[i] += self._size[j]
        return True

    def is_connected(self, i, j):
        return self.root(i) == self.root(j)

    def size(self, k):
        return self._size[self.root(k)]

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

    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1; v -= 1
        uf.unite(u, v)

    print(max(uf.size(v) for v in range(n)))
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

N, M = map(int, input().split())
nums = [0] * N
friends = []
for _ in range(N):
    friends.append(set())

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

gnum = 0
groupn = 0
nmax = 0

def find_route(i):
    global gnum
    global nums
    global friends
    global groupn
    global nmax
    if len(friends[i]) == 0:
        return
    if nums[i] == 0:
        gnum += 1
        groupn = 1
        nums[i] = gnum
    for f in friends[i]:
        if nums[f] == 0:
            nums[f] = gnum
            groupn += 1
            if groupn > nmax:
                nmax = groupn
            find_route(f)

for i in range(N):
    find_route(i)

print(max(nmax, 1))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]


    
    
def main():
    N, M = MI()
    mylist = [[] for i in range(N)]
    for i in range(M):
        a, b = MI()
        mylist[a-1].append(b-1)
        mylist[b-1].append(a-1)
    
    dic = defaultdict(int)
    
    visit = [True]*N
    index = 0

    for i in range(N):
        dq = deque()
        if visit[i]:
            dq.append(i)
            while dq:
                temp = dq.popleft()
                for j in mylist[temp]:
                    if visit[j]:
                        dic[index]+=1
                        visit[j] = False
                        dq.append(j)
            index+=1
                
        
        
        
    #グループ数
    all_group_num = sorted(dic.values())
    res = 0
    all_num = N
    min_num = 0
    
    if sum(all_group_num) < N:
        all_group_num = [1]*(N-sum(all_group_num))+all_group_num
    group = len(all_group_num)

    while True:
        index = bisect_right(all_group_num, min_num)
        all_num -= (group-index)*(all_group_num[index]-min_num)
        res+= all_group_num[index]-min_num
        
        min_num = all_group_num[index]
        
        if all_num == 0:
            break
        
    print(res)

    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *
import queue

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, M = In.ints()

if M==0:
    Out.int(1)
else:
    conns = [set() for i in range(N)]
    for i in range(M):
        A, B = In.ints()

        A-=1
        B-=1

        if B not in conns[A]:
            conns[A].add(B)
        if A not in conns[B]:
            conns[B].add(A)
    
    ans = 0
    seen = set()
    for i in range(N):        
        if len(conns[i])==0:            
            continue
        
        if i not in seen:
            seen.add(i)

            #dfs
            stck = deque([(i)])
            ct = 1
            while len(stck)>0:
                now = stck.popleft()
                
                for nex in conns[now]:
                    if nex not in seen:
                        ct+=1
                        seen.add(nex)
                        ans = max(ans, ct)
                        stck.append(nex)
                    

    Out.int(ans)
        




######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(99999999)


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

tomodachi=[[]for i in range(n)]

for i in range(m):
    tomodachi[friends[i][0]-1].append(friends[i][1]-1)
    tomodachi[friends[i][1]-1].append(friends[i][0]-1)

for i in range(n):
    tomodachi[i]=list(set(tomodachi[i]))

namelist=[1 for i in range(n)]
teams=[]

def haba(x,kari,tomodachi,namelist):
    for i in range(len(tomodachi[x])):
        if namelist[tomodachi[x][i]]==1:#生き残っているなら
            kari.append(tomodachi[x][i])
            namelist[tomodachi[x][i]]=0#殺す
            haba(tomodachi[x][i],kari,tomodachi,namelist)
    return(kari)
            


for i in range(n):
    if namelist[i]==1:
        teams.append(list(set(haba(i,[i],tomodachi,namelist))))

saidai=0

for i in range(len(teams)):
    if saidai<len(teams[i]):
        saidai=len(teams[i])

ans=saidai

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    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 unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

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

print(max(tree.size))

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *                      # ll = deepcopy(l)
from heapq import *                     # heappush(hp,x)
from string import *                    # alpha = ascii_lowercase
from random import *                    # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *                    # bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin                   # bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize                 # minn = -maxsize
from operator import *                  # d = sorted(d.items(), key=itemgetter(1))
from itertools import *                 # pre = [0] + list(accumulate(l))
from decimal import Decimal             # a = Decimal(a)    # use this for math questions
from collections import Counter         # d = dict(Counter(l))
from collections import defaultdict     # d = defaultdict(list)

'''
5 3
1 2
3 4
5 1
'''

class DSU:

	def __init__(self,n):
		self.n = n
		self.par = list(range(self.n))
		self.size = [1 for i in range(self.n)]

	def find(self,i):
		while(i != self.par[i]):
			self.par[i] = self.par[self.par[i]]
			i = self.par[i]
		return i

	def unite(self,a,b):
		par_a = self.find(a)
		par_b = self.find(b)
		if(par_a == par_b):
			return False
		else:
			if(par_a <= par_b):
				self.par[par_b] = par_a
				self.size[par_a] += self.size[par_b]
			else:
				self.par[par_a] = par_b
				self.size[par_b] += self.size[par_a]
			return True

	def same(self,a,b):
		self.find(a)
		self.find(b)
		return self.par[a] == self.par[b]

	def size(self,a):
		return self.size[a]


N,E = map(int, input().split())
dsu = DSU(N)
for i in range(E):
	a,b = list(map(int, input().split()))
	a -= 1
	b -= 1
	dsu.unite(a,b)
print(max(dsu.size))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        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())
AB = [list(map(int,input().split())) for _ in range(M)]

uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0]-1,AB[i][1]-1)
ufr = uf.roots()
ans = 0
for i in ufr:
    ans = max(ans,uf.size(i))
print(ans)

Submission status: Accepted

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

#初期化
#根なら-size,子なら親の頂点
n, m = map(int, input().split())
par = [-1]*n

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque

d = defaultdict(set) #初期中身は空のset

N, M = map(int, input().split())
for i in range(M):
  A, B = map(int, input().split())
  d[A-1].add(B-1)
  d[B-1].add(A-1)
        
check = [0]*N
mans = 0

for i in range(N):
    ans = 0
    if check[i] == 0:
        check[i] = 1
        ans += 1
        sl = deque(list(d[i]))
        while sl:
            s = sl.pop()
            if check[s] == 0:
                check[s] = 1
                ans += 1
                sl.extend(list(d[s]))
    if mans < ans:
        mans = ans

print(mans)

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)

N,M=map(int, input().split())
mx=0
uf = UnionFind(N+1)
for i in range(M):
	a,b = map(int, input().split())
	uf.union(a,b)
for i in uf.parents:
	mx = max(mx, uf.size(i))
if M == 0:
	mx = 1
print(mx)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(99999999)


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

tomodachi=[[]for i in range(n)]

for i in range(m):
    tomodachi[friends[i][0]-1].append(friends[i][1]-1)
    tomodachi[friends[i][1]-1].append(friends[i][0]-1)

for i in range(n):
    tomodachi[i]=list(set(tomodachi[i]))

namelist=[1 for i in range(n)]
teams=[]

def haba(x,kari,tomodachi,namelist):
    for i in range(len(tomodachi[x])):
        if namelist[tomodachi[x][i]]==1:#生き残っているなら
            kari.append(tomodachi[x][i])
            namelist[tomodachi[x][i]]=0#殺す
            haba(tomodachi[x][i],kari,tomodachi,namelist)
    return(kari)
            


for i in range(n):
    if namelist[i]==1:
        teams.append(list(set(haba(i,[i],tomodachi,namelist))))

saidai=0

for i in range(len(teams)):
    if saidai<len(teams[i]):
        saidai=len(teams[i])

ans=saidai

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
i4 = np.int32
i8 = np.int64


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


def union (x, y, parents, depth):
    x = find(x, parents)
    y = find(y, parents)
    if x == y:
        return

    if depth[x] == depth[y]:
        depth[x] += 1
        parents[y] = x
    elif depth[x] > depth[y]:
        parents[y] = x
    else:
        parents[x] = y


def main(in_file):
    stdin = open(in_file)
    N, M = [int(x) for x in stdin.readline().split()]
    a = np.empty(M, i8)
    b = np.empty(M, i8)
    for i in range(M):
        a[i], b[i] = [int(x) - 1 for x in stdin.readline().split()]
    parents = np.arange(N)
    depth = np.zeros(N, i8)
    for i in range(M):
        union(a[i], b[i], parents, depth)
    num = np.zeros(N, i8)
    for i in range(N):
        p = find(i, parents)
        num[p] += 1
    ans = num.max()
    print(ans)


main('/dev/stdin')

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
fri_dic = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in fri_dic:
    fri_dic[a] = set()
  if b not in fri_dic[a]:
    fri_dic[a].add(b)
  if b not in fri_dic:
    fri_dic[b] = set()
  if a not in fri_dic[b]:
    fri_dic[b].add(a)
visited = set()
max_count = 0
for i in range(1, n + 1):
  #print(visited)
  if i in visited:
    continue
  stack = [i]
  con_visited = set()
  while stack:
    p = stack.pop()
    if p in visited:
      continue
    visited.add(p)
    con_visited.add(p)
    if p not in fri_dic:
      continue
    for j in fri_dic[p]:
      stack.append(j)
  if len(con_visited) > max_count:
    max_count = len(con_visited)
print(max_count)

Submission status: Accepted

Solution code:
INF=float('inf')
n,m=map(int,input().split())

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

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

for _ in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  unite(a,b)
ans=-INF
for i in range(n):
  s=size(i)
  ans=max(ans,s)
print(ans)

Submission status: Accepted

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

from collections import defaultdict

# union find
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

uf = UnionFind(N)

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

    uf.union(a, b)

# member = defaultdict(int)
r = min(uf.table)
if r != -1:
    mm = abs(r)
    # ic = 0
    # for n in uf.table:
    #     if n == -1:
    #         ic += 1

    # if ic%mm != 0:
    #     mm += 1
else:
    mm = 1

print(mm)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
F = [[] for _ in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    F[A].append(B)
    F[B].append(A)
a = [1 for _ in range(N)]
l = []
b = [0 for _ in range(N)]
for j in range(N):
    mem = 1
    a[j] = 0
    nex = F[j]
    while True:
        que = nex
        nex = []
        for k in que:
            if a[k] == 1:
                a[k] = 0
                mem += 1
                nex.extend(F[k])
        if nex == []:
            break
    l.append(mem)
print(max(l))