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:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent,cnt):
    global MAX
    MAX = max(cnt,MAX)
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur,cnt)
    return

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1,cnt)
print(MAX)

Submission status: Time Limit Exceeded

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

fs = [list(map(int, input().split())) for i in range(m)]

g = [set([fs[0][0], fs[0][1]])]
for a, b in fs[1:]:
    f = 0
    for j in g:
        if a in j or b in j:
            f = 1
            j.add(a)
            j.add(b)
            break
    if f == 0:
        g.append(set([a, b]))

ans = 0
for i in g:
    ans = max(ans, len(i))
print(ans)

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())
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)
agm = uf.all_group_members()
ufr = uf.roots()
ans = 0
for i in ufr:
    ans = max(ans,len(agm[i]))
print(ans)

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

def resolve():
    N, M = list(map(int, input().split()))
    uf = UnionFind(N)
    for i in range(M):
        a, b = list(map(int, input().split()))
        uf.union(a-1, b-1)
    maxnum = 0
    for _, v in uf.all_group_members().items():
        maxnum = max(maxnum, len(v))
    print(maxnum)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ls = [0 for _ in range(N)]
flg = 1
for i in range(M):
    a,b = map(int,input().split())
    if ls[a-1] == 0 and ls[b-1] == 0:
        ls[a-1]=flg
        ls[b-1]=flg
        flg+=1
    elif ls[a-1] == 0:
        ls[a-1] = ls[b-1]
    elif ls[b-1] == 0:
        ls[b-1] = ls[a-1]
    else:
        check = ls[b-1]
        ls[b-1] = ls[a-1]
        for l in range(len(ls)):
            if ls[l] == check:
                ls[l]=ls[a-1]
import collections
c = collections.Counter(ls)
plan = c.most_common()
ans = 0
if plan[0][0] == 0 and M != 0:
    ans = plan[1][1]
elif M ==0:
    ans =1
else:
    ans = plan[0][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(s) for s in input().split()] 
hito=[-1 for i in range(N)]
edge=[set() for _ in range(N)]
for i in range(M):
  a,b=[int(s) for s in input().split()]
  edge[a-1].add(b-1)
  edge[b-1].add(a-1)


def dfs(start):
  count=1
  reach=[start]
  hito[start]=1
  while reach:
    _from=reach.pop(0)
    for _to in edge[_from]:
      if not(_to in reach) and hito[_to]==-1:
        reach.append(_to)
        count+=1
        hito[_to]=1
  return(count)
 

ans=set()
for h in range(N):
  if hito[h]==-1:
    ans.add(dfs(h))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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

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

for i in range(M):
    A,B=map(int,input().split())
    if A not in D[B]: D[B].append(A)
    if B not in D[A]: D[A].append(B)

for i in range(1,N+1):
    for f in D[i]:
        for ff in D[f]:
            if ff != i:
                if ff not in D[i]: D[i].append(ff)


ans=0
for i in range(1,N+1):
    L=len(D[i])+1
    if L>ans: ans=L

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
if m == 0:
  print(1)
  quit()
if m == 1:
  print(2)
  quit()
a,b = map(int,input().split())
sets = [set([a,b])]
for i in range(m-1):
  a,b = map(int,input().split())
  for s in sets:
    if (a in s) or (b in s):
      s.add(a)
      s.add(b)
      break
    else:
      sets.append(set([a,b]))
ans = 0
for s in sets:
  ans = max(ans,len(s))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split()]
Groups = [{i} 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 == src:
        continue
    dsts[src] = dst
    Groups[dst] = Groups[dst] | Groups[src]
    Groups[src] = {}
    # print(Groups)
    # print(dsts)
ans = 0
for group in Groups:
    ans = max(ans, len(group))
print(ans)

Submission status: Time Limit Exceeded

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

import networkx as nx

G = nx.Graph()
G.add_nodes_from(range(n))
for ppp in range(m):
    i,j= list(map(int, input().split()))
    i-=1
    j-=1
    G.add_edge(i,j)   
max_size = 0
for component in nx.connected_components(G):
        if len(component) > max_size:
                max_cluster = component
                max_size = len(max_cluster)

print(len(max_cluster))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n, m = map(int, input().split())
ab = np.array([[0] * n] * n)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ab[a][b] = 1
    ab[b][a] = 1
ans = 0
for i in range(n):
    ans = max(sum(ab[i]), ans)
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
from pprint import pprint

if __name__ == '__main__':
    N, M = list(map(lambda x: int(x), sys.stdin.readline().split()))
    matrix = [[0 for i in range(N)] for j in range(N)]
    for _ in range(M):
        a, b = list(map(lambda x: int(x), sys.stdin.readline().split()))
        matrix[a-1][b-1] = 1
        matrix[b-1][a-1] = 1

    # つながっている最大のグラフを求めればいい
    print(max([sum(matrix[i]) for i in range(N)])+1)

Submission status: Time Limit Exceeded

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

n,m=map(int, input().split())
list=[]
list2=[]
count=0
for i in range(m):
 list.append([])
 a,b=map(int,input().split())
 list[i].append(a)
 list[i].append(b)
for i in range(n):
  list2.append(0)

for i in range(len(list)):
  list[i].sort()
  for g in range(len(list)):
    if list[i][0]==list[g][0] and list[i][1]!=list[g][1]:
      list.append([list[i][1],list[g][1]])
  
for i in range(len(list)):
  if list2[list[i][0]-1]==list2[list[i][1]-1]:
    list2[list[i][1]-1]+=1
for i in range(20000):
  if i in list2:
    count+=1
print(count)

Submission status: Time Limit Exceeded

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

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

def main():
    N, M = map(int, input().split())
    C = []
    for i in range(M):
        a, b = map(int, input().split())
        p = min(a, b)
        q = max(a, b)
        C.append([p,q])
    D = get_unique_list(C)
    # print(D)

    # C = [list(map(int, input().split())) for i in range(M)]

    # F = [[0]*(N+1) for i in range(N+1)]
    F = [1]*(N+1)
    for a, b in D:
        F[a] += 1
        F[b] += 1
    # for a,b in D:
    #     if F[a][b] == 0:
    #         F[a][b] += 1
    #     if F[b][a] == 0:
    #         F[b][a] += 1
    # G = [1]*(N+1)
    # for i in range(N+1):
    #     G[i] = sum(F[i])
    ans = max(F)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

graph = [[] for _ in range(n+1)]
tmp = 0
for i in range(m):
  a, b = map(int, input().split())
  for j in range(tmp+1):
    if a in graph[j] and b in graph[j]:
      break
    elif b in graph[j] and a not in graph[j]:
      graph[j].append(a)
      break
    elif a in graph[j] and b not in graph[j]:
      graph[j].append(b)
      break
    else:
      if j == tmp:
        graph[tmp].append(a)
        graph[tmp].append(b)
        tmp += 1
      else:
        continue
  
for i in range(n+1):
  graph[i] = len(graph[i])

print(max(graph))

Submission status: Time Limit Exceeded

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

group = [set([i]) for i in range(N)]
syozoku = [i for i in range(N)]


for a,b in AB:
  a -= 1
  b -= 1
  group[syozoku[a]] = group[syozoku[a]] | group[syozoku[b]]
  x = group[syozoku[b]].copy()
  if syozoku[a]!=syozoku[b]:
  	group[syozoku[b]] = set([])
  for i in x:
    syozoku[i] = syozoku[a]
  
ans = 0
for i in range(N):
  ans = max(len(group[i]),ans)
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  n, m = map(int, input().split())
  graph = [[] for _ in range(n)]

  for i in range(m):
    a, b = map(int, input().split())
    if b-1 not in graph[a-1]:
      graph[a-1].append(b-1)
      graph[b-1].append(a-1)
  
  searched = []
  result = 0
  while len(searched) != n:
    for i in range(n):
      if i not in searched:
        s = i
        break
    tmp, cnt = dfs(graph, s)
    searched += tmp
    if cnt > result:
      result = cnt
      
  print(result)

def dfs(graph, s):
  stack = deque([s])
  searched = [s]
  while len(stack):
    cur = stack.pop()
    for i in graph[cur]:
      if i not in searched:
        stack.append(i)
        searched += [i]
  return searched, len(searched)

main()

Submission status: Time Limit Exceeded

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

x = [{i} for i in range(n)]

def search(k):
    for i in range(len(x)):
        if k in x[i]:
            return i

for i in range(m):
    v = search(a[i][0]-1)
    u = search(a[i][1]-1)
    if (v != u):
        x[v].update(x[u])
        del x[u]

ml = 0
for i in x:
    if len(i) > ml:
        ml = len(i)

print(ml)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
k=[1]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    for i in range(1,n+1):
        if i==a or i==b:
            k[i]+=1
if max(k)>n:
    print(n)
else:
    print(max(k))

Submission status: Time Limit Exceeded

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

# print('input >>')
N, M = map(int,(input().split()))
ABs = []
for _ in range(M):
    ABs.append(tuple(map(lambda x:int(x)-1,(input().split()))))

uf = UnionFind(N)
for AB in ABs:
    A, B = AB
    uf.union(A, B)
    
members = uf.all_group_members()

ans = 0
for member in members.values():
    ans = max(ans, len(member))

# print('-----output-----')
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    frd=[[0]]
    #print(frd)
    for i in range(m):
        a,b=INTM()
        flg=True
        for k in range(len(frd)):
            if ((a in frd[k])or(b in frd[k])):
                if not(a in frd[k]):
                    frd[k].append(a)
                if not(b in frd[k]):
                    frd[k].append(b)
                flg=False
                break
        if flg:
            frd.append([a,b])
            
                
    #print(frd)
    ans=1
    for i in range(len(frd)):
        ans=max(ans,len(frd[i]))
    
    print(ans)

                
if __name__=='__main__':
    do()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
G = [[] for i in range(n)]
C = [[]for i in range(n)]
for _ in range(m):
    A, B = map(int, input().split())
    tmp = [A,B]
    tmp2 = [B,A]
    if tmp in C or tmp2 in C:
        continue
    else:
        C.append(tmp)
        G[A-1].append(B-1)
        G[B-1].append(A-1)
ans = 0
for i in range(len(G)):
    ans = max(len(G[i]),ans)
print(ans +1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
friends = [0 for i in range(n)]
relation = [[False for i in range(n)] for j in range(n)]

for i in range(m):
  a, b = map(int, input().split())
  if not relation[a - 1][b - 1]:
    relation[a - 1][b - 1] = True
    relation[b - 1][a - 1] = True
    friends[a - 1] += 1
    friends[b - 1] += 1

print(max(friends) + 1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
Friend = list(range(N))
for i in range(M):
    A, B = map(int, input().split())
    a = A-1
    b = B-1
    if(B < A):
        a = B-1
        b = A-1
    for j in range(N):
        if(Friend[j] == Friend[b]):
            Friend[j] = Friend[a]
sF = sorted(Friend)
now = 0
count = 0
cmax = 0
for i in range(N):
    if(sF[i] == now):
        count += 1
        if(count > cmax):
            cmax = count
    else:
        now = sF[i]
        if(count > cmax):
            cmax = count
        count = 1
print(cmax)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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 members(self, x):
    #    root = self.find(x)
    #    return [i for i in range(self.n) if self.find(i) == root]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def roots(self):
        #全ての根の要素のリスト
        return [i for i, x in enumerate(self.parents) if x<0]
    def group_count(self):
        #グループの数
        return len(self.roots())
    def members(self, x):
        root = self.find(x)
        return len([i for i in range(self.n) if self.find(i) == root])
    #def __str__(self):
    #   return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=reads()
uf=UnionFind(n)
a,b=[0 for i in range(m)],[0 for i in range(m)]
for i in range(m):
    a,b=reads()
    uf.unite(a-1,b-1)
ls=uf.roots()
max=0
y=0
for l in ls:
    y=uf.members(l)
    if max<y:
        max=y
print(max)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
friend = [1 for i in range(N)]
k = []

for i in range(M):
    A, B = map(int, input().split())
    if [A, B] not in k:
        friend[A-1] += 1
        friend[B-1] += 1
        k.append([A, B])
        k.append([B, A])

print(max(friend))

Submission status: Time Limit Exceeded

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

    def getParents(self):
        return self.parents

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



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

roots = friend.all_group_members()
ans = -1
for x in roots.values():
    ans = max(ans, len(x))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
index = 0
MAX = 0
def dfs(fr,cur,parent,cnt):
    global MAX
    MAX = max(cnt,MAX)
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur,cnt)

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1,cnt)
    MAX = max(MAX,cnt)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
li = [[] for i in range(N+1)]
for i in range(M):
  a, b = map(int, input().split())
  li[a].append(b)
  li[b].append(a)
  
ans = 0
for i in range(1, N+1):
  l = li[i]
  for x in li[i]:
    for y in li[x]:
      if y == i:
        pass
      elif y in li[i]:
        pass
      else:
        l.append(y)
  ans = max(ans, len(set(l))+1)
print(ans)

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 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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = list(map(int, input().split()))
uf = UnionFind(n)

for i in range(m):
    x, y = list(map(int, input().split()))
    uf.union(x-1, y-1)

cnt = max([len(uf.members(r)) for r in uf.roots()])
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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 m in range(M):
    temp = [int(i)-1 for i in input().split()]
    uf.union(temp[0],temp[1])

group_dict = uf.all_group_members()
ans = 0
for key in group_dict.keys():
    ans = max(ans,len(group_dict[key]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) 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 size(self, x):
        return -self.parents[self.find(x)]

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
      
uf = UnionFind(n+1)
for i in range(m):
  uf.union(ab[i][0], ab[i][1])
ans=0
for i in range(uf.group_count()):
  if ans < len(uf.members(i)):
    ans = len(uf.members(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
pair = list(map(lambda x: int(x), input().split()))

peer = [[0 for j in range(pair[0])] for i in range(pair[0])]
for i in range(pair[1]):
  pa = sorted(list(map(lambda x: int(x), input().split())))
  peer[pa[0]-1][pa[1]-1] = 1
  
pairs = [sum(i)+1 for i in peer]
print(max(pairs))

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])



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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n,m = inpm()
AB = inplt(m)

uf = UnionFind(n)
for a,b in AB:
    uf.union(a-1,b-1)

ans = 0
for x in uf.all_group_members().values():
    ans = max(ans,len(x))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
ls = [0 for _ in range(N)]
flg = 1
for i in range(M):
    a,b = map(int,input().split())
    if ls[a-1] == 0 and ls[b-1] == 0:
        ls[a-1]=flg
        ls[b-1]=flg
        flg+=1
    elif ls[a-1] == 0:
        ls[a-1] = ls[b-1]
    elif ls[b-1] == 0:
        ls[b-1] = ls[a-1]
    else:
        x = ls.count(ls[a-1])
        y = ls.count(ls[b-1])
        if x >= y:
            check = ls[a-1]
        else:
            check = ls[b-1]
        ls[a-1] = check
        ls[b-1] = check
import collections
c = collections.Counter(ls)
plan = c.most_common()
ans = 0
if plan[0][0] == 0 and M != 0:
    ans = plan[1][1]
elif M ==0:
    ans =1    
else:
    ans = plan[0][1]
print(ans)