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

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]

g = {i:[] for i in range(n+1)}

for a,b in ab:
    g[a].append(b)
    g[b].append(a)
    
seen = [0]*(n+1)
seen[1]=1
q = deque()
q.append(1)
grpsize=1

while 0 in seen[1:]:
    if len(q)>0:
        now = q.popleft()
        nextp = g[now]
        for i in nextp:
            if seen[i]==0:
                q.append(i)
                grpsize+=1
                seen[i]=grpsize
        
    else:
        for i in range(1,n+1):
            if seen[i]==0:
                grpsize=1
                seen[i]=grpsize
                q.append(i)
                break
                
print(max(seen))

Submission status: Time Limit Exceeded

Solution code:
def find(n):
    if root[n] < 0:
        return n
    else:
        root[n] = find(root[n])
        return root[n]

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if root[x] > root[y]:
        x, y = y, x

    root[x] += root[y]
    root[y] = x

def size(x):
    return -root[find(x)]

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

def member(x):
    rt = find(x)
    return [i for i in range(n) if find(i) == rt]

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

def member_count(x):
    return len(roots())

def all_group_members():
    return {r: member(r) for r in roots()}

n , m = map(int,input().split())
root = [-1 for i in range(n)]
for i in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    unite(a,b)

d = all_group_members()
ans = 0
for v in d.values():
    ans = max(ans,len(v))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent):
    global cnt
    children = fr[cur]
    for chi in children:
        if used[chi] != -1:
            continue
        if chi == parent:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur)
    return

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1)
    MAX = max(MAX, cnt)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent):
    global cnt
    children = fr[cur]
    for chi in children:
        if used[chi] != -1:
            continue
        if chi == parent:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur)
    return

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1)
    MAX = max(MAX, cnt)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent):
    global cnt
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur)
    return

for i in range(N):
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1)
    MAX = max(MAX, cnt)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    n, m = map(int, input().split())
    ab = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)

    ans = 0
    n_set = deque([i for i in range(n)])
    while n_set:
        g = set()
        queue = deque([n_set.popleft()])
        while queue:
            now = queue.popleft()
            if now in g:
                break
            g.add(now)
            for i in ab[now]:
                if i not in g:
                    queue.append(i)
                    g.add(i)
        ans = max(ans, len(g))
        n_set = deque(set(n_set) - g)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def d_friends():
    class UnionFind(object):
        def __init__(self, n):
            """要素番号は 0 スタートを前提とする"""
            self.num_element = n
            self.parents = [-1] * n  # 要素が根の場合は、-(グループの要素数) を格納

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

        def union(self, x, y):
            """要素 x が属するグループと要素 y が属するグループとを併合する"""
            u, v = self.find(x), self.find(y)

            if u == v:
                return

            # u のグループの方が要素数が少なかった (parents の 定義より)
            if self.parents[u] > self.parents[v]:
                u, v = v, u

            self.parents[u] += self.parents[v]  # u と同グループの要素数を増やす
            self.parents[v] = u  # v は u に繋げる

        def get_members(self, x):
            """要素 x が属するグループに属する要素をリストで返す"""
            root = self.find(x)
            return [i for i in range(self.num_element) if self.find(i) == root]

        def get_roots(self):
            """根となっている要素のすべてを返す"""
            return [i for i, x in enumerate(self.parents) if x < 0]

    N, M = [int(i) for i in input().split()]
    uf = UnionFind(N)
    for _ in range(M):
        a, b = [int(i) - 1 for i in input().split()]
        uf.union(a, b)
    return max([len(uf.get_members(r)) for r in uf.get_roots()])

print(d_friends())

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
f=lambda x:int(x)-1
l=[[] for _ in range(n)]
for i in range(m):
  a,b=map(f,input().split())
  l[a].append(b)
  l[b].append(a)
m=0  
vis=[]
for i in range(n):
  queue=[i]
  visit=set()
  visit.add(i)
  cnt=1
  while len(queue)>0:
    now=queue.pop(0)
    for j in l[now]:
      if j not in visit:
        visit.add(j)
        queue.append(j)
        cnt+=1
  m=max(m,cnt)
  vis+=list(visit)
  if len(vis)==n:
    break
print(m)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
f=lambda x:int(x)-1
l=[[] for _ in range(n)]
for i in range(m):
  a,b=map(f,input().split())
  l[a].append(b)
  l[b].append(a)
m=0  
for i in range(n):
  queue=[i]
  visit=set()
  visit.add(i)
  cnt=1
  while len(queue)>0:
    now=queue.pop(0)
    for j in l[now]:
      if j not in visit:
        visit.add(j)
        queue.append(j)
        cnt+=1
  m=max(m,cnt)
print(m)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline
read = stdin.buffer.read
def r_map(): return map(int, readline().rstrip().split())
def r_list(): return list(r_map())

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n + 1)
        self.rank = [0] * (n + 1)

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

    def unite(self, x, y) -> bool:
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
        return True

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

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

    def is_same(self, x, y) -> bool:
        return self.root(x) == self.root(y)

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

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


def main():
    N, M = r_map()
    uf = UnionFind(N)
    for _ in range(M):
        a, b = r_map()
        uf.unite(a, b)
    ans = 0
    for i in uf.all_group_members():
        ans = max(ans, uf.size(i))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
friends = [[] for _ in range(N)]

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

counted = [False]*N
def grouping(i): # return list of friends of i
	i_friends = friends[i]
	ret = [i]
	for f in i_friends:
		if counted[f]:
			continue
		counted[f] = True
		ret += grouping(f)
	return ret

group_list = []
for i in range(N):
	if counted[i]:
		continue
	counted[i] = True
	group_list.append(grouping(i))

gsize = [len(g) for g in group_list]
print(max(gsize))

Submission status: Time Limit Exceeded

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

for i in range(M):
    A,B=map(int,input().split())
    tree[A].append(B)
    tree[B].append(A)
kazoe=tree.copy()
hako=[]
for i in range(N+1):
    tree[i].append(i)

for i in range(1,N+1):
    if i in hako:
        continue
    for j in tree[i]:
        hako.append(j)
        kazoe[i]+tree[j]
        #print(kazoe[i])
for i in range(1,N+1):
    kazoe[i]=list(set(kazoe[i]))        

ans=0
for i in range(1,N+1):
    ans=max(len(kazoe[i]),ans)
print(ans)
#print(kazoe)

Submission status: Time Limit Exceeded

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

uf = UnionFind(N)
for i in range(M):
    a, b = AB[i]
    uf.union(a, b)
    
ans = 0
for val in uf.all_group_members().values():
    ans = max(ans, len(val))

print(ans)

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

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

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


N, M = map(int, input().split()) 
union_find = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    union_find.union(A, B)

answer = 0
for i in range(N):
    answer = max(answer, union_find.size(i))

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
import sys
sys.setrecursionlimit(1000000)

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = self.id

N, M = [int(i) for i in input().split()]
P = [Node(i) for i in range(N)]

def root(a):
    if a.id == a.parent:
        return a.id
    else:
        id = root(P[a.parent])
        return id

def union(a, b):
    p = root(a)
    q = root(b)
    if p == q:
        return
    else:
        P[q].parent = p

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

c = defaultdict(int)
for i in range(N):
    c[root(P[i])] += 1
    maxc = 0
for key in c.keys():
    if maxc < c[key]:
        maxc = c[key]
print(maxc)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
friend=[[] for _ in range(N)]
for i in range(M):
    A,B=map(int,input().split())
    friend[A-1].append(B-1)
    friend[B-1].append(A-1)
ans=0
ischecked=[0]*N
for i in range(N):
    if ischecked[i]==1:
        continue
    group=1
    ischecked[i]=1
    ship=friend[i]
    while ship:
        nex=ship.pop(0)
        if ischecked[nex]==1:
            continue
        ischecked[nex]=1
        group+=1
        ship.extend(friend[nex])
    ans=max(ans,group)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def return_par(self):
        return self.par

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


unionfind = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    unionfind.union(x, y)
    
par = unionfind.return_par()

ans = 0
for num in range(1, n+1):
    ans = max(ans, par.count(num))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
while True:
    count = 0
    for i in range(n):
        for j in range(n):
            if i != j and i in ar[j]:
                for r in ar[j]:
                    if r not in ar[i] and r != i:
                        ar[i].append(r)
                        count += 1
    if count == 0:
        break
br = []
for r in ar:
    br.append(len(set(r)))
print(max(br) + 1)

Submission status: Time Limit Exceeded

Solution code:
# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

from collections import defaultdict
d = defaultdict(set)

for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    d[a].add(b)
    d[b].add(a)

def bfs(i):
    obs = {i}
    passed = {i}

    # get next_obs
    before = {i}
    while True:
        after = set()
        for i in before:
            after |= d[i]
        before = after - passed
        passed |= after
        if len(after) == 0:
            return len(passed)

print(max([bfs(i) for i in range(1, N+1)]))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
while True:
    count = 0
    for i in range(n):
        for j in range(n):
            if i != j and i in ar[j]:
                for r in ar[j]:
                    if r not in ar[i] and r != i:
                        ar[i].append(r)
                        count += 1
    if count == 0:
        break
br = []
for i in range(n):
    if i not in br:
        br.append(i)
        count += 1
        for j in range(n):
            if j not in ar[i]:
                br.append(j)
print(count)

Submission status: Time Limit Exceeded

Solution code:
# 接続最大クラスタのサイズが答え？

N, M = [int(x) for x in input().split(' ')]

from collections import defaultdict
d = defaultdict(set)

for i in range(M):
    a, b = [int(x) for x in input().split(' ')]
    d[a].add(b)
    d[b].add(a)

def bfs(i):
    obs = {i}
    passed = {i}

    # get next_obs
    before = {i}
    while True:
        after = set()
        for i in before:
            after |= d[i]
        before = after - passed
        passed |= after
        if len(after) == 0:
            return passed
    return len(passed)

print(max(len(bfs(i)) for i in range(1, N+1)))

Submission status: Time Limit Exceeded

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
p[0]=1

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[i-1]==-1:
            if p[j-1]==-1:
                if i<j:
                    p[i-1]=i
                    p[j-1]=i
                else:
                    p[i-1]=j
                    p[j-1]=j
            else:
                p[i-1]=p[j-1]
        else:
            if p[j-1]==-1:
                p[j-1]=p[i-1]
            else:
                if p[i-1]<p[j-1]:
                    p[i-1]=p[j-1]
                else:
                    p[j-1]=p[i-1]

for i,a in enumerate(p):
    if i!=a-1 and a>=0 and p.count(i+1)>1:
        p=[a if k==i+1 else k for k in p]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
p[0]=1

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[i-1]==-1:
            if p[j-1]==-1:
                if i<j:
                    p[i-1]=i
                    p[j-1]=i
                else:
                    p[i-1]=j
                    p[j-1]=j
            else:
                p[i-1]=p[j-1]
        else:
            if p[j-1]==-1:
                p[j-1]=p[i-1]
            else:
                if p[i-1]<p[j-1]:
                    p[i-1]=p[j-1]
                else:
                    p[j-1]=p[i-1]

for i,a in enumerate(p):
    if i!=a-1 and a>=0 and p.count(i+1)>1:
        p=[i if k==a else k for k in p]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

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

c = [False for i in range(N)]

for i in range(N-2):
    if c[i]:
        continue
    else:
        c[i] = True 

    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
                c[a] = True
                c[a] = True
                

m = 0

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

print(m)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=np.array([-1]*N)
p[0]=1

for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[i-1]==-1:
            if p[j-1]==-1:
                if i<j:
                    p[i-1]=i
                    p[j-1]=i
                else:
                    p[i-1]=j
                    p[j-1]=j
            else:
                p[i-1]=p[j-1]
        else:
            if p[j-1]==-1:
                p[j-1]=p[i-1]
            else:
                if p[i-1]<p[j-1]:
                    temp1=p[j-1]
                    temp2=p[i-1]
                else:
                    temp1=p[j-1]
                    temp2=p[i-1]
                p=[temp2 if k==temp1 else k for k in p]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
import collections as col
from collections import defaultdict as dd

d=dd(list)

N,M=map(int, input().split())
p=[-1]*N
cnt=[0]*N
p[0]=1
cnt[0]=1
for _ in range(M):
    i,j=map(int, input().split())
    if i>j:
        i,j=j,i
    d[i].append(j)

for i in d:
    for j in d[i]:
        if p[i-1]==-1:
            if p[j-1]==-1:
                if i<j:
                    p[i-1]=i
                    p[j-1]=i
                else:
                    p[i-1]=j
                    p[j-1]=j
            else:
                p[i-1]=p[j-1]
        else:
            if p[j-1]==-1:
                p[j-1]=p[i-1]
            else:
                if p[i-1]<p[j-1]:
                    temp1=p[j-1]
                    temp2=p[i-1]
                else:
                    temp1=p[j-1]
                    temp2=p[i-1]
                p=[temp2 if k==temp1 else k for k in p]

ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
friends = [{i} for i in range(n)]

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

flg = [0]*n
max_ans = 0

for i in range(n):
    if flg[i]:
        continue
    for j in range(i+1, n):
        if not friends[i].isdisjoint(friends[j]):
            friends[i] |= friends[j]
            flg[j] = 1
    ans = len(friends[i])
    max_ans = max(max_ans, ans)

print(max_ans)

Submission status: Time Limit Exceeded

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

for i in range(M):
	Ai, Bi = map(int, input().split())
	if Ai > Bi:
		z = Ai
		Ai = Bi
		Bi = z
	A.append(Ai)
	B.append(Bi)

for i in range(M - 1):
	for j in range(i + 1, M):
		if A[i] > A[j]:
			z = A[i]
			A[i] = A[j]
			A[j] = z
			z = B[i]
			B[i] = B[j]
			B[j] = z

G[0] = x = 1
for i in range(N):
	for j in range(M):
		if A[j] == i + 1:
			G[B[j] - 1] = G[A[j] - 1]
	if min(G) == 0:
		x += 1
		for k in range(N):
			if G[k] == 0:
				G[k] = x
				break

answer = 0
for i in range(max(G)):
	check = 0
	for j in G:
		if j == i + 1:
			check += 1
	answer = max(answer, check)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
A = [[] for i in range(N)]
checkd = [False]*N
for _ in range(M):
    a,b = (map(lambda a: int(a)-1, input().split()))
    A[a].append(b)
    A[b].append(a)
nextS = set(range(N))
ans = 0
while len(nextS)>0:
    s = nextS.pop()
    if checkd[s]: 
        continue
    count = 0
    que = [s]
    while len(que)>0:
        nn = que.pop(0)
        if checkd[nn]:
            continue
        checkd[nn] = True
        nextS.discard(nn)
        count += 1
        que += A[nn]
    ans = max(count,ans)


print(ans)

Submission status: Time Limit Exceeded

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

checked = [False for _ in range(N)]
ans = 0
for i in range(N):
    if checked[i]:
        continue

    checked[i] = True
    A = G[i]
    tmp = 1
    while len(A) > 0:
        e = A.pop()
        if checked[e]:
            continue
        checked[e] = True
        tmp += 1
        A = A + G[e]

    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {n : set() for n in range(N)}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    friends_map[a].add(b)
    friends_map[b].add(a)
    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = [0] * N
count = 0
while stack:
    now = stack.popleft()

    if watch[now] == 0:
        remain_user.discard(now)
        count += 1
        watch[now] = 1

    if now in friends_map:
        for next_node in friends_map[now]:
            if watch[next_node] == 0:
                stack.appendleft(next_node)

    if not stack:
        max_group = max(count, max_group)

        if remain_user:
            stack.appendleft(remain_user.pop())
            count = 0

print(max_group)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    if a in friends_map:
        friends_map[a].add(b)
    else:
        friends_map[a] = {b}

    if b in friends_map:
        friends_map[b].add(a)
    else:
        friends_map[b] = {a}

    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = [0] * N
count = 0
while stack:
    now = stack.popleft()
    remain_user.discard(now)

    if watch[now] == 0:
        count += 1
        watch[now] = 1

    if now in friends_map:
        for next_node in friends_map[now]:
            if watch[next_node] == 0:
                stack.appendleft(next_node)
                remain_user.discard(next_node)

    if not stack:
        max_group = max(count, max_group)

        if remain_user:
            stack.appendleft(remain_user.pop())
            count = 0

print(max_group)

Submission status: Time Limit Exceeded

Solution code:
n, m = (int(x) for x in input().split())
dummy = [input().split() for i in range(m)]

gl = []
for x in range(n):
    friendset = set()
    friendset.add(str(x+1))
    gl.append(friendset)

for x in gl:
    for y in dummy:
        if y[0] in x or y[1] in x:
            x.add(y[0])
            x.add(y[1])

max = 0
for x in gl:
    for y in gl:
        if not x.isdisjoint(y):
            x = x | y
            if max < len(x):
                max = len(x)

print(max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {}
remain_user = set()
for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    if a in friends_map:
        friends_map[a].add(b)
    else:
        friends_map[a] = {b}

    if b in friends_map:
        friends_map[b].add(a)
    else:
        friends_map[b] = {a}

    remain_user.add(a)
    remain_user.add(b)

stack = deque()
stack.appendleft(0)

max_group = 1
watch = set()
while stack:
    now = stack.popleft()
    remain_user.discard(now)
    watch.add(now)

    if now in friends_map:
        for next_node in friends_map[now]:
            if not next_node in watch:
                stack.appendleft(next_node)
                remain_user.discard(next_node)

    if not stack:
        if len(watch) > max_group:
            max_group = len(watch)

        if remain_user:
            stack.appendleft(remain_user.pop())
            watch = set()

print(max_group)