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:
n, m = list(map(int, input().split()))
am = []
bm = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    am.append(a)
    bm.append(b)

groups = []
for ai, bi in zip(am, bm):
    ag = None
    bg = None
    for g, group in enumerate(groups):
        if ai in group:
            ag = g
        if bi in group:
            bg = g
    if ag is None:
        if bg is None:
            groups.append([ai, bi])
        else:
            groups[bg].append(ai)
    else:
        if bg is None:
            groups[ag].append(bi)
        else:
            if ag != bg:
                groups[ag].extend(groups[bg])
                del groups[bg]

# max_gr_len = 1
# for group in groups:
#     if max_gr_len < len(group):
#         max_gr_len = len(group)
max_gr_len = max([len(group) for group in groups] + [1])

print(max_gr_len)

Submission status: Time Limit Exceeded

Solution code:
n, m = [int(e) for e in input().split()]

d = {}

t = set()

for i in range(m):
    a, b = [int(e) for e in input().split()]
    
    if a > b:
        a, b = b, a
    if (a, b) in t:
        continue
    t.add((a,b))
    
    if not a in d:
        d[a] = set([a])
    if not b in d:
        d[b] = set([b])    

    if len(d[a]) > len(d[b]):
        for i in d[b] - d[a]:
            if i != b:
                d[i] = d[a]
        d[a].update(d[b])
        d[b] = d[a]
        d[a].add(b)
    else:
        for i in d[a] - d[b]:
            if i != a:
                d[i] = d[b]
        d[b].update(d[a])
        d[a] = d[b]
        d[b].add(a)

r = 1
for v in d.values():
    if len(v) > r:
        r = len(v)

print(r)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

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

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

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

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

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

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

In = InputHelper()
Out = OutputHelper()

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

N, M = In.ints()

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

        A-=1
        B-=1

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

            #dfs
            stck = [(i,1)]
            ct = 1
            while len(stck)>0:
                now, way = stck.pop(0)
                
                

                for nex in conns[now]:
                    if nex not in seen:
                        ct+=1
                        seen.add(nex)
                        ans = max(ans, ct)
                        stck.append((nex,way+1))
                    

    Out.int(ans)
        




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

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

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, input().split())
    ans = 1
    if M > 0:
        a, b = map(int, input().split())
        groups = []
        groups.append({a, b})
        for _ in range(1, M):
            a, b = map(int, input().split())
            flag = True
            for g in groups:
                if a in g:
                    g.add(b)
                    flag = False
                if b in g:
                    g.add(a)
                    flag = False
            if flag:
                groups.append({a, b})

        for g in groups:
            ans = max(ans, len(g))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
from collections import deque


def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

N,M = LI()
AB = [LI() for _ in range(M)]

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

# 無向グラフ
G = []
for _ in [0]*N:
    G.append([False]*N)

for r in AB:
    f = r[0]-1
    t = r[1]-1
    G[f][t] = True
    G[t][f] = True

used = [False] * N

ss = []
for i in range(N):
    if used[i]==True:
            continue
    s = set()
    que = deque([])
    que.append(i)
    while que:
        p = que.popleft() 
        if used[p]==True:
            continue
        s.add(p)
        used[p]=True   
        for i, x in enumerate(G[p]):
            if x == True:
                if used[i]==True:
                    continue
                if not i in que:
                    que.append(i)
    ss.append(len(s))


    # for i, x in enumerate(G[i]):
    #     if x == True:
    #         if used[i]==True:
    #             continue
    #         for j,y in enumerate(x):
    #             if used[j]==True:
    #                 continue
    #             if x == True and used[i]==False:
    #                 s.add(i)


    # l = [i for i, x in enumerate(G[i]) if x == True and used[i]==False]
    # for j in l:
    #     used[j]=True
    #     s.add(j)
    #     for i,x in enumerate(G[i]):
    #         if x == True and used[i]==False:
    #             s.add(i)

print(max(ss))

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 group_count(self):
        return len(self.roots())
    
    def max_group_length(self):
        tmp_max = 0
        for r in self.roots():
            tmp_max = max(tmp_max, len(self.members(r)))
        return tmp_max

    def __str__(self):
        return str(self.max_group_length())
    
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 = str(uf)
print(ans)

Submission status: Time Limit Exceeded

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

def sagasu(t):
  ze = []
  itta[t-1] = 1
  for i in range(m):
    if a[i] == t and itta[b[i]-1] != 1:
      ze.append(b[i])
      itta[b[i]-1] = 1
    elif b[i] == t and itta[a[i]-1] != 1:
      ze.append(a[i])
      itta[a[i]-1] = 1
  return ze

z = [1]
gokei = 0
qa = 0
while qa <= n:
  if itta.count(0) == 0:
    break
  z = [(itta.index(0)) + 1]

  for i in z:
    kaku = sagasu(i)
    if len(kaku) == 0:
      break
    z.extend(kaku)
    
  if gokei<len(z):
    gokei = len(z)
  qa += 1
print(gokei)

Submission status: Time Limit Exceeded

Solution code:
n, m = map( int, input().split() )
a = []
b = []
friend = [ [] for _ in range( n ) ]
for _ in range( m ):
    a_i, b_i = map( int, input().split() )
    a.append( a_i - 1 )
    b.append( b_i - 1 )
    friend[ a_i - 1 ].append( b_i - 1 )
    friend[ b_i - 1 ].append( a_i - 1 )

group = [ -1 for _ in range( n ) ]
group_id = 0
queue = [ i for i in range( n ) ]
visited = [ 0 for _ in range( n ) ]

while len( queue ) > 0:
    i = queue.pop( 0 )
    if visited[ i ] == 1:
        continue
    visited[ i ] = 1
    if group[ i ] == -1:
        group[ i ] = group_id
        group_id += 1
    for j in friend[ i ]:
        group[ j ] = group[ i ]
        queue.insert( 0, j )

num_v = [ 0 for _ in range( n ) ]
for i in range( n ):
    num_v[ group[ i ] ] += 1

# print( group )
# print( num_v )
print( max( num_v ) )

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
n,m = list(map(int, input().split()))

d = defaultdict(set)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].add(b)
    d[b].add(a)
    
visited = set()

def dfs(node):
    
    c = 0
    stack = deque([node])
    s = set()
    while stack:
        n = stack.popleft()
        c += 1
        visited.add(n)
        s.add(n)
        for i in d[n]:
            if i not in visited:
                stack.append(i)
                
    return len(s)
    

ans = 1

for key in list(d.keys()):
    if key not in visited:

        c = dfs(key)
        ans = max(ans, c)
        


print(ans)

Submission status: Time Limit Exceeded

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

grpno=[i for i in range(N)]
ngrp=[1 for i in range(N)]
# members=[[i] for i in range(N)]

ngrp_max=1

for i in range(M):
    p,q = list(map(int,input().split()))

    if grpno[p-1] > grpno[q-1]:
        r = p
        p = q
        q = r
    
    if grpno[p-1] != grpno[q-1]:
        ngrp[grpno[p-1]] += ngrp[grpno[q-1]]
        ngrp[grpno[q-1]] = 0

        to_remove = grpno[q-1]
        for j in range(N):
            if grpno[j] == to_remove:
                grpno[j] = grpno[p-1]            
                   

        if ngrp_max < ngrp[grpno[p-1]]:
            ngrp_max = ngrp[grpno[p-1]]
   
        # members[p-1] += members[q-1]

# for i in range(N):
#     print("i=",i)
#     print(members[i])
#     print("group_no=",grpno[i])
#     print("#member=",ngrp[i])

print(ngrp_max)

Submission status: Time Limit Exceeded

Solution code:
from __future__ import print_function
range = xrange
input = raw_input





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




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

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

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

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

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

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

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


   
    cd=0
    p=sum(x)
    while p!=0:
        for i in range(len(x)):
            if x[i]>0:
                x[i]-=1
                p-=1
        cd+=1
    print(cd)
        
        
    
for _ in range(1):
    solve()

Submission status: Time Limit Exceeded

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 _ in range(M):
    A, B = map(int, input().split())
    A = A - 1
    B = B - 1
    uf.union(A, B)
    uf.find(A)

ans = 0
for k, v in uf.all_group_members().items():
    ans = max(ans, len(v))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ed = [0] * (n+1)


def rm(nu):
    if len(vr) == 0:
        return 0
#    print(vr)
    if nu not in vr:
        return 0
    curr = vr.pop(vr.index(nu))
#    print(curr)
    if ed[curr] == 0:
        return 1
    else:
        tmp = 1
#        print(f"2edc:{ed[curr]}")
        for p in ed[curr]:
            tmp += rm(p)
#            print(f"tr:{tmp}")
#        print(f"ftmp:{tmp}")
        return tmp


for i in range(m):
    t1, t2 = map(int, input().split())
    if ed[t1] == 0:
        ed[t1] = [t2]
    else:
        if t2 not in ed[t1]:
            ed[t1].append(t2)
    if ed[t2] == 0:
        ed[t2] = [t1]
    else:
        if t1 not in ed[t2]:
            ed[t2].append(t1)
vr = list(range(n, 0, -1))
maxs = 0
#print(vr, ed)
itr = 0
while len(vr) != 0 and itr < n + 100:
    itr += 1
    maxs = max(maxs, rm(vr[-1]))
print(maxs)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
t = [-1*(i+1) for i in range(n)]
count = 0
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    if t[a] <= -1 and t[b] <= -1:
        count += 1
        t[a] = count
        t[b] = count
        continue
    if t[a] > -1 and t[b] > -1 and t[a] != t[b]:
        max_t = max(t[a], t[b])
        min_t = min(t[a], t[b])
        t[a] = max_t
        t[b] = max_t
        for i in t:
            if i == min_t:
                i = max_t
        continue
    if t[a] > -1 and t[b] > -1 and t[a] == t[b]:
        continue
    if t[a] <= -1:
        t[a] = t[b]
        continue
    if t[b] <= -1:
        t[b] = t[a]

print(
    max([t.count(i) for i in set(t)])
)

Submission status: Time Limit Exceeded

Solution code:
def packrel(s: str):
    x, y = map(int, s.split())
    if (x < y):
        return (x, y)
    else:
        return (y, x)


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

rels = {packrel(input()) for i in range(M)}

unions = [set((-1,))]
index = [-1] * (N + 1)

for a, b in rels:
    if index[a] != -1:
        unions[index[a]].add(b)
        index[b] = index[a]
        continue
    if index[b] != -1:
        unions[index[b]].add(a)
        index[a] = index[b]
        continue

    for i, u in enumerate(unions):
        if a in u:
            u.add(b)
            index[b] = index[a]
            break
        if b in u:
            u.add(a)
            index[a] = index[b]
            break
    else:
        x = set((a, b))
        c = len(unions)
        index[a] = index[b] = c
        unions.append(x)

z = max(len(x) for x in unions)
print(z)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import math

class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

N, M = map(int,input().split())
AB=[]
for i in range(M):
    At, Bt= map(int,input().split())
    Ac = 0
    Bc = 0
    if At > Bt:
        Ac = Bt
        Bc = At
    else:
        Ac = At
        Bc = Bt
    if not (Ac, Bc) in AB:
        AB.append((Ac,Bc))

uf = UnionFindVerSize(N)
for t in AB:
    uf.unite(t[0]-1,t[1]-1)
c = 0
for i in range(uf.calc_group_num()):
    if c < uf.get_size(i):
        c = uf.get_size(i)

print(c)
#N = int(input())
#C = input()
#D, T, S=map(int,input().split())
#C = []
#for i in range(N):
#    C.append(list(map(int,input().split())))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
li = [0]*(n+1)
lii = []
flag = 1
for _ in range(m):
    a, b = map(int, input().split())
    if li[a] and li[b]:
        if li[a] != li[b]:
            lii.append([li[a], li[b]])
    elif li[a] or li[b]:
        s = max(li[a],li[b])
        li[a] = s
        li[b] = s
    else:
        li[a] = flag
        li[b] = flag
        flag += 1
for i in range(len(li)):
    if li[i] == 0:
        li[i] = -i
for i in lii:
    a,b = i[0],i[1]
    for j in range(len(li)):
        if li[j] == a or li[j] == b:
            li[j] = a+b
            
from collections import Counter
result = Counter(li)
print(result.most_common(1)[0][1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
uniquePair = set()
for i in range(m):
  a, b = map(int, input().split())
  uniquePair.add((a, b) if(a<b) else (b, a))
uniquePair = sorted(uniquePair, key = lambda x:x[0])
masterGroup = [{1}]
for a, b in uniquePair:
  inGroup = False
  for group in masterGroup:
    if(a in group or b in group):
      inGroup = True
      group.add(a)
      group.add(b)
      break
    else:
      continue
  if(not inGroup):
  	masterGroup.append({a, b})
result = 0
for i in masterGroup:
  result = max(result, len(i))
print(result)

Submission status: Time Limit Exceeded

Solution code:
N,M=list(map(int, input().split()))
A = [0] * M
B = [0] * M
li=[]
for i in range(M):
    A[i], B[i] = list(map(int, input().split()))
    ma = A[i] if A[i] > B[i] else B[i]
    mi= B[i] if A[i] > B[i] else A[i]
    li.append([mi,ma])
F=[0]*N

seen = []
simple_list=[x for x in li if x not in seen and not seen.append(x)]



import numpy as np
simple_list=np.array(simple_list)
simple_list=simple_list.ravel()

for i in range(N):
    F[i]+=list(simple_list).count(i+1)
print(max(F)+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def dfs(node):
    while len(todo) > 0:
        node = todo.pop()
        if tf[node] == 0:
            tf[node] = 1
            seen.add(node)
            for nextnode in graph[node]:
                todo.append(nextnode)

todo = deque()
done = set()
for i in range(1,n+1):
    if i in done:
        continue
    else:
        todo.append(i)
        tf = [0 for _ in range(n+1)]
        seen = set()
        dfs(i)
        ans = max(ans,len(seen))
        done |= seen
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
if m == 0:
  print(1)
elif m == 1:
  print(2)
else:
  ls=[]
  a,b = map(int, input().split())
  tmp = {a, b}
  ls.append(tmp)
  for i in range(m-1):
    a,b = map(int, input().split())
    for s in ls:
      if (a in s) or (b in s):
        s.add(a)
        s.add(b)
        break
      else:
        tmp = {a,b}
        ls.append(tmp)

  ans = 0
  for s in ls:
    ans = max(ans, len(s))
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n, m = map(int, input().split())
# # arr = [tuple(map(int, input().split())) for _ in range(m)]

f = {a: set() for a in range(1, n+1)}
for _ in range(m):
    x, y = map(int, input().split())
    f[x].add(y)
    f[y].add(x)

res = 0
visited = set()
stack = deque()
for i in range(1, n+1):
    if i in visited:
        continue
    visited = {i}
    stack = deque([i])
    while stack:
        c = stack.pop()
        for v in f[c]:
            if v not in visited:
                visited.add(v)
                stack.append(v)
    res = max(res, len(visited))

print(res)

# f = []
# for _ in range(m):
#     x, y = map(int, input().split())
#     for f_ in f:
#         if x in f_ or y in f_:
#             f_.update((x, y))
#             break
#     else:
#         f.append({x, y})

# if m == 0:
#     print(1)
# else:
#     print(max([len(f_) for f_ in f]))

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)
#list2=[[0] for i in range(n)]
for i in range(n):
  list2.append(0)
i=0
  
while m>i:
  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]])
      m+=1
  if list2[list[i][0]-1]==list2[list[i][1]-1]:
    list2[list[i][1]-1]+=1
  i+=1
for i in range(n):
  if i in list2:
    count+=1
  else:
    break
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M = list(map(int, input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]

checker = []

detacheck = [0 for _ in range(N)]


#for AB in ABs:
#    checker[AB[0] - 1].add(AB[1])
#    checker[AB[1] - 1].add(AB[0])

tmp = 0
for AB in ABs:
#    print(detacheck)
    if(detacheck[AB[0] -1] == 0 and detacheck[AB[1] -1] == 0):
        checker.append(set(AB))
        tmp += 1
        detacheck[AB[0] - 1] = tmp
        detacheck[AB[1] - 1] = tmp


    elif(detacheck[AB[0] -1] == 0 or detacheck[AB[1] -1] == 0):
#        print(detacheck[AB[0] -1] , detacheck[AB[1] -1])
        checker[max(detacheck[AB[0] -1]-1,detacheck[AB[1] -1]-1)].add(AB[0])
        checker[max(detacheck[AB[0] -1]-1,detacheck[AB[1] -1]-1)].add(AB[1])

        detacheck[AB[0] - 1] = max(detacheck[AB[0] - 1],detacheck[AB[1] - 1])
        detacheck[AB[1] - 1] = max(detacheck[AB[0] - 1],detacheck[AB[1] - 1])

    else:
#        print(AB[0], AB[1])
        checker[detacheck[AB[0] -1]-1] = checker[detacheck[AB[0] -1]-1].union(checker[detacheck[AB[1] -1]-1])
        for i in checker[detacheck[AB[1] -1]-1]:
            detacheck[i-1] =  detacheck[AB[0] - 1]
#    print(checker)

ans = 1

for anscheck in checker:
#    print(anscheck, len(anscheck))
    ans = max(ans, len(anscheck))


print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inp():
    return input()
def iinp():
    return int(input())
def inps():
    return input().split()
def miinps():
    return map(int,input().split())
def linps():
    return list(input().split())
def lmiinps():
    return list(map(int,input().split()))
def lmiinpsf(n):
    return [list(map(int,input().split()))for _ in range(n)]

n,m = miinps()
a = lmiinpsf(m)

k = [1]

ans1 = 1
ans = 1

d = []
D = [True]*n
D[0] = False

for i in range(n):
  d.append(i)

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

for i in range(m):
  b[a[i][0]-1].append(a[i][1])
  b[a[i][1]-1].append(a[i][0])

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

d.remove(0)
  
while d != 0:
  for i in range(len(k)):
    y = k.pop(0)
    x = b[y-1]
    for j in range(len(x)):
      if D[x[j]-1]:
        d.remove(x[j]-1)
        D[x[j]-1] = False
        ans += 1
        k.append(x[j])
  if not k :
    ans1 = max(ans,ans1)
    ans = 0
    if not d:
      break
    k.append(d[0])
    z = d.pop(0)
    D[z] = False

ans1 = max(ans,ans1)
print(ans1)

Submission status: Time Limit Exceeded

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

c = []
flag = False
for i in ab:
    a, b = i[0], i[1]
    for i in c:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            if len(i) == n:
                flag = True
            break
    else:
        c.append(set())
        c[-1].add(a)
        c[-1].add(b)
    if flag:
        break
if m == 0:
    print(1)
else:
    print(max(map(len, c)))

Submission status: Time Limit Exceeded

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

frends = []

for i in range(m):
  a,b = map(int, input().split())
  ainclude = set()
  binclude = set()
  flag = False
  for j in frends:
    if a in j:
      if b in j:
        flag = 'Y'
      ainclude = j
      frends.remove(j)
      flag = True
    elif b in j:
      binclude = j
      frends.remove(j)
      flag = True
  if flag == False:
    frends.append({a,b})
  elif flag == 'Y':
    continue
  else:
    c = {a,b}
    frends.append(ainclude|binclude|c)

cnt = 1

for i in frends:
  num = len(i)
  if cnt < num:
    cnt = num


print(cnt)

Submission status: Time Limit Exceeded

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

import networkx as nx

g = nx.Graph()
g_list = []
s_list = []
for i in range(M):
    b, c = map(int, input().split())
    
    if b in g_list and c in g_list:
        continue
    
    g_list.append(b)
    g_list.append(c)
    
    if b not in s_list and c not in s_list:
        s_list.append(b)
    
    g.add_edges_from([(b,c)])
    
g_list = list(set(g_list))
result = 1
for n in s_list:
    tmp = len(nx.single_source_shortest_path(g, n).keys())
    if result < tmp:
        result = tmp
print(result)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
t = [-1*(i+1) for i in range(n)]
count = 0
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    if t[a] <= -1 and t[b] <= -1:
        count += 1
        t[a] = count
        t[b] = count
        continue
    if t[a] > -1 and t[b] > -1 and t[a] != t[b]:
        max_t = max(t[a], t[b])
        min_t = min(t[a], t[b])
        t[a] = max_t
        t[b] = max_t
        for i in range(n):
            if t[i] == min_t:
                t[i] = max_t
        continue
    if t[a] > -1 and t[b] > -1 and t[a] == t[b]:
        continue
    if t[a] <= -1:
        t[a] = t[b]
        continue
    if t[b] <= -1:
        t[b] = t[a]

print(
    max([t.count(i) for i in set(t)])
)

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 all_group_members(self):
        return {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)

ans = 0
for i in list(uf.all_group_members().values()):
  ans = max(len(i),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力
N, M = list(map(int, input().split()))

A = []
B = []

for i in range(M):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

max_group = 0
tmp_set = set()

for i in range(N):
    if(tmp_set.isdisjoint({i})):
        group = set([i])
        for j in range(M):
            if (A[j] == i and B[j] != i):
                group.add(B[j])
                tmp_set.add(B[j])
            if (A[j] != i and B[j] == i):
                group.add(A[j])
                tmp_set.add(A[j])
        if (max_group < len(group)):
            max_group = len(group)
print(max_group)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
li=deque([])
ans=0
if m!=0: 
    for i in range(m):
        a,b=map(int,input().split())
        if len(li)==0:
            li.append([a,b])
        else:
            flag=0
            for j in range(len(li)):
                if a in li[j] or b in li[j]:
                    li[j].append(a)
                    li[j].append(b)
                    flag=1
                elif flag==0 and j==len(li)-1:
                    li.append([a,b])
        #print(li)
    ans=max([len(set(li[i])) for i in range(len(li))])
print(ans if m!=0 else 1)