Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
#ABC177
#D - Friends

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

friends=[[i] for i in range(N)]
member=[]

for i in range(M):
  x,y=map(lambda x :int(x)-1,input().split())
  friends[x].append(y)
  friends[y].append(x)
  member.extend([x,y])

friends=[sorted(set(i)) for i in friends]
member=sorted(set(member))

for i in member:
  a=[]
  c=[]
  for j in range(len(friends)):
    b=friends[j]
    if i in b:
      a.extend(b)
    else:
      c.append(b)
  friends=[list(set(a))]+c
  
group=[len(i) for i in friends]    


print(max(group))

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n,m=map(int, input().split())
uf=UnionFind(n)
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a-1, b-1)
cnt=0
x=list(uf.all_group_members().values())
for l in x:
    cnt=max(cnt, len(l))
print(cnt)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n,m=map(int, input().split())
uf=UnionFind(n)
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a-1, b-1)
cnt=0
for l in list(uf.all_group_members().values()):
    cnt=max(cnt, len(l))

print(cnt)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

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

out = 0
for L in Network.all_group_members().values():
    out = max(out,len(L))
print(out)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N,M = list(map(int,input().split()))
Network = UnionFind(N)
Friend = [0] * N
BlockInNetwork = [0] * N

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

out = 0
for L in Network.all_group_members().values():
    out = max(out,len(L))
print(out)

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque

n,m=map(int,input().split())
f=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)
g=[0]*(n+1)
p=[0]*(n+1)
for i in range(1,n+1):
    if p[i]==0:
        p[i]=i
        data=[i]
        data=deque(data)
        while len(data)>0:
            pos=data.popleft()
            p[pos]=i
            for j in f[pos]:
                if p[j]==0:
                    data.append(j)
for i in range(n):
    g[p[i+1]]+=1
print(max(g))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
f=[[] for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    f[a].append(b)
    f[b].append(a)
g=[0]*(n+1)
p=[0]*(n+1)
for i in range(1,n+1):
    if p[i]==0:
        p[i]=i
        data=[i]
        while len(data)>0:
            pos=data.pop(0)
            p[pos]=i
            for j in f[pos]:
                if p[j]==0:
                    data.append(j)
for i in range(n):
    g[p[i+1]]+=1
print(max(g))

Submission status: Time Limit Exceeded

Solution code:
#D - Friends
N,M = map(int,input().split())
par = [i for i in range(N+1)]
 
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
 
def size(x):
    return par.count(find(x))
 
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if par[x] > par[y]:
        x,y = y,x
    #par[x] += par[y]
    par[y] = x
#    par[x] = y
 
#print(par)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
#    print(par)
 
group_count = 0
 
for i in range(N):
    group_count = max(group_count,size(i))
 
# 出力
print(group_count)

Submission status: Time Limit Exceeded

Solution code:
#D - Friends
N,M = map(int,input().split())
par = [i for i in range(N+1)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def size(x):
    return par.count(find(x))

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    if par[x] > par[y]:
        x,y = y,x
    #par[x] += par[y]
    par[y] = x
#    par[x] = y

#print(par)
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    unite(a,b)
#    print(par)

group_count = 0

for i in range(N):
    group_count = max(group_count,size(i))

# 出力
print(group_count)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
ans = 0
mem = uf.all_group_members()
for k in mem.keys():
    ans = max(ans, len(mem[k]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500*500)

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

    def root(self, x):
        if self.par[x] < 0:
            return x
        return self.root(self.par[x])

    def unite(self, x, y):
        if x > y:
            x, y = y, x
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx

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

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def return_par(self):
        return self.par

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,m=nii()
l=[lnii() for i 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 same(self, x, y):
        return self.find(x) == self.find(y)

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

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

uf=UnionFind(n)
for a,b, in l:
  a-=1
  b-=1
  if uf.same(a,b)==False:
    uf.union(a,b)

ans=0
roots=uf.roots()
for i in uf.roots():
  mem=len(uf.members(i))
  ans=max(ans,mem)
print(ans)

Submission status: Time Limit Exceeded

Solution code:

"""
https://atcoder.jp/contests/abc177/tasks/abc177_d
"""

import numpy as np


def solve(n, m, a):
    if m == 0:
        return 1

    grp = [np.array(a[0])]
    for i in range(1, m):
        # このfと結合できるものを集めてくればよい
        f = np.array(a[i])

        lg = len(grp)
        gi = 0
        while gi < lg:
            g = grp[gi]

            u = np.intersect1d(f, g)
            if u.size == 0:
                gi += 1
            else:
                f = np.union1d(f, grp.pop(gi))
                lg = len(grp)

        grp.append(f)

    ml = 0
    for g in grp:
        if g.size > ml:
            ml = g.size

    return ml


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

print(solve(n, m, a))

Submission status: Time Limit Exceeded

Solution code:
"""
https://atcoder.jp/contests/abc177/tasks/abc177_d
"""


def solve(n, m, a):
    if m == 0:
        return 1

    grp = [set(a[0])]
    for i in range(1, m):
        # このfと結合できるものを集めてくればよい
        f = set(a[i])

        tgrp = []

        for gi, g in enumerate(grp):

            if f.isdisjoint(g):
                tgrp.append(g)
            else:
                f = f.union(g)
        tgrp.append(f)
        grp = tgrp

    ml = 0
    for g in grp:
        if len(g) > ml:
            ml = len(g)

    return ml


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

print(solve(n, m, a))

Submission status: Time Limit Exceeded

Solution code:
number = [int(s) for s in input().split()]
input = [[int(x) for x in input().split()] for i in range(number[1])]
check = [[0] * number[0] for i in range(number[0])]

#print(check)

temp = 0

for i in range(number[1]):
    check[input[i][0]-1][input[i][1]-1] = 1
    check[input[i][1]-1][input[i][0]-1] = 1

for i in range(number[0]):
    if(sum(check[i]) > temp):
        temp = sum(check[i])

#print(check+1)

print(temp+1)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    global ans
    n,m = i_map()
    s = [0]*n
    g = [[0]*n for i in range(n)]
    for i in range(m):
        a,b = i_map()
        a -= 1
        b -= 1
        g[a][b] = g[b][a] = 1

    def dfs(i):
        global ans
        s[i] = 1
        ans += 1
        for v in range(n):
            if g[i][v] == 0:
                continue
            if s[v] == 0:
                dfs(v)

    cnts = []

    for i in range(n):
        if s[i] == 0:
            trial = dfs(i)
            cnts.append(ans)
            ans = 0
    print(max(cnts))




if __name__=="__main__":
    ans = 0
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [0] * 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):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
  
N, M = map(int, input().split())
uft = UnionFindTree(N)
for m in range(M):
  a, b = map(lambda x: int(x)-1, input().split())
  uft.union(a, b)
  
size = [uft.parents.count(n) for n in range(N)]
print(max(size))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


t = dict()

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


for a, b in ab:
    t[a].add(b)
    t[b].add(a)


def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)

            stack.extend(graph[vertex] - visited)
    return visited

length = 0

for i in range(1, n+1):
    ans = dfs(t, i)
    if len(ans) > length:
        length = len(ans)

print(length)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def bfs(fd, n):
    visited = set()
    ans = 1
    for i in range(1, n + 1):
        if i in visited: continue
        volume = 1
        queue = deque(list(fd[i]))
        visited.add(i)
        while queue:
            x = queue.popleft()
            if x in visited: continue
            visited.add(x)
            volume += 1
            for l in fd[x]:
                if l not in visited and l not in queue:
                    queue.append(l)
        ans = max(ans, volume)
    return ans

if __name__ == "__main__":
    n, m = map(int, input().split())
    fd = {i+1:set() for i in range(n)}
    for _ in range(m):
        a, b = map(int, input().split())
        fd[a].add(b)
        fd[b].add(a)
    print(bfs(fd, n))

Submission status: Time Limit Exceeded

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

# D - Friends
def append_(A, B):
  global people

  people.setdefault(A, [])
  people[A].append(B)


def create_new_group(p):
  global groups

  group = set()
  group.add(p)

  groups.append(group)


def exists_friend(i, group):
  global friends

  for p in group:
    if i in friends[p]:
      return True


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

for i in range(M):
  A, B = map(int, input().split())
  append_(A, B)
  append_(B, A)

friends = dict()

for i in range(1, N + 1):
  friends[i] = set()

for k in people:
  for v in people[k]:
    friends[k].add(v)

    for f in people[v]:
      friends[k].add(f)

groups = []
create_new_group(1)

for i in range(2, N + 1):
  is_added = False

  for group in groups:
    if not exists_friend(i, group):
      group.add(i)
      is_added = True
      break

  if not is_added:
    create_new_group(i)

print(len(groups))

#for g in groups:
  #print(g)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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



f=lambda:map(int,input().split())
N,M=f()
uf=UnionFind(N+1)
for _ in range(M):
    a,b=f()
    uf.union(a,b)
    
print(max([len(i) for i in list(uf.all_group_members().values())]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n,m=map(int,input().split())
root=[-1]*(n+1)
def r(x):
    if root[x]<0:
        return x
    else:

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

    root[x]+=root[y]
    root[y]=x
def size(x):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())

    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i+1))
print(ans)

Submission status: Time Limit Exceeded

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

n,m=map(int,input().split())
root=[-1]*(n+1)
def r(x):
    if root[x]<0:
        return x
    else:

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

    root[x]+=root[y]
    root[y]=x
def size(x):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())

    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data)

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, m = I()

ppl = D(int)
grp = D(list)

for i in range(1, n+1):
    ppl[i] = i
    grp[i].append(i)

seen = []
for _ in range(m):
    a, b = I()

    if (a,b) in seen:
        continue
    else:
        seen.append((a,b))
        seen.append((b,a))

    ga, gb = ppl[a], ppl[b]
    if ga == gb:
        continue
    for p in grp[gb]:
        ppl[p] = ga
    grp[ga] += grp[gb]


print(np.max([len(p) for _, p in grp.items()]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data)

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, m = I()

ppl = D(int)
grp = D(list)

for i in range(1, n+1):
    ppl[i] = i
    grp[i].append(i)

for _ in range(m):
    a, b = I()
    ga, gb = ppl[a], ppl[b]
    if ga == gb:
        continue
    for p in grp[gb]:
        ppl[p] = ga
    grp[ga] += grp[gb]


print(np.max([len(p) for _, p in grp.items()]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F, sqrt
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data)

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, m = I()

ppl = D(int)
grp = D(list)

for i in range(1, n+1):
    ppl[i] = i
    grp[i].append(i)

for _ in range(m):
    a, b = I()
    ga, gb = ppl[a], ppl[b]
    if ga == gb:
        continue
    for p in grp[gb]:
        ppl[p] = ga
    grp[ga] += grp[gb]
    del grp[gb]

print(np.max([len(p) for _, p in grp.items()]))

Submission status: Time Limit Exceeded

Solution code:
data = input().split(" ")
N = int(data[0])
M = int(data[1])

if M == 0:
  print(1)
else:
  Comb = [0]*M
  List = []
  for i in range(M):
    buf = input().split(" ")
    buf[0] = int(buf[0])
    buf[1] = int(buf[1])
    List.extend(buf)
    Comb[i] = buf
  List = list(set(List))
  #print(Comb,List)

  for i in range(len(List)):
    buf = []
    num = len(Comb)
    for j in range(num):
      if List[i] in Comb[j]:
        buf.extend(Comb[j])
        Comb[j] = None
    buf = list(set(buf))
    Comb.append(buf)
    Comb = [i for i in Comb if i != None]
  #  print(Comb)

  for i in range(len(Comb)):
    Comb[i] = len(Comb[i])
  print(max(Comb))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
N,M=map(int,input().split(" ")) 
global count
count=0
Y=[] 
Z=[] 
A=set() 
for _ in range(M): 
    y,z=map(int,input().split()) 
    if y<z: 
        A.add((y,z)) 
    else: 
        A.add((z,y)) 
for i in A:
    Y.append(i[0]) 
    Z.append(i[1]) 
b=[int(i+1) for i in range(N)]

def g(x): 
    global count
    #print(Y,Z,b,count)
    try: 
        b.remove(x)
    except ValueError:
        return
        
    count+=1
    while x in Y: 
        s=Y.index(x) 
        t=Z[s] 
        del Y[s] 
        del Z[s] 
        g(t) 
    return 
result=0 
while b!=[]: 
    count=0 
    g(b[0]) 
    result=max(count,result) 
print(result)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

ARR = []

for i in range(M):
    ARR.append(list(map(int,input().split())))

def calculate(n,m,arr):
    unionFind = UnionFind(n)

    for i in range(m):
        startNode = arr[i][0] - 1
        endNode = arr[i][1] - 1
        unionFind.union(startNode, endNode)

    result = 0
    for item in unionFind.all_group_members().values():
        result = max(result,(len(item)))

    print(result)



calculate(N,M,ARR)

Submission status: Time Limit Exceeded

Solution code:
class UnionFindBySize():
    def __init__(self, n):
        self.parents = list(range(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):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x

    # 全ての要素の親を求める
    def calc_parents(self):
        self.parents = [self.find(i) for i in self.parents]

    # 根を出力する
    def roots(self):
        self.calc_parents()
        return list(set(self.parents))

    # rootを親として持つ
    def groupcounts(self, root):
        self.calc_parents()
        return self.parents.count(root)


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

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

groups = uf.roots()
counts = [uf.groupcounts(group) for group in groups]
print(max(counts))