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:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

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

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

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

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

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

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

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

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

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


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

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

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

Submission status: Accepted

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

def main():
    n , m = map( int, input().split() )
    Sets = []

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

    for i in range( m ):
        a , b = map( int , input().split() )
        if Dicto[a] == -1 and Dicto[b] == -1:
            Sets.append( set( [a,b] ) )
            x_i = len(Sets)
            Dicto[ a ] = x_i - 1
            Dicto[ b ] = x_i - 1
        elif Dicto[ a ] != -1 and Dicto[ b ] == -1:
            Sets[ Dicto[a] ].add( b )
            Dicto[ b ] = Dicto[a]
        elif Dicto[ b ] != -1 and Dicto[ a ] == -1:
            Sets[ Dicto[b] ].add( a )
            Dicto[ a ] = Dicto[b]
        elif Dicto[ b ] != -1 and Dicto[ a ] != -1 and Dicto[ a ] != Dicto[ b ]:
            if Dicto[ b ] > Dicto[ a ]:
                set_x = Sets[Dicto[b]]
                Sets[ Dicto[a] ] |= ( set_x )
                l_set_x = list( set_x )
                for j in l_set_x:
                    Dicto[j] = Dicto[a]

            else:
                set_x = Sets[Dicto[a]]
                Sets[ Dicto[b] ] |= ( set_x )
                l_set_x = list( set_x )
                for j in l_set_x:
                    Dicto[j] = Dicto[b]

    #print(Sets)
    #print(Dicto)

    max_len = 1

    for i in range( len(Sets) ):
        if max_len < len( Sets[i] ):
            max_len = len( Sets[i] )

    print(max_len)


main()

Submission status: Accepted

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

N, M = map(int, input().split())
f = [set() for _ in range(N)]
v = [False for _ in range(N)]
ans = 1

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  f[a].add(b)
  f[b].add(a)
  
  
def dfs(fi):
  if v[fi]: return 0
  
  v[fi] = True
  cnt = 1
  
  for fr in f[fi]:
    cnt += dfs(fr)
    
  return cnt

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

Submission status: Accepted

Solution code:
from collections import deque



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

D = [-1]*(N+1)
#S=[[0] * 3 for _ in range(2)] 2行3列の場合
S = [[]for i in range(N+1)]
deq=deque()

    


for i in range(M):
    A,B=map(int,input().split())
    
    S[A].append(B)
    S[B].append(A)
ans=0
for i in range(1,N+1):
    deq.append(i)
    count=0
    #D = [-1]*(N+1)
    while len(deq)!=0:
        v= deq.popleft()
        for nv in S[v]:
            if D[nv] !=-1:
                continue
            D[nv] =D[v]+1
            deq.append(nv)
            count+=1
    if count>ans:
        ans=count


if ans==0:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
class DisjointSet():
    def __init__(self, size):
        self.size = size
        self.rank = [None] * size
        self.parents = [None] * size
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.parents[x] = x
        self.rank[x] = 0

    def findSet(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.findSet(self.parents[x])
        return self.parents[x]

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.parents[y] = x
        else:
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

N, M = map(int, input().split())
ds = DisjointSet(N)
for _ in range(M):
    a, b = map(int, input().split())
    ds.unite(a-1, b-1)

setdict = defaultdict(int)
for i in range(N):
    setdict[ds.findSet(i)] += 1

clist = list(sorted(list(setdict.values())))
# clist = set(setdict.values())
ans = 0
r = 0
for c in clist:
    ans += (c-r)
    r = c

# print(clist)
print(ans)

Submission status: Accepted

Solution code:
# def friends(arr):
#     table = [{}]
#     for a in arr:
#         seted = False
#         for t in table:
#             if a[0] in t or a[1] in t:
#                 seted = True
#                 t.add(a[0])
#                 t.add(a[1])
#         if not seted:
#             table.append({a[0], a[1]})
#
#     return max(table, key=len)
# def start():
#     n, m = [int(x) for x in input().split(" ")]
#     arr = []
#     while m:
#         arr.append([int(x) for x in input().split(" ")])
#         m -= 1
#     print(len(friends(arr)))
# start()

def friends(n,arr):
    import collections
    graph = collections.defaultdict(list)
    for i in range(len(arr)):
        graph[arr[i][0]].append(arr[i][1])
        graph[arr[i][1]].append(arr[i][0])
    visited = [False]*(n+1)
    maxi = 0
    for i in range(1,n+1):
        if not visited[i]:
            queue = collections.deque()
            queue.append(i)
            visited[i] = True
            temp = 0
            while queue:
                temp += 1
                s = queue.popleft()
                for t in graph[s]:
                    if not visited[t]:
                        queue.append(t)
                        visited[t] = True
            maxi = max(maxi, temp)
    return maxi

def start():
    n, m = [int(x) for x in input().split(" ")]
    arr = []
    while m:
        arr.append([int(x) for x in input().split(" ")])
        m -= 1
    print((friends(n,arr)))
start()

Submission status: Accepted

Solution code:
from collections import deque, defaultdict

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

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

vertexes = set()
edges = defaultdict(set)
for a, b in AB:
    edges[a].add(b)
    edges[b].add(a)
    vertexes.add(a)
    vertexes.add(b)

res = 1
while vertexes:
    v = vertexes.pop()
    compos = 1
    q = deque()
    q.append(v)
    while q:
        now = q.popleft()
        for neighbor in edges[now]:
            if neighbor in vertexes:
                vertexes.discard(neighbor)
                q.append(neighbor)
                compos += 1
    
    res = max(compos, res)

print(res)

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int, input().split())
groups = [0] * (N + 1)
group_num_list = [[0]]
group_num = 1
for _ in range(M):
    A, B = map(int, input().split())
    if groups[A] != 0 and groups[B] != 0:
        if groups[A] != groups[B]:
            lower = min(groups[A], groups[B])
            higher = max(groups[A], groups[B])
            for i in group_num_list[higher]:
                groups[i] = lower
            tmp = group_num_list[higher]
            group_num_list[lower].extend(tmp)
            # del group_num_list[higher]
    elif groups[A] != 0:
        groups[B] = groups[A]
        group_num_list[groups[A]].append(int(B))
    elif groups[B] != 0:
        groups[A] = groups[B]
        group_num_list[groups[B]].append(int(A))
    else:
        groups[A] = group_num
        groups[B] = group_num
        group_num_list.append([int(A), int(B)])
        group_num += 1
counter = Counter(groups)
# print(collection)
# print(group_num_list)
if len(group_num_list) == 1:
    print(1)
elif int(counter.most_common()[0][0]) != 0:
    print(counter.most_common()[0][1])
else:
    print(counter.most_common()[1][1])

Submission status: Accepted

Solution code:

import collections

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(" "))
ufb = UnionFind(n)

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

c = collections.Counter([ufb.find(i) for i in range(n)])
print(max(c.values()))

Submission status: Accepted

Solution code:
class UnionFind():
    #https://note.nkmk.me/python-union-find/ 
    #note.nkmk.me  2019-08-18 
    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())


# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない
N,M = map(int, input().split())
G =UnionFind(N)
ans =0
for i in range(M):
    a,b = map(int, input().split())
    #a,b =min(a,b),max(a,b)
    G.union(a-1,b-1)
    ans =max(ans,G.size(a-1))
if M ==0:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import collections
n, m = map(int, input().split())
mydic = defaultdict(set)
for i in range(m):
    ai, bi = map(int, input().split())
    mydic[ai].add(bi)
    mydic[bi].add(ai)
queque = collections.deque()
visited = [0] * (n + 1)
ans = 0
for i in range(1, n+1):
    if not visited[i]:
        temp = 1
        queque.append(i)
        temp = 1
        while queque:
            j = queque.popleft()
            visited[j] = 1
            for k in mydic[j]:
                if visited[k] == 0:
                    temp += 1
                    visited[k] = 1
                    queque.append(k)
        ans = max(ans, temp)
    else:
        continue            
print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from time import time
import re
setrecursionlimit(10**9)
mod=10**9+7
inf=10**18
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=[int(x) for x in input().split()]
uf=UnionFind(n)
for _ in range(m):
    a,b=[int(x)-1 for x in input().split()]
    uf.union(a,b)
ans=0
for i in range(n):
    ans=max(ans,uf.size(i))
print(ans)

Submission status: Accepted

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

import networkx as nx
G = nx.Graph()
G.add_edges_from(a)
nx.connected_components(G)

max_size = 1

for component in nx.connected_components(G):
    if len(component) > max_size:
        max_cluster = component
        max_size = len(max_cluster)
print(max_size)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
lst = [[] for _ in range(n)]
visited = [0] * n
for _ in range(m):
    a, b = map(int, input().split())    
    a -= 1
    b -= 1
    lst[a].append(b)
    lst[b].append(a)

def dfs(st):
    global visited
    global c
    stack = deque([st])
    visited[st] = 1
    c = 1
    while stack:
        nw = stack.pop()
        if visited[nw] == 0:
            c = 1
        for _ in lst[nw]:
            if visited[_] == 0:
                visited[_] = 1
                c += 1
                stack.append(_)
        
ans = 0
for _ in range(n):
    if visited[_] == 0:
        dfs(_)
        ans = max(ans, c)    
print(ans)

Submission status: Accepted

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

    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)

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

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

Submission status: Accepted

Solution code:
# D
from collections import deque
from bisect import bisect_left as bl

f=lambda:map(int,input().split())
N,M=f()
D=[[] for _ in [0]*(N+1)]
F=[0]*(N+1)
F[0]=1
for _ in range(M):
    a,b=f()
    D[a].append(b)
    D[b].append(a)

q=deque()
res=0


while bl(F,1):
    index=bl(F,1)-1
    q.append(index)
    tmp=0
    while q:
        k=q.pop()
        if F[k]!=1:
            tmp+=1
            F[k]=1
            for d in list(set(D[k])):
                if F[d]!=1:
                    q.append(d)
            D[k]=0
    res=max(res,tmp)

print(res)

Submission status: Accepted

Solution code:
def abc177d():
    n, m = map(int, input().split())
    if m ==0:
        print(1)
        return 
    check = [-1] * n
    group_no = 0
    group = {}
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if check[a] == check[b] != -1: continue
        if check[a] == check[b] == -1:
            group[group_no] = {a, b}
            check[a] = check[b] = group_no
            group_no += 1
        elif check[a] == -1 or check[b] == -1:
            max_g = max(check[a],check[b])
            group[max_g] |= {a,b}
            check[b] = check[a] = max_g
        else:
            re = min(check[a], check[b])
            de = max(check[a], check[b])
            for v in group[de]:
                check[v] = re
            group[re] |= group[de]
            del group[de]
    max_val = max(map(len, group.values()))
    print(max(1,max_val))


abc177d()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].add(b - 1)
    G[b - 1].add(a - 1)
d = [0] * N
Q = deque()
for i in range(N):
    if d[i] != 0:
        continue
    Q.append(i)
    d[i] = 1
    while len(Q) > 0:
        q = Q.pop()
        for g in G[q]:
            if d[g] != 0:
                continue
            d[i] += 1
            d[g] = -1
            Q.append(g)
print(max(d))

Submission status: Accepted

Solution code:
from collections import deque

def main():
    n, m = list(map(int, input().split(" ")))
    v_set = [set([]) for _ in range(n)]
    for _ in range(m):
        a, b = list(map(int, input().split(" ")))
        v_set[a-1].add(b-1)
        v_set[b-1].add(a-1)

    max_num = 0
    checked = [0]*n
    for ni in range(n):
        if checked[ni]:
            continue
        stack = deque([ni])
        checked[ni] = 1
        f = 1
        while stack:
            cur = stack.pop()
            for next_i in v_set[cur]:
                if checked[next_i]:
                    continue
                stack.append(next_i)
                checked[next_i] = 1
                f+=1
        max_num = max(max_num, f)

    print(max_num)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

d = {i: [] for i in range(1, N + 1)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)

visited = [False for _ in range(N + 1)]


def visit(x):
    if visited[x]:
        return 0
    visited[x] = True

    z = 1
    for y in d[x]:
        z += visit(y)
    return z


m = 1
for i in range(1, N + 1):
    r = visit(i)
    if m < r:
        m = r

print(m)

Submission status: Accepted

Solution code:
import collections
import sys

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

l = []
for _ in range(n):
  l.append([])

# for x in range(n):
#   l[x]

for a, b in ab:
  a -= 1
  b -= 1
  l[a].append(b)
  l[b].append(a)

# c = [None] * n

# for i in range(n):
#   if c[i] is None:
#     c[i] = i
#   for f in l[i]:
#     if c[f] is None:
#       c[f] = i


# https://algo-logic.info/connected-components-num/

color = [None] * n

sys.setrecursionlimit(3*10**5)


def dfs(i, c):
  if color[i] is not None:
    return
  color[i] = c

  for f in l[i]:
    dfs(f, c)


for i in range(n):
  if color[i] is None:
    dfs(i, i)

print(max([v for k, v in collections.Counter(color).items()]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
par = [-1]*(n+1)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[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
    else:
      if par[x] > par[y]:
        x,y = y,x
      par[x] += par[y]
      par[y] = x
def size(x):
    return -par[find(x)]

max_size=0
for _ in range(m):
  a,b=map(int,input().split())
  unite(a,b)
  
print(-min(par))

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
Groups = [1 for i in range(N)]
dsts = [-1 for i in range(N)]
ABs = [[int(i)-1 for i in input().split()] for i in range(M)]
for A, B in ABs:
    dst = min(A, B)
    src = max(A, B)
    # print('A', A, B, dst, src)
    while(dsts[dst] != -1):
        dst = dsts[dst]
    while(dsts[src] != -1):
        src = dsts[src]
    if dst != min(A, B):
        omdst = min(A, B)
        while(dsts[omdst] != dst):
            n_omdst = dsts[omdst]
            dsts[omdst] = dst
            omdst = n_omdst
    if src != max(A, B):
        omsrc = max(A, B)
        while(dsts[omsrc] != src):
            n_omsrc = dsts[omsrc]
            dsts[omsrc] = src
            omsrc = n_omsrc

    if dst == src:
        continue
    dst2 = min(dst, src)
    src2 = max(dst, src)
    dsts[src2] = dst2
    Groups[dst2] += Groups[src2]
    Groups[src2] = 0
    # print(Groups)
    # print(dsts)
print(max(Groups))

Submission status: Accepted

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

import sys
from collections import namedtuple

DEBUG = False


def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep=" "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


Point = namedtuple("Point", ("id", "to"))
points = {}


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 scc_forward(p, visited, rev_scc_ponints):
    if p in visited:
        return
    visited.add(p)
    for to in points[p].to:
        scc_forward(to, visited, rev_scc_ponints)
    rev_scc_ponints.append(p)


def scc_backword(p, visited, cur_sc):
    if p in visited:
        return 0
    visited.add(p)
    cur_sc.add(p)
    for to in points[p].to:
        scc_backword(to, visited, cur_sc)
    print(repr(cur_sc))
    return len(cur_sc)


def count_max_sc_size(points):
    rev_scc_points = []
    visited_forward = set()
    for p in points:
        scc_forward(p, visited_forward, rev_scc_points)

    max_sc_size = 1
    visited_backward = set()
    for p in rev_scc_points:
        cur_sc_size = scc_backword(p, visited_backward, set())
        if cur_sc_size > max_sc_size:
            max_sc_size = cur_sc_size
    return max_sc_size


def old_main():
    _n, m = read_list(int)
    for _ in range(0, m):
        a, b = read_list(int)
        a -= 1
        b -= 1

        if a not in points:
            points[a] = Point(a, set())
        if b not in points:
            points[b] = Point(b, set())
        f = points[a]
        t = points[b]
        f.to.add(b)
        t.to.add(a)
    print(count_max_sc_size(points))


def main():
    n, m = read_list(int)
    union_find = UnionFind(n)
    for _ in range(0, m):
        a, b = read_list(int)
        a -= 1
        b -= 1
        union_find.union(a, b)

    max_size = 1
    for i in range(0, n):
        if union_find.size(i) > max_size:
            max_size = union_find.size(i)
    print(max_size)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

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

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

marks = [False for i in range(N)]
m = 1
def dfs(n):
    global E_list
    global marks
    global N,M

    marks[n] = True

    steps = 1

    for nx in E_list[n]:
        if not marks[nx]:
            marks[nx] = True
            steps += dfs(nx)
    
    return steps



for i in range(M):
    e1,e2 = map(int, input().split())
   
    E_list[e1-1].append(e2-1)
    E_list[e2-1].append(e1-1)


for i in range(N):
    E_list[i] = list(set(E_list[i]))

for i in range(N):
    if not marks[i]:
        st = dfs(i)

    m = max(m,st)

print(m)

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

      
from collections import Counter
n, m = map(int, input().split())

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

print(abs(min((uf.parents))))

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())
a = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)
ans = 0
x = uf.parents
for i in range(n):
    if x[i]<0:
        #print(i)
        ans = max(ans,uf.size(i))
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:  # O(α(N))
    def __init__(self, size):  # construct a Union-Find tree (1-idx)
        self.parent = [i for i in range(size)]
        self.rank = [0] * size
 
    def find(self, x):  # find the group (root) of a vertex
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def is_same(self, x, y):  # check two vertices are in the same group
        return self.find(x) == self.find(y)
 
    def unite(self, x, y):  # unite two groups
        x, y = self.find(x), self.find(y)
        if x == y:  # the same group
            return
        # unite a small one to a bigger one to balance trees
        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 main():
    N, Q = map(int, input().strip().split())
    ab = [map(int, input().strip().split()) for _ in range(Q)]
    uf = UnionFind(N)
    for a, b in ab:
        uf.unite(a-1, b-1)
    for i in range(N):
        uf.find(i)
    import collections
    print(collections.Counter(uf.parent).most_common()[0][1])

                

if __name__=="__main__":
    main()