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 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+1)
for i in range(M):
    A,B = map(int,input().split())
    uf.union(A,B)
Group = uf.all_group_members()
A = uf.roots()
Answer = 0
for h in range(len(Group)):
    Answer = max(Answer,len(Group[A[h]]))
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 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 = list(map(int, input().split(" ")))

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

members = uf.all_group_members()
max_members = 1
for k in members:
    max_members = max(max_members, len(members[k]))
print(max_members)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
judge = [input().split() for i in range(m)]
people = list(range(1,n+1,1))
 
for i in judge :
  a = i[0]
  b = i[1]
  for k in range(n) :
    if people[k] == int(a) :
      people[k] = int(b)
  for j in judge :
    j[0] = j[0].replace(a,b)
    j[1] = j[1].replace(a,b)
 
groups = []
for i in range(n) :
  groups.append(people.count(i+1))
 
print(max(groups))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

# from typing import Optional
# from typing import List
# from typing import Dict
# from typing import Tuple
# from typing import Sequence


def main():
    args = input().split()
    N = int(args[0])
    M = int(args[1])

    groupTable = [i for i in range(N + 1)]

    for i in range(M):
        args = list(map(lambda x: int(x), input().split()))
        if groupTable[args[0]] > groupTable[args[1]]:
            groupTable[args[0]] = groupTable[args[1]]
        else:
            groupTable[args[1]] = groupTable[args[0]]

    maxNum = 0
    for i in range(1, N + 1):
        counter = groupTable.count(i)
        maxNum = max(maxNum, counter)

    print(maxNum)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

# from typing import Optional
# from typing import List
# from typing import Dict
# from typing import Tuple
# from typing import Sequence


def main():
    args = input().split()
    N = int(args[0])
    M = int(args[1])

    groupList = list()
    hitDict = set()
    groupTable = [i for i in range(N + 1)]

    for i in range(M):
        args = list(map(lambda x: int(x), input().split()))
        if groupTable[args[0]] > groupTable[args[1]]:
            groupTable[args[0]] = groupTable[args[1]]
        else:
            groupTable[args[1]] = groupTable[args[0]]

    maxNum = 0
    for i in range(1, N + 1):
        counter = len(list(filter(lambda x: x == i, groupTable)))
        maxNum = max(maxNum, counter)

    print(maxNum)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
if M == 0:
    print(1)
else:
    D = {}
    count = 0
    friends = []
    while count < M:
        A, B = map(int,input().split())
        if A not in D and B not in D:
            D[A] = len(friends)
            D[B] = D[A]
            friends += [[A,B]]
        elif A in D and B not in D:
            friends[D[A]] += [B]
            D[B] = D[A]
        elif B in D and A not in D:
            friends[D[B]] += [A]
            D[A] = D[B]
        elif A in D and B in D:
            if D[A] != D[B]:
                d = D[B]
                for K in friends[D[B]]:
                    D[K] = D[A]
                friends[D[A]] += friends[d]
        count += 1
    print(max(len(f) for f in friends))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)


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())
 
u = UnionFind(n)
 
for i in range(m):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  u.union(a,b)
 
res = u.all_group_members()
mxsz = 0
for i in res:
  mxsz = max(mxsz, len(res[i]))
print(mxsz)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
mat=[[1 if i==j else 0 for j in range(N)] for i in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    mat[a-1][b-1]=1
    mat[b-1][a-1]=1
mat2=[[j for j in i] for i in mat]
for i in range(N-1):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if (mat[i][j]==1)&(mat[i][k]==1):
                mat[j][k]=1
                mat[k][j]=1
maxmax=0
for i in mat:
    if maxmax<sum(i):
        maxmax=sum(i)
maxmax
print(maxmax)

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
    if B in i:
      b = i
  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())
A = [[0 for i in range(n)] for j in range(n)]
B = [0 for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if A[a][b] == 0:
    B[a] += 1
    B[b] += 1
    A[a][b] = 1
    A[b][a] = 1
  else:
    continue

print(max(B)+1)

Submission status: Time Limit Exceeded

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

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

grf=[[0]*n for i in range(n)]
grf=np.array(grf)

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

n, labels = connected_components(grf)

from collections import Counter
counter = Counter(labels)

print(counter.most_common()[0][1])

Submission status: Time Limit Exceeded

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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



def main():
    N, M = map(int, input().split())
    unf = UnionFind(N)
    for i in range(M):
        A, B = map(int, input().split())
        if not unf.same(A-1, B-1):
            unf.union(A-1, B-1)
    
    groups = unf.all_group_members()

    sizes = []
    for k, i in groups.items():
        sizes.append(len(groups[k]))
    
    group_nums = len(sizes)
    print(max(sizes))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
A = [[0 for i in range(n)] for j in range(n)]
B = [0 for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if A[a][b] == 0:
    B[a] += 1
    B[b] += 1
    A[a][b] = 1
    A[b][a] = 1

print(max(B)+1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
N,M=map(int,input().split())
mem=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    if b-1 not in mem[a-1]:
        mem[a-1].append(b-1)
    if a-1 not in mem[b-1]:
        mem[b-1].append(a-1)


inf=10**7
ans=0
vist=[0]*N
arr=[inf]*N
for i in range(N):
    if vist[i]==1:
        continue
    hq=[(0,i)]
    cnt=1
    while hq:
        d,node=hq.pop()
        vist[node]=1
        for next in mem[node]:
            if vist[next]==0 and d<arr[next]:
                arr[next]=min(d+1,arr[next])
                hq.append((arr[next],next))
                cnt+=1
        #print(hq,d)        
                
    ans=max(cnt,ans)
    #print(ans)
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
g = [set() for i in range(n)]
visited = [False] * n
group = []

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

for i in range(n):
    if visited[i]:
        continue
    s = set()
    q = [i]
    while len(q) > 0:
        p = q.pop()
        visited[p] = True
        s.add(p)
        for x in g[p]:
            if visited[x]:
                continue
            q.append(x)
    group.append(s)

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

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split(" ")) 
Y=[] 
Z=[] 
A=set() 
for _ in range(M): 
    y,z=map(int,input().split()) 
    if y<z: 
        A.add((y,z)) 
    else: 
        A.add((z,y)) 
for i in A:
    Y.append(i[0]) 
    Z.append(i[1]) 
b=[int(i+1) for i in range(N)]

def g(x): 
    try: 
        b.remove(x)
    except ValueError:
        return
        
    count.append(0) 
    while x in Y: 
        s=Y.index(x) 
        t=Z[s] 
        del Y[s] 
        del Z[s] 
        g(t) 
    return 
result=0 
while b!=[]: 
    count=[] 
    g(b[0]) 
    result=max(len(count),result) 
print(result)

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)

    r[a] = r[a] | r[b]
    r[b] = r[a] | r[b]

for k in r.keys():
    r[k] = r[k] - set([k])

group = [list(range(1, N+1))]
while 1:
    group.append([])
    completed = False
    for p in group[-2]:
        for f in r[p]:
            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:
n, m = map(int, input().split())
d = {}

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
# Union-Find
a=list(range(n))
def find(x):
  while a[x] != x:
    a[x] = a[a[x]]
  return a[x]

for _ in range(m):
  x,y=map(int,input().split())
  x,y=find(x-1),find(y-1)
  if x == y: continue
  a[y]=x

count=[0]*n
for i in range(n):
  count[find(i)] += 1
print(max(count))

Submission status: Time Limit Exceeded

Solution code:
import queue
import sys

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

conne = [[0]*n for _ in range(n)]
visited = [0]*n

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

ans=0
for i in range(n):
    
    d=1
    count=0
    if visited[i]==0:
        visited[i]=1
        q=queue.Queue()
        q.put((i,d))
        count+=1
        
        while not q.empty():
            x,d = q.get()
            
            for j in range(n):
                if visited[j]==0 and conne[x][j]==1:
#                    print(i,j)
                    visited[j]=1
                    count+=1
                    q.put((j,d+1))
                    
                    
    ans = max(count,ans)
    
print(ans)

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 = hit.union(tup, {A, B})
            else:
                hit = 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:
import sys
sys.setrecursionlimit(100000)
N,M=map(int,input().split(" ")) 
Y=[] 
Z=[] 
A=set() 
for _ in range(M): 
    y,z=map(int,input().split()) 
    if y<z: 
        A.add((y,z)) 
    else: A.add((z,y)) 
for i in A:
    Y.append(i[0]) 
    Z.append(i[1]) 
b=[int(i+1) for i in range(N)]

def g(x): 
    try: 
        b.remove(x)
    except ValueError:
        return
        
    count.append(0) 
    while x in Y: 
        s=Y.index(x) 
        t=Z[s] 
        del Y[s] 
        del Z[s] 
        g(t) 
    while x in Z: 
        s=Z.index(x) 
        t=Y[s] 
        del Y[s] 
        del Z[s] 
        g(t)
    return 
result=0 
while b!=[]: 
    count=[] 
    g(b[0]) 
    result=max(len(count),result) 
print(result)

Submission status: Time Limit Exceeded

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc177/abc177_d
import sys
from collections import deque

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

class node:
    def __init__(self, i):
        self.i = i
        self.adj = {self}
        self.visited = False
    
    def join(self, B):
        self.adj.add(B)
        B.adj.add(self)

def bfs(tar):
    q = deque()
    q.append(tar)
    cnt = 0
    while (q):
        tar = q.popleft()
        if not tar.visited:
            cnt += 1
        tar.visited = True
        q.extend(adj for adj in tar.adj if not adj.visited)
    return cnt

def main():
    N, M = i2nn()
    G = [node(i) for i in range(N + 1)]
    for _ in range(M):
        A, B = i2nn()
        G[A].join(G[B])
    ans = 0
    for tar in G[1:]:
        if not tar.visited:
            ans = max(bfs(tar), ans)
    print(ans)
    return

main()

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 = [None]*N
ans = -1

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

Submission status: Time Limit Exceeded

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

c = []
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)
            break
    else:
        c.append(set())
        c[-1].add(a)
        c[-1].add(b)
if m == 0:
    print(1)
else:
    print(max(map(len, c)))

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
ed = []
for _ in range(M):
    ed.append(list(map(int, input().split())))
import networkx as nx
G = nx.Graph()
G.add_edges_from(ed)
ans = 1
for comp in nx.connected_components(G):
    ans = max(ans, len(comp))
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 = set([node])
    while q:
        v = q.popleft()
        for n in r[v]:
            if n not in visited:
                if isinstance(r[v], list):
                    visited = visited | set(r[v])
                else:
                    q.append(n)
                    visited.add(n)
    return list(visited - set([node]))

for i in range(1,N+1):
    r[i] = bfs(r, i)
    # print(r[i])

group = [list(range(1, N+1))]
while 1:
    group.append([])
    completed = False
    for p in group[-2]:
        for f in r[p]:
            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:
import collections
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int,input().split())
ans = 0
f = [-1]*N
for i in range(M):

  if f[A[i]-1] == -1 and f[B[i]-1] == -1:
    f[A[i]-1] = i
    f[B[i]-1] = i
  elif f[A[i]-1] != -1 and f[B[i]-1] == -1:
    f[B[i]-1] = f[A[i]-1]
  elif f[A[i]-1] == -1 and f[B[i]-1] != -1:
    f[A[i]-1] = f[B[i]-1]
  else:
    f = [f[B[i]-1] if j == f[A[i]-1] else j for j in f]
ff = [i for i in f if i != -1]
if ff != []:
  print(max(collections.Counter(ff).values()))
else:
  print(1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
frends = []
for i in range(m):
	frends.append(list(map(int, input().split())))
# print(frends)

matrix = [[0 for i in range(n)] for j in range(n)]
# print(matrix)
for i in range(m):
	matrix[frends[i][0]-1][frends[i][1]-1] = 1
	matrix[frends[i][1]-1][frends[i][0]-1] = 1
# print(matrix)

ans = 0
for i in range(n - 1):
	# print(matrix[i][i+1:])
	cnt = matrix[i][i+1:].count(1)
	# print(cnt)
	ans = max(ans, cnt)

print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

x = [[] for _ in range(N + 1)]
for a, b in AB:
    x[a].append(b)
    x[b].append(a)

for row in x:
    if len(row) >= 2:
        for v in combinations(row, 2):
            x[v[0]].append(v[1])
            x[v[1]].append(v[0])

l1 = []
l2 = [False] * (N + 1)

for i in range(1, N + 1):
    if l2[i]:
        continue
    l1.append([i])
    l2[i] = True
    for j in range(1, N + 1):
        flag=False
        if j == i or l2[j]:
            continue
        for k in l1[-1]:
            if j in x[k]:
                flag=True
                break
        if flag:
            continue
        l1[-1].append(j)
        l2[j] = 1
print(len(l1))

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)
    ans = max(ans, len(group))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import sys

n, m = map(int, input().split())
r = []
for _ in range(m):
    r.append(tuple(sorted(list(map(int, input().split())))))

for i in range(n):
    add_num = []
    for j in range(m):
        if r[j][0] == i+1:
            add_num.append(r[j][1])
        if len(add_num) != 0: 
            add_num = sorted(list(set(add_num )))
            for x in range(len(add_num)-1):
                for y in range(x, len(add_num)):
                    if (add_num[x],add_num[y]) not in r:
                        r.append((add_num[x],add_num[y]))
    
groups = []
for i in range(1, 1<<n):
    group = []
    for bit in range(n):
        if i&(1<<bit):
            group.append(bit+1)
    if all([c not in r for c in combinations(group, 2)]):
        groups.append(group)

        
groups.sort(key = lambda x: len(x))
groups.reverse()

group_gt = [i+1 for i in range(n)]
ans = 0

while True:
    ans += 1
    for gp_list in  combinations(range(len(groups)), ans):
        menber = []
        for index in gp_list:
            menber += groups[index]
        menber = sorted(menber)
        if menber == group_gt:
            print(ans)
            sys.exit()

Submission status: Time Limit Exceeded

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

def find_root(a):
    while d[a] != a:
        a = d[a]
    return a
    
for _ in range(m):
    i,j = map(int, input().split())
    if (not i in d) and (not j in d):
        d[i] = i
        d[j] = i
    elif (not i in d) and (j in d):
        d[i] = d[j]
    elif (i in d) and (not j in d):
        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]).most_common(1)[0][1])
else:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))
n = a[0]
m = a[1]

if m != 0:
  ab = [map(int, input().split()) for _ in range(m)]
  a, b = [list(i) for i in zip(*ab)]
  
  edge = [[0 for j in range(n)] for i in range(n)]
  for i in range(m):
    edge[a[i]-1][b[i]-1] = 1
    edge[b[i]-1][a[i]-1] = 1

  #print(set_list)

  ans = 1
  for i in range(n):
    aa = sum(edge[i])+1
    ans = max(aa,ans)

  print(ans)
else:
  print(1)

Submission status: Time Limit Exceeded

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

ans = 0
ans = max(number)
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] and b not in li[j]:
                	li[j].append(b)
                	flag=1
                elif a not in li[j] and b in li[j]:
                    li[j].append(a)
                    flag=1
                elif a in li[j] and b in li[j]:
                    break
                elif flag==0 and j==len(li)-1:
                    li.append([a,b])
        #print(li)
    ans=max([len(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())

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)]
groupNum = [1] * n

for i in range(n-1):
  for j in range(i+1, n):
    if(table[i][j] and group[i] != group[j]):
      if(group[i] > group[j]):
        groupNum[group[j]] += groupNum[group[i]]
        groupNum[group[i]] = 0
        group[i] = group[j]
      else:
        groupNum[group[i]] += groupNum[group[j]]
        groupNum[group[j]] = 0
        group[j] = group[i]

maxNum = 0
for i in range(n):
  maxNum = max(groupNum[i], maxNum)

print(maxNum)

Submission status: Time Limit Exceeded

Solution code:
import collections

N,M = map(int,input().split())
List = [[]]*N
List2 = [0]*N
for i in range(M):
    A,B = map(int,input().split())
    if(List[A-1] == 0 or List[B-1] == 0):
        List2[A-1] += 1
        List2[B-1] += 1
        List[A-1].append(B-1)
        List[B-1].append(A-1)
    else:
        cA = collections.Counter(List[A-1])
        cB = collections.Counter(List[B-1])
        if(cA[B-1] >= 1 and cB[A-1] >= 1):
            pass
        else:
            List2[A-1] += 1
            List2[B-1] += 1
            List[A-1].append(B-1)
            List[B-1].append(A-1)
print(max(List2)+1)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
m = [[i] for i in range(N)]
l = [0 for i in range(N)]
for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    for y, row in enumerate(m):
        try:
            Apos = (y, row.index(A))
            break
        except ValueError:
            pass
    for y, row in enumerate(m):
        try:
            Bpos = (y, row.index(B))
            break
        except ValueError:
            pass
    if not Apos[0] == Bpos[0]:
        if min(A,B) == A:
            m[Apos[0]] += m[Bpos[0]]
            m[Bpos[0]] = []
            l[Apos[0]] += (l[Bpos[0]] +1)
        else:
            m[Bpos[0]] += m[Apos[0]]
            m[Apos[0]] = []
            l[Bpos[0]] += (l[Apos[0]] +1)
print(max(l)+1)

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx

n,m=map(int,input().split())
a=[[tuple(i) for i in input().split()] for _ in range(m)]
g=nx.Graph()
g.add_edges_from(a)
o=1
for i in list(nx.connected_components(g)):
     o=max(o,len(i))
print(o)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
N,M = map(int,input().split())
A = [0] * M
#B = [0] * M
for i in range(M):
    A[i] = list(map(int,input().split()))
    if A[i][0] > A[i][1]:
        A[i][0],A[i][1] = A[i][1],A[i][0]
A = sorted(A, key = itemgetter(0))        
C = [set()]
if M != 0:
    C[0].add(A[0][0])
    C[0].add(A[0][1])
else:
    print(1)
    sys.exit()
for i in range(1,M):
    for j in range(len(C)):
        if A[i][0] in C[j]:
            C[j].add(A[i][1])
            continue
        elif A[i][1] in C[j]:
            C[j].add(A[i][0])
            continue
        else:
            C.append({A[i][0],A[i][1]})
            continue
ans = 0
for j in range(len(C)):
    if len(C[j]) > ans:
        ans = len(C[j])
print(ans)