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 = map(int, input().split())
A = list()
B = list()
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

largest = 1
group = []
people = [-1] * N
for a, b in zip(A, B):
    if people[a] != -1 and people[b] != -1 and people[a] != people[b]:
        group[people[a]] |= group[people[b]]
        for gb in group[people[b]]:
            people[gb] = people[a]
    elif people[a] != -1:
        people[b] = people[a]
        group[people[a]].add(b)
    elif people[b] != -1:
        people[a] = people[b]
        group[people[b]].add(a)
    else:
        group.append(set([a, b]))
        people[a] = len(group)-1
        people[b] = people[a]
    largest = max(len(group[people[a]]), largest)

print(largest)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
friend = [[]]
for i in range(m):
  a, b = map(int,input().split())
  for j in range(len(friend)):
    if a in friend[j] and b in friend[j]:
      break
    elif a in friend[j] and not b in friend[j]:
      friend[j].append(b)
      break
    elif b in friend[j]:
      friend[j].append(a)
      break
    elif j == len(friend)-1:
      friend.append([a,b])
ans = 1
for i in range(len(friend)):
  ans = max(ans,len(friend[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = map(int, input().split())
rinsetu = [set() for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, (input().split()))
    rinsetu[a].add(b)
    rinsetu[b].add(a)

grp = []
color = ["white"] * (N + 1)
color[0] = "black"
for i in range(1, N + 1):
    if color[i] == "white":
        d = deque()
        d.append(i)
        a = set()
        a.add(i)
        while (d):
            k = d.popleft()
            color[k] = "black"
            for j in rinsetu[k]:
                if color[j] == "white":
                    d.append(j)
                    a.add(j)
        grp.append(len(a))
print(max(grp))

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 and b in j:
      flag = 'M'
      continue
    elif a in j:
      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())

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)

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:
import sys
from operator import itemgetter
N,M = map(int,input().split())
A = [0] * M
#B = [0] * M
for i in range(M):
    A[i] = list(map(int,input().split()))
    if A[i][0] > A[i][1]:
        A[i][0],A[i][1] = A[i][1],A[i][0]
A = sorted(A, key = itemgetter(0))        
C = [set()]
if M != 0:
    C[0].add(A[0][0])
    C[0].add(A[0][1])
else:
    print(1)
    sys.exit()
for i in range(1,M):
    for j in range(len(C)):
        if A[i][0] in C[j]:
            C[j].add(A[i][1])
        elif A[i][1] in C[j]:
            C[j].add(A[i][0])
        else:
            C.append({A[i][0],A[i][1]})
ans = 0
for j in range(len(C)):
    if len(C[j]) > ans:
        ans = len(C[j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import itertools

def resolve():
    #N=int(input())
    N,M=map(int,input().split())
    Gr = [set([]) for y in range(N)]
    GrNum=1

    Max=1

    if(M>=1):
        A0,B0=map(int,input().split())
        Gr[0].add(A0)
        Gr[0].add(B0)
        Max=2

    if(M>=2):
        for i in range(M-1):
            A,B=map(int,input().split())
            found=False
            for j in range(GrNum):
                if(A in Gr[j]):
                    Gr[j].add(B)
                    found=True
                if(B in Gr[j]):
                    Gr[j].add(A)
                    found=True
                tmp=len(Gr[j])
                Max=max(Max,len(Gr[j]))
            if(found!=True):
                Gr[GrNum].add(A)
                Gr[GrNum].add(B)
                GrNum+=1                

    ans=Max

    print(ans)

resolve()

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
a=input()
a=a.split()
n=int(a[0])
m=int(a[1])
if m==0:
    print(1)
    sys.exit()
l=[0]*(n)
k=1
for i in range(m):
    x=input()
    x=x.split()
    xa=int(x[0])-1
    xb=int(x[1])-1
    if l[xa]==0 and l[xb]==0:
        l[xa]=k
        l[xb]=k
        k+=1
    if l[xa]==0 and l[xb]!=0:
        l[xa]=l[xb]
    if l[xa]!=0 and l[xb]==0:
        l[xb]=l[xa]
    if l[xa]!=0 and l[xb]!=0 and l[xa]!=l[xb]:
        p=min(l[xa],l[xb])
        q=max(l[xa],l[xb])
        l=[p if z==q else z for z in l]
l=[z for z in l if z!=0]
c=collections.Counter(l)
print(max(c.values()))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
all_set = set({})
friends = []
ans = 1
for i in range(m):
    temp = set(map(int, input().split()))
    if temp & all_set:
        for j in range(len(friends)):
            if temp & friends[j]:
                friends[j] |= temp
                if len(friends[j]) > ans:
                    ans = len(friends[j])
                break
    else:
        friends.append(temp)
        if ans < 2:
            ans = 2
    all_set |= temp

print(ans)

Submission status: Time Limit Exceeded

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

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

A_set = set()
B_set = set()
A = []
B = []
for i in range(M):
    a, b = map(int, input().split())
    if (a < b):
        A_set.add(a)
        A.append(a)
        B_set.add(b)
        B.append(b)
    else:
        A_set.add(b)
        A.append(b)
        B_set.add(a)
        B.append(a)


count = 0
member = []
for a in A_set:
    group = set()
    group.add(a)
    for i in range(M):
        if (A[i] == a):
            group.add(B[i])    
    member.append(len(group))
    count = count + 1

print(max(member))

Submission status: Time Limit Exceeded

Solution code:
import collections

N,M = map(int,input().split())
List = [[]]*N
List2 = [0]*N
for i in range(M):
    A,B = map(int,input().split())
    cA = collections.Counter(List[A-1])
    cB = collections.Counter(List[B-1])
    if(cA[B-1] >= 1 and cB[A-1] >= 1):
        pass
    else:
        List2[A-1] += 1
        List2[B-1] += 1
    List[A-1].append(B-1)
    List[B-1].append(A-1)
print(max(List2)+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
C = [{i + 1} for i in range(N)] #友人グループ
ans = 1
for i in range(M):
    A, B = map(int, input().split())
    D = {A, B} # A B 含む友人グループ
    E = []
    for d in C:
        
        if d & D != set():
            D = d | D
            
        else:
            E.append(d)
    a = len(D)
    if a > ans:
        ans = a
    E.append(D)
    C = E

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dc
x, y = map(int, input().split())
graph = [[] for n in range(x+1)]

st = dc(lambda: 0)

for n in range(y):
    a, b = map(int, input().split())

    if a > b:
        a, b = b, a
    graph[a].append(b)
    graph[b].append(a)


res = 0
vis = dc(lambda: 0)


def dfs(node):
    global res
    bfs = [node]
    vis[node] = 1
    while len(bfs):
        top = bfs[0]
        del bfs[0]
        res += 1
        for n in graph[top]:
            if not vis[n]:
                vis[n] = 1
                bfs.append(n)


mx = 0
for n in range(1, x+1):
    res = 0
    if vis[n] == 0:
        dfs(n)
        mx = max(mx, res)

print(mx)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = 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
    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:
from collections import deque

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

ans = 0
n_set = set([i for i in range(n)])
while n_set:
    g = set()
    queue = deque([list(n_set)[0]])
    while queue:
        now = queue.popleft()
        if now in g:
            continue
        g.add(now)
        for i in ab[now]:
            queue.append(i)
            g.add(i)
    ans = max(ans, len(g))
    if ans > n//2:
        print(ans)
        exit()
    n_set -= g
print(ans)

Submission status: Time Limit Exceeded

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

friends=set()

for i in range(M):
    friend=tuple(map(int,input().split()))
    friends.add(friend)
friends=list(friends)

research={i:N+1 for i in range(N+1)}
group={}
nums=0
for i in range(len(friends)):
    a_mem=min(friends[i])
    b_mem=max(friends[i])
    if research[a_mem]==N+1 and research[b_mem]==N+1:
        research[a_mem]=nums
        research[b_mem]=nums
        group[nums]=[a_mem,b_mem]
        nums+=1
    elif research[a_mem]==N+1:
        research[a_mem]=research[b_mem]
        group[research[b_mem]].append(a_mem)
    elif research[b_mem]==N+1:
        research[b_mem]=research[a_mem]
        group[research[a_mem]].append(b_mem)
    else:
        pt=research[b_mem]
        dist=research[a_mem]
        for j in reversed(range(len(group[pt]))):
            mem=group[pt].pop(j)
            group[dist].append(mem)
            research[mem]=dist

ans=1
for k in range(len(group)):
    ans=max(ans,len(group[k]))  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))
n = a[0]
m = a[1]

if m != 0:
  ab = [map(int, input().split()) for _ in range(m)]
  a, b = [list(i) for i in zip(*ab)]
  set_list = [{a[0],b[0]}]
  for i in range(1,m):
    flag = 0
    for j in range(len(set_list)):
      if a[i] in set_list[j] or b[i] in set_list[j]:
        set_list[j].add(a[i])
        set_list[j].add(b[i])
        flag = 1
        break
    if flag == 0:
      set_list.append({a[i],b[i]})

  #print(set_list)

  ans = 1
  for i in range(len(set_list)):
    ans = max(ans, len(set_list[i]))

  print(ans)
else:
  print(1)

Submission status: Time Limit Exceeded

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


friends=[{-1}]
num=1
people=[-1]*n
ans=0

F2=[]

for f in F:
    if f[0]<f[1]:
        F2.append(f)
    else:
        F2.append([f[1],f[0]])

F2.sort()

for f in F2:
    a=f[0]-1
    b=f[1]-1
    #print(a,b)

    if people[a]==-1 and people[b]==-1:
        friends.append({a,b})
        people[a]=num
        people[b]=num
        num+=1

    elif people[a]!=-1 and people[b]!=-1 and people[a]!=people[b]:
        A=people[a]
        B=people[b]
        friends[A] = friends[A].union(friends[B])
        for i in friends[B]:
            people[i]=A

    elif people[a]!=-1 and people[b]==-1:
        friends[people[a]].add(b)
        people[b]=people[a]

    elif people[a]==-1 and people[b]!=-1:
        friends[people[b]].add(a)
        people[a]=people[b]

    #print(people)
    #print(friends)

for i in friends:
    if len(i)>ans:
        ans=len(i)
print(ans)

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)
    
   
def dfs(node):
    
    s = set()
    stack = deque([node])
    while stack:
        
        n = stack.popleft()
        s.add(n)
        for i in d[n]:
            if i not in s and i not in visited:
                stack.append(i)
                
    return s
    
visited = set()
ans = 1

for key in list(d.keys()):
    if key not in visited:
        s = dfs(key)
        ans = max(ans, len(s))
        for i in s:
            visited.add(i)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = list()
B = list()
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

largest = 1
group = []
people = [-1] * N
for a, b in zip(A, B):
    if people[a] != -1 and people[b] != -1 and people[a] != people[b]:
        group[people[a]].update(group[people[b]])
        for gb in group[people[b]]:
            people[gb] = people[a]
        group[people[b]] = group[people[a]]
    elif people[a] != -1:
        people[b] = people[a]
        group[people[a]].add(b)
    elif people[b] != -1:
        people[a] = people[b]
        group[people[b]].add(a)
    else:
        group.append(set([a, b]))
        people[a] = len(group)-1
        people[b] = people[a]
    largest = max(len(group[people[a]]), largest)

print(largest)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect

from sys  import stdin,stdout

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

from math import gcd,ceil,floor,sqrt

from collections import Counter,defaultdict,deque,OrderedDict

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


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

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

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

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

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

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

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

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

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


   
    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
    pr(cd)
        
        
    
for _ in range(1):
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

x =lambda:list(map(int,sys.stdin.readline().strip().split()))
n,m=x()
adjac = {i:[] for i in range(1,n+1)}

for _ in range(m):
    a,b = x()
    adjac[a].append(b)
    adjac[b].append(a)

comp = 0

visited = {i:False for i in range(1,n+1)}

for i in range(1,n+1):

    if not visited[i]:
        queue = [i]
        count=1
        visited[i] = True
        while len(queue)!=0:
            h=queue[0]
            queue.pop(0)
            arr = adjac[h]
            # print(arr,i)
            for j in arr:
                if not visited[j]:
                    # print(j,h)
                    visited[j]=True
                    queue.append(j)
                    count+=1
        comp=max(comp,count)
print(comp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin


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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def main():
  N, M = map(int, input().split())
  lst = [list(map(int, stdin.readline().split())) for _ in range(M)]
  
  f_lst = [[0 for j in range(N)] for i in range(N)]
  count = [0] * N
  for A, B in lst:
    if f_lst[A-1][B-1] != 1 and f_lst[B-1][A-1] != 1:
      f_lst[A-1][B-1] = 1
      f_lst[B-1][A-1] = 1
      count[A-1] += 1
      count[B-1] += 1
  print(max(count)+1)

main()

Submission status: Time Limit Exceeded

Solution code:
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

# region fastio
# Credits
# # template credits to cheran-senthil's github Repo

BUFSIZE = 8192
from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

def main():
    class Graph(object):

        def __init__(self):
            self.neighbours = {}
        
        def add_node(self, node):
            self.neighbours[node] = []
        
        def add_edge(self, edge):
            u, v = edge
            if v not in self.neighbours[u]:
                self.neighbours[u].append(v)
            if u not in self.neighbours[u]:
                self.neighbours[v].append(u)
        
        @bootstrap
        def dfs(self, node):
            visited[node] = 1
            count = 0
            for child in self.neighbours[node]:
                if visited[child] == 0:
                    count += yield self.dfs(child)
            yield count + 1

    g = Graph()
    n, m = map(int, input().split())
    visited = [0] * (n + 1)
    for i in range(n):
        g.add_node(i + 1)
    for i in range(m):
        x, y = map(int, input().split())
        g.add_edge((x, y))
    ans = -1
    for i in range(1, n + 1):
        if visited[i] == 0:
            ans = max(ans,g.dfs(i))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

n, m = map(lambda x: int(x), input().split())
person_to_friends = defaultdict(set)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    person_to_friends[a].add(b)
    person_to_friends[b].add(a)

not_searched = set(range(1, n+1))
max_pool_num = 1

while len(not_searched) > 0:
#     print(not_searched)
    first_person = not_searched.pop()
    friend_pool = set([first_person])
    que = deque([first_person])
    while len(que) > 0:
        current_person = que.pop()
#         print('que', que)
        not_searched_friends = person_to_friends[current_person].intersection(not_searched)
#         print(not_searched_friends)
        for friend in not_searched_friends:
            not_searched.remove(friend)
            que.appendleft(friend)
            friend_pool.add(friend)
    max_pool_num = max(len(friend_pool), max_pool_num)
print(max_pool_num)

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 ]:
        if visited[ j ] == 1:
            continue
        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(list)

for _ in range(m):
    
    a,b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)
    
   
def dfs(node):
    
    s = set()
    stack = deque([node])
    while stack:
        
        n = stack.popleft()
        s.add(n)
        for i in d[n]:
            if i not in s and i not in visited:
                stack.append(i)
                
    return s
    
visited = set()
ans = 1

for key in list(d.keys()):
    if key not in visited:
        s = dfs(key)
        ans = max(ans, len(s))
        for i in s:
            visited.add(i)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    n, m = map(int, input().split())
    ab = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)

    ans = 0
    n_set = set([i for i in range(n)])
    while n_set:
        g = set()
        queue = deque([list(n_set)[0]])
        while queue:
            now = queue.popleft()
            if now in g:
                continue
            g.add(now)
            for i in ab[now]:
                queue.append(i)
                g.add(i)
        ans = max(ans, len(g))
        if ans > n//2:
            print(ans)
            exit()
        n_set -= g
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from collections import Counter
n,m = map(int,input().split())

l = np.array([[0]*n for _ in range(n)])

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

x,labels= connected_components(l)
c = Counter(list(labels))
print(c.most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
import collections
n, m = map(int, input().split())
gp = [[] for i in range(n+1)]
seen = [0 for i in range(n+1)]
ans = []

for i in range(m):
  a, b = map(int, input().split())
  if b not in gp[a]:
    gp[a].append(b)
  if a not in gp[b]:
    gp[b].append(a)

for i in range(1, n+1):
  if seen[i] == 1:
    continue
  else:
    que = [i]
    cnt = 1
    while que:
      now = que.pop(0)
      for g in gp[now]:
        if seen[g] == 1:
          continue
        else:
          que.append(g)
          seen[g] = 1
          cnt += 1
    if cnt != 1:
      cnt -= 1
    ans.append(cnt)
          
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest

from collections import deque

# DFSで連結成分求める
def resolve():
    # s = input()
    # n = int(input())
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    seen = set()

    graph = [[] for _ in range(n + 1)]

    # 線形
    for a, b in ab:
        if b not in set(graph[a]):
            graph[a] += [b]
        if a not in set(graph[b]):
            graph[b] += [a]

    que = deque()
    renketsu = []

    for ss in range(1, n + 1):
        if ss not in seen:
            tmp_renketsu = set()
            que.append(ss)
            while que:
                next_point = que.popleft()
                seen.add(next_point)
                tmp_renketsu.add(next_point)
                # print(tmp_renketsu, seen)

                if graph[next_point]:
                    for point in graph[next_point]:
                       if point not in tmp_renketsu:
                            que.append(point)
                            tmp_renketsu.add(point)
            l = len(tmp_renketsu)
            renketsu.append(l)
            if l == m + 1:
                break

    print(max(renketsu))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5 3
1 2
3 4
5 1"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 4
3 1
4 1
5 9
2 6"""
        output = """3"""
        self.assertIO(input, output)


if __name__ == "__main__":
    #unittest.main()
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import itertools

def resolve():
    #N=int(input())
    N,M=map(int,input().split())
    Gr = [[] for y in range(N)]
    GrNum=1

    Max=1

    if(M>=1):
        A0,B0=map(int,input().split())
        Gr[0].append(A0)
        Gr[0].append(B0)
        Max=2

    if(M>=2):
        for i in range(M-1):
            A,B=map(int,input().split())
            found=False
            for j in range(GrNum):
                if(A in Gr[j]):
                    if(B not in Gr[j]):
                        Gr[j].append(B)
                    found=True
                if(B in Gr[j]):
                    if(A not in Gr[j]):
                        Gr[j].append(A)
                    found=True
                tmp=len(Gr[j])
                Max=max(Max,len(Gr[j]))
            if(found!=True):
                Gr[GrNum].append(A)
                Gr[GrNum].append(B)
                GrNum+=1                

    ans=Max

    print(ans)

resolve()