Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
List = [[]]*N
List2 = [0]*N
for i in range(M):
    A,B = map(int,input().split())
    if(List[A-1].count(B-1) >= 1 and List[B-1].count(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())
A,B=[],[]

l=[-1]*N

getIDmem={}
def getID(l,idx):
  orig=idx
  if idx==-1:
    return -1
  if(getIDmem.get(idx)!=None):idx=getIDmem[idx]
  while True:
    if idx==l[idx]:break
    idx=l[idx]
  getIDmem[orig]=idx
  return idx

d={}
for i in range(M):
  s=list(map(int,input().split()))
  s[0]-=1
  s[1]-=1
  if l[s[0]]==-1 and l[s[1]]==-1:
    l[s[0]]=s[0]
    l[s[1]]=s[0]
    d[s[0]]=2
  elif l[s[0]]==-1 or l[s[1]]==-1:
    for j in range(2):
      if l[s[j]]==-1:
        id=getID(l,s[(j+1)%2])
        l[s[j]]=id
        d[id]+=1
  else:
    r1=getID(l,s[0])
    r2=getID(l,s[1])
    if r1==r2:continue
    l[r1]=r2
    d[r2]+=d[r1]
    d[r1]=0
ans=1
for i in d:
  ans=max(ans,d[i])
print(ans)

Submission status: Time Limit Exceeded

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

d = {}

for i in range(m):
    a, b = [int(e) for e in input().split()]
    
    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]):
        d[a].update(d[b])
        for i in d[b]:
            if i != b:
                d[i] = d[a]
        d[b] = d[a]
        d[a].add(b)
    else:
        d[b].update(d[a])
        for i in d[a]:
            if i != a:
                d[i] = d[b]
        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:
def tuika(a,b):
    if a in dicSet:
        dic[a].add(b)
    else:
        dic[a] = set()
        dic[a].add(b)
        dicSet.add(a)



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

dic = dict()
dicSet = set()

for i in range(m):
    a,b = list(map(int,input().split()))
    if a in dicSet:
        dic[a].add(b)
    else:
        dic[a] = set()
        dic[a].add(b)
        dicSet.add(a)

    if b in dicSet:
        dic[b].add(a)
    else:
        dic[b] = set()
        dic[b].add(a)
        dicSet.add(b)

for i in dicSet:
    for j in dic[i]:
        dic[j] = dic[j] | dic[i]

ans = 1

for i in dicSet:
    long = len(dic[i])
    if long > ans:
        ans = long

#print(dic)

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
group = [set()]
member = []
for a in A_set:
    group[count].add(a)
    for i in range(M):
        if (A[i] == a):
            group[count].add(B[i])    
    member.append(len(group[count]))
    group.append(set())
    count = count + 1

print(max(member))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

c = [sorted(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:
            s = g[c[i][0]-1]
            t = g[c[i][1]-1]
            for j in range(len(g)):
                if g[j] == t:
                    g[j] = s
                    n[s-1] += 1
                    n[t-1] -= 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:
from collections import deque
N,M = map(int,input().split())
fship = []
for i in range(M):
    x,y = map(int,input().split())
    if x>y:
        x,y = y,x
    if [x,y] not in fship:
        fship.append([x-1,y-1])
fship.sort(key = lambda x: x[0])
graph = [[] for _ in range(N)]
for i in fship:
    graph[i[0]].append(i[1])

dist = [0]*N

ans = 0
for i in range(N):
    if dist[i]:
        continue
    dist[i] = 1
    tmp = 0
    d = deque()
    d.append(i)
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i]:
                continue
            dist[i] = 1
            d.append(i)
            tmp += 1
    ans = max(ans,tmp)
print(ans+1)

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,))]
for a, b in rels:
    for u in unions:
        if a in u:
            u.add(b)
            break
        if b in u:
            u.add(a)
            break
    else:
        x = set((a, b))
        unions.append(x)

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

Submission status: Time Limit Exceeded

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

for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1, b-1
  e[a][b]=1
  e[b][a]=1

end_q=[]
def conn(s):
  q=[s]
  end_q.append(s)
  an=0
  while len(q)>0:
    qq=q.pop(0)
    an+=1
    for i in range(N):
      if e[qq][i]==1 and (i not in end_q):
        q.append(i)
        end_q.append(i)
  return an
ans=0
for a in range(N):
  if a in end_q:
    continue
  else:
    ans=max(ans,conn(a))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [list(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:
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]
        for j in reversed(range(len(group[pt]))):
            mem=group[pt].pop(j)
            group[research[a_mem]].append(mem)
            research[mem]=research[a_mem]

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
cnt = [0] * N
mt = [[0] * N for _ in range(N)]
l = {tuple(sorted(list(map(int, input().split())))) for _ in range(M)}
for i, j in l:
  cnt[i-1] += 1
  cnt[j-1] += 1

print(max(cnt)+1)

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)

print(max_gr_len)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
    n, m = list(map(int, input().split(" ")))
    v_set = [set([]) for _ in range(n)]
    for _ in range(m):
        a, b = list(map(int, input().split(" ")))
        v_set[a-1].add(b-1)
        v_set[b-1].add(a-1)

    max_num = 0
    seen = [0]*n
    for ni in range(n):
        if seen[ni]:
            continue
        checked = [0]*n
        stack = deque([ni])
        checked[ni] = 1
        while stack:
            cur = stack.pop()
            seen[cur]+=1
            for next_i in v_set[cur]:
                if seen[next_i] or checked[next_i]:
                    continue
                stack.append(next_i)
                checked[next_i] = 1
        max_num = max(max_num, sum(checked))

    print(max_num)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

import networkx as nx

def connected_components(G):
    seen={}
    max_length = 0
    for v in G:
        if v not in seen:
            c = nx.algorithms.shortest_paths.single_source_shortest_path_length(G, v)
            #yield list(c)
            seen.update(c)
            length = len(c.values())
            if max_length<length:
                max_length=length
    return max_length

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)
sg = connected_components(G)
print(sg)

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 c in C:
        d = set(c)
        if d & D != set():
            D = d | D
            
        else:
            E.append(c)
    D = list(D)
    a = len(D)
    if a > ans:
        ans = a
    E.append(D)
    C = E

print(ans)

Submission status: Time Limit Exceeded

Solution code:
baseData = [int(i) for i in input().split(" ")]
N = baseData[0]
M = baseData[1]

group = []
flg = False

for i in range(M):
    temp = [int(j) for j in input().split(" ")]
    temp.sort()
    if i == 0:
        group.append(temp)
        flg = True
    else:
        for j in range(len(group)):
            if temp[0] in group[j]:
                if temp[1] not in group[j]:
                    for k in range(len(group)):
                        if j < k:
                            if temp[1] in group[k]:
                                group[j] += group[k]
                                group.pop(k)
                                break
                        if k == len(group) - 1:
                            group[j].append(temp[1])
                flg = True
                break
    if not flg:
        group.append(temp)
    flg = False

numGroup = []

for i in range(len(group)):
    numGroup.append(len(group[i]))

if numGroup == []:
    print(1)
else:
    print(max(numGroup))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
li = [0]*(n+1)
flag = 1
for _ in range(m):
    a, b = map(int, input().split())
    if li[a] and li[b]:
        if li[a] != li[b]:
            x = li[b]
            for i in range(len(li)):
                if li[i] == x:
                    li[i] = li[a]
    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
from collections import Counter
result = Counter(li)
print(result.most_common(1)[0][1])

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

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

ans = 0
for i in range(n):
  ans = max(ans, len(uf.members(i)))

print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
cnt = [0] * N
mt = [[0] * N for _ in range(N)]
l = [sorted(list(map(int, input().split()))) for _ in range(M)]
l = {(i, j) for i, j in l}
for i, j in l:
  cnt[i-1] += 1
  cnt[j-1] += 1

print(max(cnt)+1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
frnd = [set([i]) for i in range(n+1)]
mx = 1
for _ in range(m):
  f1,f2 = map(int, input().split())
  if f2 in frnd[f1]: continue
  frnd[f1] |= frnd[f2]
  frnd[f2] |= frnd[f1]
  mx = max(mx,len(frnd[f1]))
  for i in frnd[f1]-set([f1,f2]):
    frnd[i] |= frnd[f1]
print(mx)

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
    l[b-1][a-1] = 1

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
L = []
N2 = [[0]*N for i in range(N)]
ans = 0
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1; B -= 1
  N2[A][B] = 1; N2[B][A] =1
for i in range(N):
  ans = max(ans, sum(N2[i])+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

N,M= map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    A[i], B[i] = map(int, input().split())
    
#A=[1, 3, 5]
#B=[2, 4, 1]
#N,M=5 ,3

l=[[0 for i in range(N)] for j in range(N)]
for i in range(M):
    l[A[i]-1][B[i]-1]=1
    l[B[i]-1][A[i]-1]=1
#print(l)
a = np.array(l)
n, labels = connected_components(a)
#print(n)
#print(labels)
ans=0
for i in range(N):
    if labels[i]==0:
        ans+=1
print(ans)

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)


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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, m = map(int, input().split())
    s = [[j] for j in range(n)]
    for _ in range(m):
        a,b  = map(int, input().split())
        a-=1
        b-=1
        s[a].append(b)
        s[b].append(a)
    for i in range(n):
        for j in s[i]:
            s[j]=list(set(s[j]+s[i]))

    ans=0
    for i in range(len(s)):
        ans=max(len(s[i]),ans)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:

n, m = map(int, input().split())

table = [[False] * n for _ in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  table[a-1][b-1] = True
  table[b-1][a-1] = True

group = [i for i in range(n)]
update = [True] * n
needUpdate = True

while(needUpdate):
  nextUpdate = [False] * n
  needUpdate = False
  for i in range(n):
    if(not update[i]):
      continue
    for j in range(i + 1, n):
      if(table[i][j] and group[j] != group[i]):
        nextUpdate[j] = True
        needUpdate = True
        group[j] = group[i]
  update = nextUpdate

counttable = [0] * n
maxNum = 0
for i in range(n):
  temp = counttable[group[i]] + 1
  maxNum = max(maxNum, temp)
  counttable[group[i]] = temp
  
print(maxNum)

Submission status: Time Limit Exceeded

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

import networkx as nx

def connected_components(G):
    seen={}
    for v in G:
        if v not in seen:
            c = nx.algorithms.shortest_paths.single_source_shortest_path_length(G, v)
            yield list(c)
            seen.update(c)

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)
sg = connected_components(G)
connected = sorted(sg, key=len)
print(len(connected[-1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

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 = MI()
    union = UnionFind(N)
    for i in range(M):
        a, b = MI()
        union.union(a-1, b-1)
        
    #グループ数
    all_group_member = union.all_group_members()
    all_group_num = sorted([len(i) for i in all_group_member.values()])
    res = 0
    all_num = N
    min_num = 0
    group = len(all_group_num)
    while True:
        index = bisect_right(all_group_num, min_num)
        all_num -= (group-index)*(all_group_num[index]-min_num)
        res+= all_group_num[index]-min_num
        
        min_num = all_group_num[index]
        
        if all_num == 0:
            break
        
    print(res)

    
    
    
if __name__ == "__main__":
    main()

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 != min(A, B):
        omdst = min(A, B)
        while(dsts[omdst] != dst):
            n_omdst = dsts[omdst]
            dsts[omdst] = dst
            omdst = n_omdst
    if src != max(A, B):
        omsrc = max(A, B)
        while(dsts[omsrc] != src):
            n_omsrc = dsts[omsrc]
            dsts[omsrc] = src
            omsrc = n_omsrc

    if dst == src:
        continue
    dst2 = min(dst, src)
    src2 = max(dst, src)
    dsts[src2] = dst2
    Groups[dst2].extend(Groups[src2])
    Groups[src2] = []
    # print(Groups)
    # print(dsts)
ans = 0
for group in Groups:
    ans = max(ans, len(group))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D
from collections import deque
from bisect import bisect_left as bl

f=lambda:map(int,input().split())
N,M=f()
D=[[] for _ in [0]*(N+1)]
F=[0]*(N+1)
F[0]=1
for _ in range(M):
    a,b=f()
    if not b in D[a]:
        D[a].append(b)
    if not a in D[b]:
        D[b].append(a)

q=deque()
res=0
while bl(F,1):
    index=bl(F,1)-1
    q.append(index)
    tmp=0
    while q:
        k=q.pop()
        if F[k]!=1:
            tmp+=1
            F[k]=1
            for d in D[k]:
                if F[d]!=1:
                    q.append(d)
            D[k]=0
    res=max(res,tmp)

print(res)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
info=[[] for i in range(N+1)]
for i in range(M):
    a,b=map(int, input().split())
    info[a].append(b)
    info[b].append(a)

ls=[0]*(N+1)
for i in range(1, N+1):
    if ls[i]==0:
        ls[i]=i
    else:
        continue
    
    i_info=info[i]
    while i_info!=[]:
        fr=i_info.pop(0)
        ls[fr]=i
        i_info+=info[fr]
        info[fr]=[]
        
ans=[0]*(N+1)
for i in ls:
    ans[i]+=1
print(max(ans))

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 = friend[ i ] + queue

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:
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 == n:
                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:
N,M = map(int,input().split())

groups = [[]]
_max = []

for m in range(M):
    A, B = map(int, input().split())
    for i,group in enumerate(groups):
        if (A in group)and(B in group):
            break
        elif (A in group):
            groups[i].append(B)
        elif (B in group):
            groups[i].append(A)
        else:
            groups.append([A,B])

flag = 0

for n in range(1,N+1,1):
    for group in groups:
        if n in group:
            flag += 1
    if flag==0:
        groups.append([n])

for group in groups:
    _max.append(len(group))

print(max(_max))