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

from collections import defaultdict

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

uf = UnionFind(N)
REL = defaultdict(set)

for _ in range(M):
    a, b = map(int, input().split())
    # REL[a].add(b)
    # REL[b].add(a)
    a -= 1
    b -= 1
    if a > b:
        c = b
        b = a
        a = c

    uf.union(a, b)

mm = 0
for root in uf.roots():
    mm = max(mm, len(uf.members(root)))

ic = 0
for m in range(N):
    if uf.members(m) == 0:
        ic += 1

# for r, g in uf.all_group_members():
#     if len(g) == 1:
#         ic += 1
#     else:
#         mm = max(mm, len(g))

if mm < ic:
    mm += 1

print(mm)

Submission status: Time Limit Exceeded

Solution code:
import collections
def solve():
  N,M = map(int,input().split())
  ABlist = [[0 for _ in range(2)] for _ in range(M)]
  WA = [0]*N
  for i in range(N):
    WA[i] = i+1
  for i in range(M):
    A, B = map(int,input().split())
    if A>B:
      A,B =B,A
    ABlist[i][0] = A
    ABlist[i][1] = B
  ABlist.sort(key=lambda x: (x[0],x[1]))
  for i in range(M):
    A = ABlist[i][0]
    B = ABlist[i][1]
    if WA[B-1]<WA[A-1]:
      WA_ = WA[A-1]
      for i in range(N):
        if WA[i]==WA_:
          WA[i] = WA[B-1]
      WA[A-1] = WA[B-1]
    else:
      WA[B-1] = WA[A-1]
  c = collections.Counter(WA)
  print(c.most_common()[0][1])
solve()

Submission status: Time Limit Exceeded

Solution code:
x =lambda:list(map(int,input().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 = []

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.append(count)

# print(comp)
comp.sort()
ans=0
sub = 0
for i in range(0,len(comp)):
    # print(sub)
    app = comp[i]-sub
    ans+=app
    sub+=app

print(ans)

Submission status: Time Limit Exceeded

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

import networkx as nx

edges = []
for _ in range(M):
    i,j=map(int, input().split())
    edges.append([i-1,j-1])
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
sg = nx.connected_components(G)
connected = sorted(sg, key=len)
print(len(connected[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

g = np.zeros(N, dtype = int)
n = np.zeros(N, dtype = int)

num = 1

for i in range(len(c)):
    
    if g[c[i][0]-1] != 0 and g[c[i][1]-1] != 0:
        if g[c[i][0]-1] == g[c[i][1]-1]:
            pass
        else:
            matched = np.count_nonzero(g==g[c[i][1]-1])
            n[g[c[i][0]-1]-1] += matched
            n[g[c[i][1]-1]-1] -= matched
            g[g==g[c[i][1]-1]] = g[c[i][0]-1]

    elif g[c[i][0]-1] != 0:
        g[c[i][1]-1] = g[c[i][0]-1]
        n[g[c[i][0]-1]-1] += 1
    elif g[c[i][1]-1] != 0:
        g[c[i][0]-1] = g[c[i][1]-1]
        n[g[c[i][1]-1]-1] += 1
    else:
        g[c[i][0]-1] = num
        g[c[i][1]-1] = num
        n[num-1] += 2
        num += 1

print(max(n) or 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

graph = defaultdict(list)

n, m = map(int, sys.stdin.readline().split())

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

for _ in range(m):
    a,b = map(int, sys.stdin.readline().split())

    if not b in graph[a]:
        graph[a].append(b)
    if not a in graph[b]:
        graph[b].append(a)

visited = set()
maxi = 0

def dfs(start):
    stk = [start]
    visited.add(start)
    temp = 1

    while stk:
        cur = stk.pop()

        for c in graph[cur]:
            if not c in visited:
                visited.add(c)
                stk.append(c)
                temp += 1

    return temp

for j in graph:
    if not j in visited:
        cnt = dfs(j)
        maxi = max(cnt, maxi)

print(maxi)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, m = map(int, input().split())
f = []
if m == 0:
  ans = 1
else:
    for i in range(m):
      a, b = map(int, input().split())
      if a in list(itertools.chain.from_iterable(f)):
        for j in range(len(f)):
          if a in f[j]:
            f[j].append(b)
            break
      elif b in list(itertools.chain.from_iterable(f)):
        for j in range(len(f)):
          if b in f[j]:
            f[j].append(a)
            break
      else:
        f.append([a, b])
    arr = []
    for i in range(len(f)):
      arr.append(len(list(set(f[i]))))
    ans = max(arr)
print(ans)

Submission status: Time Limit Exceeded

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

members = [-1] * N

group_count = 0
groups = [0] * N
group_dict = {}
for m in range(M):
    A, B = map(int, input().split())
    A = A - 1
    B = B - 1
    if members[A]==-1 and members[B]==-1:
        members[A] = members[B] = group_count
        groups[group_count] = 2
        group_dict[group_count] = [A, B]
        group_count += 1
    
    elif members[A]!=-1 and members[B]==-1:
        members[B] = members[A]
        groups[members[A]] += 1
        group_dict[members[A]].append(B)
    
    elif members[B]!=-1 and members[A]==-1:
        members[A] = members[B]
        groups[members[B]] += 1
        group_dict[members[B]].append(A)
    
    else:
        if members[A] != members[B]:
            old = members[B]
            groups[members[A]] += groups[members[B]]
            groups[members[B]] = 0
            group_dict[members[A]] = group_dict[members[A]] +  group_dict[members[B]]
            for aaaaaa in group_dict[members[B]]:
                members[aaaaaa] = members[A]
            group_dict[old] = []

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [[0] * (N+1) for _ in range(N+1)]
ans = 0

for _ in range(M):
    link = list(map(int, input().split()))
    matrix[link[0]][link[1]] = 1
    matrix[link[1]][link[0]] = 1
    
def dfs(current_node, row, foot_prints):
    foot_prints += [current_node]
    for search_node in range(len(row[current_node])):
        if row[current_node][search_node] and search_node not in foot_prints:
            foot_prints = dfs(search_node, row, foot_prints)
    return foot_prints

tmp = []
for i in range(1, N+1):
    if i not in tmp:
        l = dfs(i, matrix, [])
        tmp.extend(l)
        ans = max(len(l), ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
n, m = map(int,input().split())

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

# total = 0
# for i in range(n):
#     sub_total = 0
#     for j in joken:
#         if i in j:
#             sub_total += 1
#     total = max(total, sub_total)

sub_total = [0] * n
for j in joken:
    sub_total[j[0] - 1] += 1
    sub_total[j[1] - 1] += 1

print(max(sub_total) + 1)

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 = []

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 len(d) != 0:
  for i in range(len(k)):
    y = k.pop(0)
    x = b[y-1]
    for j in range(len(x)):
      if (x[j]-1) in d:
        d.remove(x[j]-1)
        ans += 1
        k.append(x[j])
  if len(k) == 0:
    ans1 = max(ans,ans1)
    ans = 0
    k.append(d[0])
    d.pop(0)

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

Submission status: Time Limit Exceeded

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

from collections import defaultdict

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

uf = UnionFind(N)
REL = defaultdict(set)

for _ in range(M):
    a, b = map(int, input().split())
    # REL[a].add(b)
    # REL[b].add(a)
    a -= 1
    b -= 1
    if a > b:
        c = b
        b = a
        a = c

    uf.union(a, b)

mm = 0
for root in uf.roots():
    mm = max(mm, len(uf.members(root)))

ic = 0
for m in range(N):
    if uf.members(m) == 0:
        ic += 1

if mm < ic:
    mm += 1

print(mm)

Submission status: Time Limit Exceeded

Solution code:
from queue import deque
N,M=map(int, input().split())
f=deque()
x=deque()
mx=0
for _ in range(M):
    a,b = map(int, input().split())
    for i in f:
        if a in i[0]:
            if b not in i[0]:
                i[0].add(b)
                i[1]+=1
                mx=max(mx,i[1])
            break
        elif b in i[0]:
            i[0].add(a)
            i[1]+=1
            mx=max(mx,i[1])
            break
    else:
        f.append([set((a,b)),2])
        mx=max(mx,2)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
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 = 0
def dfs(node):
    todo = set()
    for nextnode in graph[node]:
        if nextnode not in seen:
            seen.add(nextnode)
            todo.add(nextnode)
    for nextnode in todo:
        dfs(nextnode)
for i in range(1,n+1):
    seen = set()
    seen.add(i)
    dfs(i)
    ans = max(ans,len(seen))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 接続最大クラスタのサイズが答え？
from networkx import Graph, connected_components

N, M = [int(x) for x in input().split(' ')]

list_ab = [None] * M
for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    list_ab[i] = (a, b)


G = Graph()
G.add_nodes_from(range(N))
G.add_edges_from(list_ab)

# # get max connected component
# max_size = 0
# for component in connected_components(G):
#     max_size = max(max_size, len(component))
#     if max_size >= (N+1) // 2:
#         break
# print(max_size)

largest_cc = len(max(connected_components(G), key=len))
print(largest_cc)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
group = []
for _ in range(M):
  A, B = map(int, input().split())
  for g in group:
    if A in g or B in g:
      if not A in g:
        g.add(A)
      if not B in g:
        g.add(B)
      break
  else:
    group.append(set((A, B)))

# print(group)

ans = 1
for g in group:
  ans = max(ans, len(g))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    #https://note.nkmk.me/python-union-find/ 
    #note.nkmk.me  2019-08-18 
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
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 main():
    N,M = map(int,input().split())
    AB= [list(map(int,input().split())) for _ in range(M)]

    uf = UnionFind(N)

    for ab in AB:
        uf.union(ab[0]-1,ab[1]-1)
    uflist = list(uf.all_group_members().values())
    ans = 0
    for ufs in uflist:
        ans = max(ans,len(ufs))
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
a,b = list(map(int, input().split()))
friend_li = []
matched = False

result = 0

for i in range(b):
  c,d = list(map(int, input().split()))
  for j in range(len(friend_li)):
    judge_1 = c in friend_li[j]
    judge_2 = d in friend_li[j]
    if judge_1 and not judge_2:
      friend_li[j].append(d)
      matched = True
      break
    elif not judge_1 and judge_2:
      friend_li[j].append(c)
      matched = True
      break
    elif judge_1 and judge_2:
      matched = True
      break
  if matched == False:
    friend_li.append([c,d])
  matched = False

for element in friend_li:
  len_ = len(element)
  if len_ > result:
    result = len_
print(max(1,result))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

members = np.array([-1] * N).astype(np.int)

group_count = 0
groups = [0] * N
group_dict = {}
for m in range(M):
    A, B = map(int, input().split())
    A = A - 1
    B = B - 1
    if members[A]==-1 and members[B]==-1:
        members[A] = members[B] = group_count
        groups[group_count] = 2
        group_dict[group_count] = [A, B]
        group_count += 1
    
    elif members[A]!=-1 and members[B]==-1:
        members[B] = members[A]
        groups[members[A]] += 1
        group_dict[members[A]].append(B)
    
    elif members[B]!=-1 and members[A]==-1:
        members[A] = members[B]
        groups[members[B]] += 1
        group_dict[members[B]].append(A)
    
    else:
        if members[A] != members[B]:
            old = members[B]
            groups[members[A]] += groups[members[B]]
            groups[members[B]] = 0
            group_dict[members[A]] = group_dict[members[A]] +  group_dict[members[B]]
            members[group_dict[members[B]]] = members[A]
            group_dict[old] = []
        
ans = max(groups)
if ans == 0:
    print(1)
else:
    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].extend(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=map(int, input().split())

import networkx as nx

edges = []
for _ in range(M):
    i,j=map(int, input().split())
    i-=1
    j-=1
    edges.append([i,j])
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
sg = nx.connected_components(G)
connected = sorted(sg)

max_len = 0
for nodes in connected:
    len_ = len(nodes)
    if len_>max_len:
        max_len=len_
print(max_len)

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

for f in F:
    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:
N , M = map(int,input().split())
AB = []
for _ in range(M):
    AB.append(list(map(int,input().split())))

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

for i in range(M):
    friends[AB[i][0]-1].append(AB[i][1])
    friends[AB[i][1]-1].append(AB[i][0])

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

for i in range(N):
    for f in friends[i]:
        for f2 in friends[f-1]:
            if f2 != i+1 and friends[i].count(f2) == 0:
                friends[i].append(f2)

ans = 0
for i in range(N):
    ans = max(ans, len(set(friends[i])))

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
M=[1 for i in range(n)]
F=[]
for i in range(m):
    a,b=map(int,input().split())
    a,b=min(a,b),max(a,b)
    if [a,b] not in F:
        F.append([a,b])
        M[a-1]+=1
print(max(M))

Submission status: Time Limit Exceeded

Solution code:
from typing import Set, List, Dict

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

G: List[Set[int]] = []
lookup_tab: Dict[int, int] = {}
for _ in range(M):
    a, b = map(int, input().split())
    if a not in lookup_tab and b not in lookup_tab:
        G.append({a, b})
        lookup_tab[a] = len(G) - 1
        lookup_tab[b] = len(G) - 1
    elif a in lookup_tab and b not in lookup_tab:
        gid = lookup_tab[a]
        lookup_tab[b] = gid
        G[gid].add(b)
    elif b in lookup_tab and a not in lookup_tab:
        gid = lookup_tab[b]
        lookup_tab[a] = gid
        G[gid].add(a)
    else:
        a_gid = lookup_tab[a]
        b_gid = lookup_tab[b]
        if a_gid != b_gid:
            # merge two groups
            for k, v in lookup_tab.items():
                if v == b_gid:
                    lookup_tab[k] = a_gid
            G[a_gid] = G[a_gid].union(G[b_gid])
        else:
            continue

if G:
    print(max([len(g) for g in G]))
else:
    print(1)

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)
            renketsu.append(len(tmp_renketsu))

    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:
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].add(ai)
    else:
        if bg is None:
            groups[ag].add(bi)
        else:
            if ag != bg:
                groups[ag] = groups[ag].union(groups[bg])
                groups[bg] = groups[ag].union(groups[bg])
                del groups[bg]

max_gr_len = 1
for group in groups:
    if max_gr_len < len(group):
        max_gr_len = len(group)

print(max_gr_len)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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

    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = MAP()
    AB = [LIST() for _ in range(M)]

    tree = UnionFind(N)
    for i in range(M):
        tree.union(AB[i][0]-1, AB[i][1]-1)

    ans = 0
    for l in tree.all_group_members().values():
        ans = max(ans, len(l))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

print(max(friend)+1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
lst = []
for _ in range(m):
  temp = set(input().split())
  memo = []
  F2 = False
  for i in range(len(lst)):
    if len(temp & lst[i]) == 1:
      memo.append(i)
    if len(temp & lst[i]) == 2:
      F2 = True
  if F2:
    pass
  elif len(memo) == 2:
    lst[memo[0]] = lst[memo[0]] | lst[memo[1]]
    lst[memo[1]] = set()
  elif len(memo) == 1:
    lst[memo[0]] = lst[memo[0]] | temp
  else:
    lst.append(temp)
#print(lst)###
if len(lst) == 0:
  print(1)
  exit()
res = 0
for s in lst:
  res = max(res, len(s))
print(res)