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 queue
n,m=map(int,input().split())
a=[[0 for i in range(n)] for j in range(n)]
for i in range(0,m):
    b,c=map(int,input().split())
    a[b-1][c-1]=1
    a[c-1][b-1]=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(n):
                if a[i][j]==1 and re[j]==0:
                    ans.put(j)
                    re[j]=1
                    le[-1]+=1
print(max(le))

Submission status: Time Limit Exceeded

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        データが属するグループのID(と考えて良いはず)を取得する。
        :調査するグループ x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つのデータが属するグループを結合する。
        :結合するデータ(1つ目) x:
        :結合するデータ(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(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):
        """
        指定したグループに属するデータの数を返す。
        :調査グループ x:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

    def is_same(self, x, y):
        return self.getroot(x) == self.getroot(y)

    def members(self, x):
        """
        指定したグループに属するデータの一覧を返す。size()と比較して速度が圧倒的に遅いので注意。
        :調査グループ x:
        """
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(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 resolve(test_def_name=""):
    n, m = map(int, input().split())
    ab_s = [list(map(int, input().split())) for i in range(m)]

    uf = UnionFind(n + 1)

    for a, b in ab_s:
        uf.union(a, b)

    ans = 0
    for aaa in uf.all_group_members():
        ans = max(ans, uf.size(aaa))

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5 3
1 2
3 4
5 1"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_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(test_input, output)

    def test_input_3(self):
        test_input = """10 4
3 1
4 1
5 9
2 6"""
        output = """3"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original(self):
        pass


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Time Limit Exceeded

Solution code:
M,N = map(int, input().split())
sets=[{m+1} for m in range(M)]
for _ in range(N):
  a,b = map(int, input().split())
  aset={}
  bset={}
  asetFound=False
  bsetFound=False
  for set_ in sets:
    if not asetFound and a in set_:
      aset=set_
      asetFound=True
      if bsetFound:
        break
    elif not bsetFound and b in set_:
      bset=set_
      bsetFound=True
      if asetFound:
        break
  if len(aset)!=0 and len(bset)!=0:
    newset=aset|bset
    sets.append(newset)
    sets.remove(aset)
    sets.remove(bset)
#print(sets)
max=0
for set_ in sets:
  if max < len(set_):
    max=len(set_)
print(max)

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 graph[a]:
            graph[a] += [b]
        if a not in 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(tmp_renketsu)

    print(max([len(i) for i in 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:
# -*- 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)

print(total + 1)

Submission status: Time Limit Exceeded

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

arr = [[0]*n for i in range(n)]
ans = 0

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

for i in range(len(arr)):
    ans = max(ans, sum(x>0 for x in arr[i]))

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return 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())

    def depth(self):
    	ans = 0
    	for r in self.roots():
    		ans = max(ans, len(self.members(r)))
    	return ans

n,m = readInts()
ab = []
for i in range(m):
	ab.append(readInts())

uf = UnionFind(n+1)
for a,b in ab:
	uf.union(a,b)

print(uf.depth())

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
f=[]
for _ in range(M):
    a,b = map(int, input().split())
    for i in f:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            break
    else:
        f.append(set((a,b)))

x = 0
for i in f:
    x=max(x,len(i))
if M == 0:
    x = 1
print(x)

Submission status: Time Limit Exceeded

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

for _ in range(M):
  i, j = map(int, input().split())
  matrix[i-1][j-1] = matrix[j-1][i-1] = 1

cnt = [sum(matrix[i]) for i in range(N)]

print(max(cnt)+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin


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

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
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():
    n,m = LI()
    route = [[] for _ in range(n+1)]
    for _ in range(m):
        a,b = LI()
        route[a].append(b)
        route[b].append(a)
    explored = set()

    sstock = collections.deque([i for i in range(1,n+1)])
    ans = 0
    while len(sstock)!=0:
        nnext = sstock.pop()
        if nnext not in explored:
            cnt = 0
            stock = collections.deque([nnext])
            while len(stock) != 0:
                next = stock.pop()
                cnt += 1
                explored.add(next)
                for i in route[next]:
                    if i not in explored and i not in stock:
                        stock.append(i)
            ans = max(ans,cnt)
    print(ans)
main()

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 i in range(M):
        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:
n,m=map(int,input().split())
Alist=[list(map(int,input().split())) for i in range(m)]

def AddFriends(Alist):
  Fmap=[[0,0]]
  
  for A in Alist:
    a=A[0]
    b=A[1]
    
    NoPair=True
    
    for listF in Fmap:
      if a in listF:
        NoPair=False
        if b in listF:
          pass
        else:
          listF.append(b)
        break
          
      if b in listF:
        NoPair=False
        if a in listF:
          pass
        else:
          listF.append(a)
          
        break
    if NoPair:
      Fmap.append(A)
        
  return Fmap 
  

Fmap=AddFriends(Alist)
#print(Fmap)
maxLenF=2

if m==0:
  print(1)
  
else: 
  for i in Fmap:
    if len(i)>maxLenF:
      maxLenF=len(i)
  print(maxLenF)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  n, m = map(int, input().split())
  graph = [[] for _ in range(n)]

  for i in range(m):
    a, b = map(int, input().split())
    if b-1 not in graph[a-1]:
      graph[a-1].append(b-1)
      graph[b-1].append(a-1)
  
  unsearched = list(range(n))
  result = 0
  border = n//2
  while len(unsearched) > 0:
    if result > border:
      break
    s = unsearched[0]
    tmp, cnt = dfs(graph, unsearched, s)
    if cnt > result:
      result = cnt
      
  print(result)

def dfs(graph, unsearched, s):
  stack = deque([s])
  searched = [s]
  while len(stack):
    cur = stack.pop()
    unsearched.remove(cur)
    for i in graph[cur]:
      if i not in searched:
        stack.append(i)
        searched += [i]
  return searched, len(searched)

main()

Submission status: Time Limit Exceeded

Solution code:
#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,raw_input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,raw_input().split())
	d[x].add(y)
	d[y].add(x)


vis=set()
for u,v in d.items():
	d[u]=list(v)
count=0
que=[]
for i in range(1,n+1):
	if i not in vis:
		que=[]
		c=1
		vis.add(i)
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if j not in vis:
					vis.add(j)
					c+=1
					que.append(j)
		count=max(c,count)

print(count)

Submission status: Time Limit Exceeded

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

def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

def main():
    N, M = map(int, input().split())
    C = []
    for i in range(M):
        a, b = map(int, input().split())
        p = min(a, b)
        q = max(a, b)
        C.append([p,q])
    D = get_unique_list(C)
    F = [1]*(N+1)
    for a, b in D:
        F[a] += 1
    ans = max(F)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return 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())

    def depth(self):
    	ans = 0
    	for r in self.roots():
    		ans = max(ans, len(self.members(r)))
    	return ans

n,m = readInts()
ab = []
for i in range(m):
	ab.append(tuple(sorted(readInts())))
ab = sorted(list(set(ab)),key=lambda x:x[0])


uf = UnionFind(n+1)
for a,b in ab:
	uf.union(a,b)

print(uf.depth())

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化
class UnionFind():
    def __init__(self, n):
        #初期化[-1]*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のグループを統合する
        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):
        #要素xが所属するグループの人数を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        #要素xとyが同じグループかどうか(同じならTrue)
        return self.find(x) == self.find(y)

    def members(self, x):
        #要素xと同じグループのメンバー全員を返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        #Find-Treeの頂点
        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 ''.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    #遷移を確認したいときはこちらに書き換えて実行する(for以降の経路圧縮が行われていない)
    #def __str__(self):
    #  return ''.join('{}: {}'.format(r, self.members(r)))

def main():
    n, m = list(map(int,input().split()))
    data = [input().split() for _ in range(m)]
    UF = UnionFind(n)
    for i in range(m):
        UF.union(int(data[i][0]) - 1, int(data[i][1]) - 1)
    
    max_mem = 0
    for i in UF.roots():
        max_mem = max(max_mem, len(UF.members(i)))
    print(max_mem)
    return 0

if __name__ == "__main__":
    main()

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)
fr = []
# G = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a,b)
    fr.append((a,b))
c = [0]*n
for i in range(n):
    c[i] = tuple(uf.members(i))

# print(c)
sc = set(c)
sc = list(sc)
lenc = []
for ss in sc:
    lenc.append(len(ss))
lenc = set(lenc)
lenc = list(lenc)
lenc.sort(reverse=1)
if len(lenc) == 1:
    print(lenc[0])
else:
    ans = lenc[1]
    ans += lenc[0]-lenc[1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D Friends

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

friends = [[0]]
for i in range(M):
  a, b = input().split()
  for j in range(len(friends)):
    if a in friends[j] and b not in friends[j]:
      friends[j].append(b)
    elif b in friends[j] and a not in friends[j]:
      friends[j].append(a)
    else:
      friends.append([a, b])

ans = 0
for friend in friends:
  ans = max(ans, len(friend))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
relation = [[False]*n for _ in range(n)]
for i in range(m):
  i, j = sorted(list(map(int, input().split())))
  relation[i-1][j-1] = True
res = 0
for i in range(n-1):
  if n-1-i < res:
    break
  res = max(relation[i].count(True)+1, res)
print(res)

Submission status: Time Limit Exceeded

Solution code:
M,N = map(int, input().split())
sets=[{m+1} for m in range(M)]
for _ in range(N):
  a,b = map(int, input().split())
  aset={}
  bset={}
  asetFound=False
  bsetFound=False
  for set_ in sets:
    if not asetFound and a in set_:
      aset=set_
      if bsetFound:
        break
    elif not bsetFound and b in set_:
      bset=set_
      if asetFound:
        break
  if len(aset)!=0 and len(bset)!=0:
    newset=aset|bset
    sets.append(newset)
    sets.remove(aset)
    sets.remove(bset)
#print(sets)
max=0
for set_ in sets:
  if max < len(set_):
    max=len(set_)
print(max)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
from fractions import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 1000010
MOD = 10**9+7
spf = [i for i in range(MAXN)]
spf[0]=-1
def sieve():
    for i in range(2,MAXN,2):
        spf[i] = 2
    for i in range(3,int(MAXN**0.5)+1):
        if spf[i]==i:
            for j in range(i,MAXN,i):
                if spf[j]==j:
                    spf[j]=i
def fib(n,m):
    if n == 0:
        return [0, 1]
    else:
        a, b = fib(n // 2)
        c = ((a%m) * ((b%m) * 2 - (a%m)))%m
        d = ((a%m) * (a%m))%m + ((b)%m * (b)%m)%m
        if n % 2 == 0:
            return [c, d]
        else:
            return [d, c + d]
 
def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))
 
def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))
 
def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD
 
    return (num*(pow(den,MOD-2,MOD)))%MOD
 
def flush():
    return sys.stdout.flush()




'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''

def bfs(v):
    q = [v]
    vis[v] = 1
    l = 0
    while q:
        x = q.pop(0)
        l+=1
        for i in d[x]:
            if not vis[i]:
                vis[i] = 1
                q.append(i)
    return l


n,m = arrIN()
d = defaultdict(set)

for _ in range(m):
    a,b = arrIN()
    d[a].add(b)
    d[b].add(a)

vis = defaultdict(int)
cc = []
for i in range(1,n+1):
    if not vis[i]:
        cc.append(bfs(i))

cc.sort()
ans = cc[0]
cl = cc[0]
t = cl
for i in cc[1:]:
    if i==cl:
        continue
    cl = i-t
    t+=cl
    ans+=cl
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M=map(int, input().split())
    l =[set() for _ in range(N)]
    for _ in range(M):
        a,b=map(int, input().split())
        for s in l:
            if s:
                if a in s or b in s:
                    s.add(a)
                    s.add(b)
                    break
            else:
                s.add(a)
                s.add(b)
                break
    ans=-1
    for s in l:
        if not(s):
            break
        ans=max(ans,len(s))
    if ans==-1:
        print(1)
    else:
        print(ans)
if __name__ == "__main__":
    main()

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

    def max_group_members(self):
        return max([len(self.members(r)) for r in self.roots()])
    
N,M = map(int,input().split())

uf = UnionFind(N+1)
for _ in range(M):
    a,b = list(map(int, input().split()))
    uf.union(a,b)

print(uf.max_group_members())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


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

table = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
#    print(a,b)
    table[a].append(b)
    table[b].append(a)

visited = [0]*N
visited[0] = 1
H = deque()
H.append(0)
ans = 0
c = 1

while H:
    ans = max(ans,c)
    x = H.popleft()
#    print("x:",x,"c:",c)
#    print(visited)
    for y in table[x]:
        if visited[y] == 0:
            H.append(y)
            visited[y] = 1
#            print(y,"added")
            c += 1
    if not H:
        for i in range(N):
            if visited[i] == 0:
                H.append(i)
                visited[i] = 1
                c = 1
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


n, m = map(int, input().split())
ab = np.array([[0] * n] * n)
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ab[a][b] = 1
    ab[b][a] = 1
ans = 0
print(max(np.sum(ab, axis=0))+1)

Submission status: Time Limit Exceeded

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

mat=[ set() for _ in range(n)]

for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  mat[a].add(b)
  mat[b].add(a)
  
ans = 1
visited = [False]*n
count = 0
q = []
tmp = 0

while count < n:
  if len(q)==0:
    ans = max(ans,tmp)
    for i in range(n):
      if visited[i]==False:
        q.append(i)
        tmp = 1
        count +=1
        visited[i] = True
        break
  
  st = q.pop(0)
  
  
  for a in mat[st]:
    if visited[a] == False:
      q.append(a)
      tmp += 1
      count+=1
      visited[a] = True
ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
def gmi(): return map(int, stdin.readline().strip().split())
def gms(): return map(str, stdin.readline().strip().split())
def gari(): return list(map(int, stdin.readline().strip().split()))
def gars(): return list(map(int, stdin.readline().strip().split()))
def gs(): return stdin.readline().strip()
def gls(): return list(stdin.readline())
def gi(): return int(stdin.readline())
mod = 1000000007

n, m = gmi()
ar = {}
ans = 0
while m:
    flag = False
    m -= 1
    a, b = gmi()
    a, b = min(a, b), max(a, b)
    if a in ar and b:
        ar[a] += [b]
        continue
    for i in ar:
        if a in ar.get(i):
            flag = True
            ar[i] += [b]
    if not flag:
        ar[a] = [b]
br = []
#print(ar)
for i in ar:
    br.append(len(set(ar.get(i))))
#print(br)
ans += 1
show = [0]*len(br)
while br:
    m = min(br)
    ans += m
    br = [i-m for i in br if i > 0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def main():
  n, m = map(int, input().split())
  graph = [[] for _ in range(n)]

  for i in range(m):
    a, b = map(int, input().split())
    if b-1 not in graph[a-1]:
      graph[a-1].append(b-1)
      graph[b-1].append(a-1)
  
  unsearched = list(range(n))
  result = 0
  border = n//2
  while len(unsearched) > 0:
    s = unsearched[0]
    tmp, cnt = dfs(graph, unsearched, s)
    if cnt > result:
      result = cnt
      
  print(result)

def dfs(graph, unsearched, s):
  stack = deque([s])
  searched = [s]
  while len(stack):
    cur = stack.pop()
    unsearched.remove(cur)
    for i in graph[cur]:
      if i not in searched:
        stack.append(i)
        searched += [i]
  return searched, len(searched)

main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
M=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    if a>b:
        M[b-1][a-1]=1
    else:
        M[a-1][b-1]=1
ans=0
for m in M:
    ans=max(ans,m.count(1))
print(ans+1)