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 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:
            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:

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

line = []
graph = [[] for _ in range(n)]

for i in range(m):
    ai, bi = list(map(int, input().split(" ")))
    ai -= 1
    bi -= 1
    graph[ai].append(bi)
    graph[bi].append(ai)


class DFS:

    def __init__(self):
        pass

    @staticmethod
    def dfs(start):
        max_size = 0
        size = 1
        stack = [start]
        tansaku_zumi = set([start])
        while stack:
            ai = stack[-1]
            if graph[ai]:
                bi = graph[ai].pop()
                if bi not in tansaku_zumi:
                    stack.append(bi)
                    size += 1
                    tansaku_zumi.add(bi)
            else:
                stack.pop()
        return size, tansaku_zumi

ans = 0
tansaku_zumi_all = set()
for i in range(n):
    if i not in tansaku_zumi_all:
        size, tansaku_zumi = DFS.dfs(i)
        tansaku_zumi_all = tansaku_zumi_all.union(tansaku_zumi)
        ans = max(ans, size)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

class UnionFind(): # 0インデックス
    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とyは-=1して使う
        '''
        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())

if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    group_dict = union_find.all_group_members()

    answer = 0
    count = 0
    for v in group_dict.values():
        answer = max(answer, len(v))
        count + 1
        if count >=  math.log2(N) + 1:
            break
    print(answer)

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

from collections import defaultdict  
N, M = map(int,input().split()) 
uf = UnionFind(N)
d = defaultdict(set)
for _ in range(M):
  a, b = map(int,input().split())
  d[a].add(b)
for k,sett in d.items():
  for v in sett:
  	uf.union(k-1,v-1)

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

Submission status: Time Limit Exceeded

Solution code:
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
    checked_list = []
    seen = [0]*n
    for ni in range(n):
        if seen[ni]:
            continue
        checked = []
        stack = deque([ni])
        while stack:
            cur = stack.pop()
            seen[cur]+=1
            checked.append(cur)
            for next_i in v_set[cur]:
                if seen[next_i] or next_i in stack:
                    continue
                stack.append(next_i)
        max_num = max(max_num, len(checked))
        checked_list.append(checked)

    print(max_num)

if __name__=="__main__":
    main()

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

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

Submission status: Time Limit Exceeded

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

sub_total = [0] * n
joken = []
for i in range(m):
    a, b = map(int,input().split())
    j = [min(a,b),max(a,b)]
    if j not in joken:
        joken.append(j)
        sub_total[j[0] - 1] += 1
        sub_total[j[1] - 1] += 1

print(max(sub_total) + 1)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    from collections import deque
    N, M = MI()
    fri_list = [[-1] for _ in range(N)]
    for i in range(M):
        a, b = MI()
        fri_list[a - 1].append(b)
        fri_list[b - 1].append(a)

    def bfs(u, n, g, A, B):
        queue = deque([u])
        d = [None] * (n + 1)  # uからの距離の初期化
        d[u] = 0  # 自分との距離は0
        A.append(u)
        while queue:
            v = queue.popleft()
            for i in g[v - 1]:
                if i == -1:
                    continue
                if d[i] is None:
                    d[i] = 1
                    B[i] = 1
                    queue.append(i)
                    A.append(i)

    group_list = []
    num_list = [0] * (N + 1)
    for i in range(1, N + 1):
        if num_list[i] == 0:
            G = []
            bfs(i, N, fri_list, G, num_list)
            group_list.append(G)

    len_list = []
    for l in group_list:
        x = len(l)
        len_list.append(x)
    ans = max(len_list)
    print(ans)

if __name__ == "__main__":
    main()

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.appendleft(index)
    tmp=0
    while q:
        k=q.pop()
        if F[k]!=1:
            tmp+=1
            q.extend(D[k])
            D[k]=0
            F[k]=1
    res=max(res,tmp)

print(res)

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

    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:
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))
        n_set -= g

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, m = nm()
    friends = [set() for _ in range(n)]
    for i in range(m):
        a, b = nm()
        friends[a - 1].add(b - 1)
        friends[b - 1].add(a - 1)

    groups = []
    in_group = [False] * n
    for i in range(n):
        if in_group[i]:
            continue
        d = deque(friends[i])
        group = [i]
        in_group[i] = True
        while d:
            c = d.pop()
            group.append(c)
            in_group[c] = True
            for friend in friends[c]:
                if not in_group[friend]:
                    d.append(friend)
        groups.append(list(set(group)))

    ans = 0
    for group in groups:
        ans = max(ans, len(group))
    print(ans)


if __name__ == '__main__':
    main()

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]:
            if len(group_dict[members[A]]) > len(group_dict[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] = []
            else:
                old = members[A]
                groups[members[B]] += groups[members[A]]
                groups[members[A]] = 0
                group_dict[members[B]] = group_dict[members[B]] + group_dict[members[A]]
                for bbbbbb in group_dict[members[A]]:
                    members[bbbbbb] = members[B]
                group_dict[old] = []

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

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])
    if max(friend) == N-1:
        break

print(max(friend)+1)

Submission status: Time Limit Exceeded

Solution code:
import queue
n,m=map(int,input().split())
a=[[] for j in range(n)]
for i in range(0,m):
    b,c=map(int,input().split())
    a[b-1].append(c-1)
    a[c-1].append(b-1)
re=[0 for i in range(n)]
le=[0]
for i in range(0,n):
    if re[i]==0:
        ans=queue.Queue()
        ans.put(i)
        le.append(1)
        re[i]=1
        while ans.empty()==False:
            d=ans.get()
            for j in range(len(a[d])):
                if re[a[d][j]]==0:
                    ans.put(a[d][j])
                    re[a[d][j]]=1
                    le[-1]+=1
print(max(le))

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(map(int, input().split())) for _ in range(M)}

for i, j in l:
  if mt[i-1][j-1] == 0:
    cnt[i-1] += 1
    cnt[j-1] += 1
    mt[j-1][i-1] = 1

print(max(cnt)+1)

Submission status: Time Limit Exceeded

Solution code:

class UnionFind:
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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)]

    # 要素x, yが同じグループに属するかどうかを返す
    def is_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()での表示用)
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def resolve():
    N, M = map(int, input().split())
    uf = UnionFind(N)

    for _ in range(M):
        a, b = map(lambda x: int(x) - 1, input().split())
        uf.union(a, b)

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


if __name__ == "__main__":
    resolve()

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

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

Submission status: Time Limit Exceeded

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

F = {v: [] for v in range(1, N+1)}

for f in AB:
    a = f[0]
    b = f[1]
    F[a].append(b)
    F[b].append(a)

groups = []

p = [-1 for _ in range(N+1)]
p[0] = 0
ans = 0

for i in range(1, N+1):
    if p[i] == 1:
        continue
    p[i] = 1
    group = [i]
    next = deque([i])
    while len(next) > 0:
        now = next.popleft()
        for j in F[now]:
            if p[j] == -1:
                p[j] = 1
                next.append(j)
            if j not in group:
                group.append(j)
    groups.append(group)
    ans = max(ans, len(group))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
 
n,m=map(int, input().split())
list=[]
list2=[]
count=0

for i in range(m):
 list.append([])
 a,b=map(int,input().split())
 list[i].append(a)
 list[i].append(b)
for i in range(n):
  list2.append(0)
 
for i in range(len(list)):
  list[i].sort()
  for g in range(len(list)):
    if list[i][0]==list[g][0] and list[i][1]!=list[g][1]:
      list.append([list[i][1],list[g][1]])
      i-=1
for i in range(len(list)):
  if list2[list[i][0]-1]==list2[list[i][1]-1]:
    list2[list[i][1]-1]+=1
for i in range(n):
  if i in list2:
    count+=1
  else:
    break
print(count)

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 = []
        queue = deque([list(n_set)[0]])
        while queue:
            now = queue.popleft()
            if now in g:
                continue
            g.append(now)
            for i in ab[now]:
                queue.append(i)
                g.append(i)
        ans = max(ans, len(set(g)))
        n_set -= set(g)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.stats as stats
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

print(stats.mode(np.array(group))[1][0])

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)

print(max(comp))

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(map(int, input().split())) for _ in range(M)}

for i, j in l:
  if mt[i-1][j-1] == 0:
    cnt[i-1] += 1
    cnt[j-1] += 1
    mt[i-1][j-1] = 1
    mt[j-1][i-1] = 1

print(max(cnt)+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 seen:
                            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:
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)
done = set()
while len(done) < n:
    seen = set()
    for i in range(1,n+1):
        if i not in done:
            break
    dfs(i)
    ans = max(ans,len(seen))
    done |= seen
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#
# abc177 d
#
import sys
from io import StringIO
import unittest


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)


def resolve():
    N, M = map(int, input().split())
    R = []
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = min(a, b), max(a, b)
        if [a, b] not in R:
            R.append([a, b])

    E = [0] * N
    for r in R:
        E[r[0]-1] += 1
        E[r[1]-1] += 1

    print(max(E)+1)


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

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=[]
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
            q.extend(D[k])
            D[k]=0
            F[k]=1
    res.append(tmp)

print(max(res))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

c = list(map(list, set(map(tuple, [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:
            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:
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
    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:
import sys
from collections import deque

def main():

    input = sys.stdin.readline

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

    A = [0] * M
    B = [0] * M

    friend_list = [ set() for _ in range(N)]
    friend_list_len = 0

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

        for j in range(friend_list_len):
            flag = False
            if A[i] in friend_list[j]:
                friend_list[j].add(B[i])
                flag = True
            if B[i] in friend_list[j]:
                friend_list[j].add(A[i])
                flag = True
            if flag:
                break                
        else:
            friend_list[friend_list_len].add(A[i])
            friend_list[friend_list_len].add(B[i])
            friend_list_len += 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

N,M= (int(x) for x in input().rstrip('\n').split())
f = [[x] for x in range(1,N+1)]
for _ in range(M):
  A,B = (int(x) for x in input().rstrip('\n').split())
  check = 0
  for i in f[::-1]:
    if A in i:
      a = i
      check += 1
    if B in i:
      b = i
      check += 1
    if check==2:
      break
  if a!=b:
    c = a+b
    f.append(c)
    f.remove(a)
    f.remove(b)
print(max(len(x) for x in f))

Submission status: Time Limit Exceeded

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

F = {v: [] for v in range(1, N+1)}

for f in AB:
    a = f[0]
    b = f[1]
    F[a].append(b)
    F[b].append(a)

groups = []

p = [-1 for _ in range(N+1)]
p[0] = 0
ans = 0

for i in range(1, N+1):
    if p[i] == 1:
        continue
    p[i] = 1
    group = [i]
    next = [i]
    while len(next) > 0:
        now = next.pop(0)
        for j in F[now]:
            if p[j] == -1:
                p[j] = 1
                next.append(j)
            if j not in group:
                group.append(j)
    groups.append(group)
    ans = max(ans, len(group))

print(ans)