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:
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 group_count(self):
        return len(self.roots())
    
    def max_group_length(self):
        tmp_max = 0
        for r in self.roots():
            tmp_max = max(tmp_max, len(self.members(r)))
        return tmp_max

    def __str__(self):
        return str(self.max_group_length())
    
N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    A, B = map(lambda x:int(x) - 1, input().split())
    uf.union(A, B)

ans = str(uf)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, M = list(map(int, input().split()))
groups = {i+1:-1 for i in range(N)}
cnt = 0
for _ in range(M):
    a, b = list(map(int, input().split()))
    if groups[a]!=-1 and groups[b]!=-1:
        a_val = groups[a]
        b_val= groups[b]
        for i in range(N):
            if groups[i+1]==b_val:
                groups[i+1]=a_val
    if groups[a]==-1 and groups[b]==-1:
        groups[a] = cnt
        groups[b] = cnt
        cnt+=1
    elif groups[a]==-1:
        groups[a] = groups[b]
    elif groups[b]==-1:
        groups[b] = groups[a]
if cnt==0:
    print(1)
else:
    for n,m in Counter(groups.values()).most_common():
        if n==-1:
            continue
        print(m)
        break

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]):
        for i in d[b] - d[a]:
            if i != b:
                d[i] = d[a]
        d[a].update(d[b])
        d[b] = d[a]
        d[a].add(b)
    else:
        for i in d[a] - d[b]:
            if i != a:
                d[i] = d[b]
        d[b].update(d[a])
        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 solve():
    n, m = map(int, input().split())
    arr = [[0 for _ in range(n)] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        arr[a][b] = 1
        arr[b][a] = 1

    ans = max([arr[i].count(1)+1 for i in range(n)])
    print(ans)


def main():
    t = 1
    while t > 0:
        solve()
        t -= 1


main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ed = [0] * (n+1)


def rm(nu):
    if len(vr) == 0:
        return 0
#    print(vr)
    if nu not in vr:
        return 0
    curr = vr.pop(vr.index(nu))
#    print(curr)
    if ed[curr] == 0:
        return 1
    else:
        tmp = 1
#        print(f"2edc:{ed[curr]}")
        for p in ed[curr]:
            tmp += rm(p)
#            print(f"tr:{tmp}")
#        print(f"ftmp:{tmp}")
        return tmp


for i in range(m):
    t1, t2 = map(int, input().split())
    if ed[t1] == 0:
        ed[t1] = [t2]
    else:
        if t2 not in ed[t1]:
            ed[t1].append(t2)
    if ed[t2] == 0:
        ed[t2] = [t1]
    else:
        if t1 not in ed[t2]:
            ed[t2].append(t1)
vr = list(range(n, 0, -1))
maxs = 0
#print(vr, ed)
while len(vr) != 0:
    maxs = max(maxs, rm(vr[-1]))
print(maxs)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {x:-1 for x in range(1,n+1)}

def find_root(a):
    while d[a] != a:
        a = d[a]
    return a
    
for _ in range(m):
    i,j = map(int, input().split())
    if d[i] == -1 and d[j] == -1:
        d[i] = i
        d[j] = i
    elif d[i] == -1 and d[j] != -1:
        d[i] = d[j]
    elif d[i] != -1 and d[j] == -1:
        d[j] = d[i]
    else:
        if d[i] != d[j]:
            d[find_root(j)] = d[find_root(i)]
            
from collections import Counter
if m > 0:
    print(Counter([find_root(x) for x in d if d[x] != -1]).most_common(1)[0][1])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
import collections

sys.setrecursionlimit(1000000)

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            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

        self.parents[y] = x


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

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A - 1, B - 1)

hoge = [uf.find(i) for i in range(N)]

#print(hoge)
hogehoge = collections.Counter(hoge).most_common()

print(hogehoge[0][1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
friendlist={i+1:0 for i in range(N)}
sumg=0
for m in range(M):
  A,B=map(int,input().split())
  if friendlist[A]==0 and friendlist[B]==0:
    sumg+=1
    friendlist[A]=sumg
    friendlist[B]=sumg
  elif friendlist[A]==0:
    friendlist[A]=friendlist[B]
  elif friendlist[B]==0:
    friendlist[B]=friendlist[A]
  elif friendlist[A]!=friendlist[B]:
    k=friendlist[B]
    for i in range(1,N+1):
      if friendlist[i]==k:
        friendlist[i]=friendlist[A]
maxlist=[0 for _ in range(sumg+1)]
for i in range(1,N+1):
  maxlist[friendlist[i]]+=1
if M==0:
  print(1)
else:
  print(max(maxlist[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())

l = []
A = 0
B = 0
ans = 1
if M > 0:
    A, B = map(int, input().split())
    l.append((A, B))
for i in range(M-1):
    A, B = map(int, input().split())
    hit = None
    for tup in l:
        if A in tup or B in tup:
            if hit != None:
                hit = tuple(set(hit+tup+(A, B)))
            else:
                hit = tuple(set(tup+(A, B)))
            l.remove(tup)
    if hit != None:
        l.append(hit)
    else:
        l.append((A, B))

if len(l) > 0:
    ans = 1
for item in (l):
    if ans < len(item):
        ans = len(item)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
friend_list = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    friend_list[a][b] = 1
    friend_list[b][a] = 1

ans = 0
for friend in friend_list:
    sum_friend = sum(friend)
    ans = max(ans, sum_friend)
print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
t = dict()
nt = dict()

for i in range(1, n+1):
    t[i] = set()

for a, b in ab:
    t[a].add(b)
    t[b].add(a)

s = set()
ans = dict()
for i in range(1, n+1):
    if len(s) == n:
        break
    if i not in s:
        ans[i] = []
        for j in range(i+1, n+1):
            if j not in t[i] and j not in s and ("".join(map(str, sorted(list(t[j])))) not in "".join(map(str, sorted(list(t[i])))) or len(t[j]) == 0):
                ans[i].append(j)
                s.add(j)
                t[i] = t[i] | t[j]
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
"""
N = int(input())
A = list(map(int,input().split()))
ans = 0
mod = 1000000007

for i in range(N-1):
    for j in range(i+1,N):
        ans += A[i]*A[j]
        ans = ans%mod
print(ans)
"""
from collections import deque

N,M = map(int,input().split())
MAP = [[False for x in range(N+1)] for x in range(N+1)]
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    MAP[A][B]=True
    MAP[B][A]=True
LIST = list(range(1,N+1))

while(True):
    if(LIST != []):
        group = set()
        group.add(LIST[0])
        q = deque()
        q.append(LIST[0])
        while(len(q) != 0):
            a = q.popleft()
            MAP[:][a] = ""
            for i in range(N+1):
                if(MAP[a][i]):
                    q.append(i)
                    group.add(i)
                    try:
                        LIST.remove(i)
                    except:
                        pass
                MAP[a][i] = ""
        if(ans < len(group)):
            ans = len(group)
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
N, M = [int(a) for a in input().split()]
r = defaultdict(set)
for _ in range(M):
    a, b = [int(a) for a in input().split()]
    r[a].add(b)
    r[b].add(a)

def bfs(r, node):
    q = deque()
    q.append(node)
    visited = [node]
    while q:
        v = q.popleft()
        for n in r[v]:
            if n not in visited:
                q.append(n)
                visited.append(n)
    return visited[1:]

friends = []
for i in range(1,N+1):
    friends.append(bfs(r, i))

group = [list(range(1, N+1))]
while 1:
    group.append([])
    completed = False
    for p in group[-2]:
        for f in friends[p-1]:
            if f in group[-2]:
                group[-1].append(f)
                group[-2].remove(f)
    if len(group[-1])==0:
        break

print(len(group)-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

friends=[0]+[[] for _ in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    friends[A].append(B)
    friends[B].append(A)
    
    
que=deque([1])
ex=[1]
num=[]

while True:
    count=1
    while que:
        x=que.popleft()
        for xx in friends[x]:
            if xx not in ex:
                que.append(xx)
                ex.append(xx)
                count+=1
    num.append(count)
    
    if len(ex)==N:
        break
    
    for i in range(1,N+1):
        if i not in ex:
            que.append(i)
            ex.append(i)
            break

print(max(num))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = list()
b = list()
for i in range(m):
  c, d = map(int,input().split())
  a.append(c)
  b.append(d)
  
itta = [0 for i in range(n)]

def sagasu(t):
  ze = []
  itta[t-1] = 1
  for i in range(m):
    if a[i] == t and itta[b[i]-1] != 1:
      ze.append(b[i])
      itta[b[i]-1] = 1
    elif b[i] == t and itta[a[i]-1] != 1:
      ze.append(a[i])
      itta[a[i]-1] = 1
  return ze

z = [1]
gokei = 0
while True:
  if itta.count(0) == 0:
    break
  z = [(itta.index(0)) + 1]

  for i in z:
    kaku = sagasu(i)
    if len(kaku) == 0:
      break
    z.extend(kaku)
    
  if gokei<len(z):
    gokei = len(z)
print(gokei)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
import collections

sys.setrecursionlimit(1000000)

class UnionFind2:
    def __init__(self, size):
        # 負の値はルート (集合の代表)
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            self.table[s2] = s1
            return True
        return False


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

for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)

hoge = [uf.find(i) for i in range(N)]

# print(hoge)
hogehoge = collections.Counter(hoge).most_common()

print(hogehoge[0][1])

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.insert( 0, j )
        friend[ j ].remove( i )

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
import os
from collections import deque


def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

N,M = LI()
AB = [LI() for _ in range(M)]

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

# 無向グラフ
G = []
for _ in [0]*N:
    G.append([False]*N)

for r in AB:
    f = r[0]-1
    t = r[1]-1
    G[f][t] = True
    G[t][f] = True

used = [False] * N

ss = []
for i in range(N):
    if used[i]==True:
            continue
    s = set()
    que = deque([])
    que.append(i)
    while que:
        p = que.popleft() 
        if used[p]==True:
            continue
        used[p]=True   
        s.add(p)
        for i, x in enumerate(G[p]):
            if x == True:
                if used[i]==True:
                    continue
                que.append(i)
    ss.append(len(s))


    # for i, x in enumerate(G[i]):
    #     if x == True:
    #         if used[i]==True:
    #             continue
    #         for j,y in enumerate(x):
    #             if used[j]==True:
    #                 continue
    #             if x == True and used[i]==False:
    #                 s.add(i)


    # l = [i for i, x in enumerate(G[i]) if x == True and used[i]==False]
    # for j in l:
    #     used[j]=True
    #     s.add(j)
    #     for i,x in enumerate(G[i]):
    #         if x == True and used[i]==False:
    #             s.add(i)

print(max(ss))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M = map(int,input().split())
graph = []
fship = []
for i in range(M):
    x,y = map(int,input().split())
    if x>y:
        x,y = y,x
    if [x-1,y-1] 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:
from collections import deque
import copy

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

edge_list = [set() for i in range (N)]


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

for i in range (N):
    d =deque(edge_list[i])
    while d:
        a = d.popleft()
        el = copy.copy(edge_list[a])
        for j in range (len(edge_list[a])):
            aj = el.pop()
            if (aj not in edge_list[i]) and i != aj:
                edge_list[i].add(aj)
                d.append(aj)


edge_list = list(map(len,edge_list))

print(max(edge_list)+1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
F = []
for _ in range(M):
    A, B = map(int, input().split())
    if len(F) == 0:
        F.append([A, B])
    isExist = False
    for f in F:
        if A in f or B in f:
            f.append(A)
            f.append(B)
            isExist = True
    if not isExist:
        F.append([A, B])
if len(F) == 0:
    print(1)
else:
    ans = 1
    for f in F:
        ans = max(ans, len(list(set(f))))
    print(ans)

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 max_group_length(self):
        tmp_max = 0
        for r in self.roots():
            tmp_max = max(tmp_max, len(self.members(r)))
        return tmp_max

    def __str__(self):
        return str(self.max_group_length())
    
N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    A, B = map(lambda x:int(x) - 1, input().split())
    uf.union(A, B)

ans = str(uf)
print(ans)

Submission status: Time Limit Exceeded

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

friend_list = [[0] * (N + 1) for _ in range(N + 1)]
call_check = [0] * (N + 1)

for a, b in A_B:
    friend_list[a][b] = 1
    friend_list[b][a] = 1


ans = 0
for friend in friend_list:
    sum_friend = sum(friend)
    ans = max(ans, sum_friend)
print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
li=[]
ans=0
if m!=0: 
    for i in range(m):
        a,b=map(int,input().split())
        if len(li)==0:
            li.append([a,b])
        else:
            flag=0
            for j in range(len(li)):
                if a in li[j] or b in li[j]:
                    li[j].append(a)
                    li[j].append(b)
                    flag=1
                elif flag==0 and j==len(li)-1:
                    li.append([a,b])
        #print(li)
    ans=max([len(set(li[i])) for i in range(len(li))])
print(ans if m!=0 else 1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
index = 1
group = [0] * (n + 1) # 何番目のグループにいるか
groups = [set()]  # グループ
dicts = {}
for i in range(m):
  a, b = map(int, input().split())
  _a = group[a]
  _b = group[b]
  if _a == 0 and _b == 0: # 新しいグループ
    group[a] = index
    group[b] = index
    groups.append({a,b})
    index += 1
  elif _a == 0: # aが新人
    group[a] = _b
    groups[_b].add(a)
  elif _b == 0: # bが新人
    group[b] = _a
    groups[_a].add(b)
  elif _a != _b:  # a,bが別グループに所属
    if len(groups[_b]) < len(groups[_a]):
      for g in groups[_b]: # bのいるグループをaのいるグループに移行
        group[g] = _a
      groups[_a] = groups[_a] | groups[_b]
    else: # a,bが別グループに所属
      for g in groups[_a]: # aのいるグループをbのいるグループに移行
        group[g] = _b
      groups[_b] = groups[_b] | groups[_a]
ans = max(map(lambda g: len(g), groups))
print(max(ans,1))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
t = [-1*(i+1) for i in range(n)]
count = 0
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    if t[a] <= -1 and t[b] <= -1:
        count += 1
        t[a] = count
        t[b] = count
        continue
    if t[a] > -1 and t[b] > -1 and t[a] != t[b]:
        t[a] = max(t[a], t[b])
        t[b] = max(t[a], t[b])
        for i in range(n):
            if t[i] == min(t[a], t[b]):
                t[i] = max(t[a], t[b])
        continue
    if t[a] > -1 and t[b] > -1 and t[a] == t[b]:
        continue
    if t[a] <= -1:
        t[a] = t[b]
        continue
    if t[b] <= -1:
        t[b] = t[a]

print(
    max([t.count(i) for i in set(t)])
)

Submission status: Time Limit Exceeded

Solution code:
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
mod = 10**9 + 7

#maincode-------------------------------------------------

n,m = inm()
check = [-1] * n
friend = [[ ] for i in range(n)]
q = 0

for i in range(m):
    a,b = inm()
    a -= 1
    b -= 1
    friend[a].append(b)
    friend[b].append(a)

for i in range(n):
    if check[i] != -1:
        continue
    mark = i
    check[i] = mark
    q = friend[i][::]
    while(len(q) > 0):
        if check[q[0]] != -1:
            q.pop(0)
            continue
        for j in friend[q[0]]:
            if check[j] != -1:
                continue
            check[j] = mark
            q.append(j)
        check[q[0]] = mark
        q.pop(0)
        
ans = 0

for i in set(check):
    ans = max(ans,check.count(i))
print(ans)

Submission status: Time Limit Exceeded

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

G = [[0 for i in range(N)] for j in range(N)]

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

for i in range(N):
    G[i][i] = 1

for i in range(N-2):
    for a in range(i+1,N):
        if G[i][a] == 0:
            continue
        for b in range(i+2,N):
            if G[i][b] == 0:
                continue
            else:
                G[a][b] == 1
                G[b][a] == 1

m = 0

for i in range(N):
    m = max(m, sum(G[i]))

print(m)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = {x:-1 for x in range(1,n+1)}

def find_root(a):
    while d[a] != a:
        a = d[a]
    return a
    
for _ in range(m):
    i,j = map(int, input().split())
    if d[i] == -1 and d[j] == -1:
        d[i] = i
        d[j] = i
    elif d[i] == -1 and d[j] != -1:
        d[i] = d[j]
    elif d[i] != -1 and d[j] == -1:
        d[j] = d[i]
    else:
        if d[i] != d[j]:
            d[find_root(j)] = d[i]
            
from collections import Counter
if m > 0:
    print(Counter([find_root(x) for x in d if d[x] != -1]).most_common(1)[0][1])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n, m = MI()
    G = [set() for _ in range(n+1)]
    for _ in range(m):
        a, b =MI()
        G[a].add(b)
        G[b].add(a)
    for i in range(n+1):
        G[i] = list(G[i])
    num = [-1]*(n+1)
    seen = [False]*(n+1)
    stack = []
    for i in range(1, n+1):
        if not seen[i]:
            stack.append(i)
            while stack:
                vertex = stack.pop(-1)
                seen[vertex] = True
                num[vertex] = i
            
                for j in range(len(G[vertex])):
                    neighbor = G[vertex][j]
                    if not seen[neighbor]:
                        stack.append(neighbor)
    c = collections.Counter(num)
    print(c.most_common()[0][1])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
sets = [set("0")]
for i in range(M):
    AB = set(map(str, input().split()))
    flag = True
    for i in range(len(sets)):
        if len(AB&sets[i])>0:
            sets[i] = (AB|sets[i])
            flag = False
            break
    if flag:
        sets.append(AB)
ans = 0
for i in sets:
    ans = max(ans,len(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = sorted(set([tuple(map(int, input().split())) for _ in range(m)]))

c = []
flag = False
for i in ab:
    a, b = i[0], i[1]
    for i in c:
        if a in i or b in i:
            i.add(a)
            i.add(b)
            if len(i) == n:
                flag = True
    else:
        c.append(set())
        c[-1].add(a)
        c[-1].add(b)
    if flag:
        break
if m == 0:
    print(1)
else:
    print(max(map(len, c)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,m = map(int,input().split())
rel = [[i] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    rel[a].append(b)
    rel[b].append(a)

for i in range(n):
    rel[i] = set(rel[i])


for i in range(n):
    for j in range(n):
        if j in rel[i]:
            rel[i].union(rel[j])

ans = 0
for i in rel:
    ans = max(len(set(i)),ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def search(x, num):
    search_set = set()
    for y in edge[x]:
        if y in nodes:
            nodes.remove(y)
            search_set.add(y)
    for y in search_set:
        num = search(y, num+1)
    return num
        


(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = list(range(1,n+1))
ans = 1
for x in range(1,n+1):
    if x not in nodes:
        continue
    tmp = search(x, 0)
    ans = max(tmp, ans)
print(ans)

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