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:
n, m = map(int, input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
ans = 0
for i in list(uf.all_group_members().values()):
    ans = max(ans, len(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
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)
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    uf.union(a, b)

friends = uf.all_group_members()
max_group = 0
for member in friends.values():
    max_group = max(max_group, len(member))

print(max_group)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m=map(int,input().split())
f=[[] for _ in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    if not (b-1) in f[a-1]:
        f[a-1].append(b-1)
    if not (a-1) in f[b-1]:
        f[b-1].append(a-1)
chk=[False]*n
q=deque()
ans=0
for i in range(n):
    if chk[i]==True:
        continue
    q.append(i)
    chk[i]=True
    cnt=1
    while q:
        x=q.popleft()
        for nx in f[x]:
            if chk[nx]==True:
                continue
            q.append(nx)
            chk[nx]=True
            cnt+=1
    ans=max(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        #親の添字、親自身は木の要素数*-1をもつ
        self.root = [-1]*(n)
        #枝の最大長さ
        self.rank = [0]*(n)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
    #高さによる合併    
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return 
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]    
    
    def members(self, x):
        root = self.find_root(x)
        return [i for i in range(self.n) if self.find_root(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.root) 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()}
    
n, m = map(int,input().rstrip().split())
ab = [list(map(int,input().split()))for _ in range(m)]

u = UnionFind(n)
for a,b in ab:
    u.unite(a-1,b-1)
d =u.all_group_members()
ans = 0
for k in d:
    if ans < len(d[k]):
        ans = len(d[k])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

friends = [0 for _ in range(N)]
#print(friends)

for _ in range(M):
  A, B = map(int, input().split())
  if friends[A - 1] != 0:
    if friends[B - 1] != 0:
      for n in range(N):
        if n != B - 1 and friends[n] == friends[B - 1]:
          friends[n] = friends[A - 1]
      friends[B - 1] = friends[A - 1]
    else:
      friends[B - 1] = friends[A - 1]
  elif friends[B - 1] != 0:
    friends[A - 1] = friends[B - 1]
  else:
    friends[A - 1] = A
    friends[B - 1] = A
  #print(friends)


for i in range(N):
  if friends[i] == 0:
    friends[i] = i + 1
    
  #print(friends)
#print(Counter(friends))
print(max(Counter(friends).values()))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    C = [list(map(int, input().split())) for i in range(M)]
    F = [[0]*(N+1) for i in range(N+1)]
    for a,b in C:
        if F[a][b] == 0:
            F[a][b] += 1
        if F[b][a] == 0:
            F[b][a] += 1
    G = [1]*(N+1)
    for i in range(N+1):
        G[i] = sum(F[i])
    ans = max(G) + 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = (int(x) for x in input().split())
import numpy as np
from scipy.sparse.csgraph import dijkstra
friends = np.array([[0]*N for _ in range(N)])
for _ in range(M):
    a, b = (int(x) for x in input().split())
    friends[a-1, b-1] = 1
friends = dijkstra(friends,directed=False, unweighted=True)
ans = max(sum(x == 1 for x in friends[i,:]) for i in range(N))+1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i 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+1)
for i in range(m):
  uf.union(ab[i][0], ab[i][1])
ans=0
for i in range(uf.group_count()):
  if ans < len(uf.members(i)):
    ans = len(uf.members(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
AB = []
for m in range(M):
    AB.append([int(i)-1 for i in input().split()])
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N)
for ab in AB:
    uf.union(ab[0],ab[1])
group_dict = uf.all_group_members()
ans = 0
for key in group_dict.keys():
    ans = max(ans,len(group_dict[key]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
groups = [set(map(int, input().split())) for _ in range(M)]
new = []
ans = 1
if M > 0:
    ans = 2
    new.append(groups[0])


for i in range(1, len(groups)):
    flag = True
    for j in range(len(new)):
        tmp = new[j]&groups[i]
        if len(tmp) > 0:
            new[j] |= groups[i]
            flag = False
            ans = max(ans, len(new[j]))
            break
    if flag:
        new.append(groups[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l_c=[0 for i in range(N)]
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   l[b].append(a)
from collections import deque
def search(start):
   que=deque([start])
   after=deque([])
   while que:
      A=que.popleft()
      after.append(A)
      l_c[A]=1
      for i in l[A]:
         if i not in que and i not in after:
            que.append(i)
   return len(after)
ans=0
for i in range(N):
   if l_c[i] ==0:
      ans=max(ans,search(i))
   if ans>M//2+1:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

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 count_member_nums(self):
        return [len(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 main():
    n, m = MII()
    group = [MIIZ() for _ in range(m)]
    uf = UnionFind(n)
    for a, b in group:
        uf.union(a, b)
    print(max(uf.count_member_nums()))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def doubleset(doublelist):
    returnlist = []
    
    return [x for x in doublelist if x not in returnlist and not returnlist.append(x)]

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

tmplist = []
friendlist = [0 for i in range(N)]


for i in range(M):
    A, B = map(int, input().split())
    if A > B:
        tmplist.append([B, A])
    else:
        tmplist.append([A, B])


tmplist = doubleset(tmplist)

for i in range(len(tmplist)):
    friendlist[tmplist[i][0] - 1] += 1
    friendlist[tmplist[i][1] - 1] += 1

print(max(friendlist) + 1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
input = sys.stdin.readline
import functools

from collections import defaultdict

############ ---- Input Functions ---- ############

def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))

############ ---- Solution ---- ############

def diff(S, i, T):
    res = 0
    for j in range(len(T)):
        if S[i + j] != T[j]:
            res += 1
    return res

def solve():
    [N, M] = inlt()
    uf = [i for i in range(N)]
    rn = [1 for i in range(N)]

    def root(i):
        j = i
        while uf[j] != j:
            j = uf[j]
        uf[i] = j
        return j

    def union(i, j):
        if rn[i] > rn[j]:
            i, j = j, i
        ri = root(i)
        rj = root(j)
        if ri == rj:
            return
        uf[ri] = rj
        rn[rj] += rn[ri]

    for i in range(M):
        [a, b] = inlt()
        union(a - 1, b - 1)

    groups = defaultdict(int)
    res = 0
    for i in range(N):
        r = root(i)
        groups[r] += 1
        res = max(res, groups[r])
    
    return res

    

if len(sys.argv) > 1 and sys.argv[1].startswith("input"):
    f = open("./" + sys.argv[1], 'r')
    input = f.readline

res = solve()
print(str(res))

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)
AB=[tuple(map(int,input().split())) for _ in range(M)]
x=[uf.union(ab[0]-1,ab[1]-1) for ab in AB]

dic=uf.all_group_members()
print(max([len(d) for d in dic.values()]))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
AB = []
for m in range(M):
    AB.append([int(i)-1 for i in input().split()])
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N)
for ab in AB:
    uf.union(ab[0],ab[1])
group_dict = uf.all_group_members()
ans = 0
for key in group_dict.keys():
    ans = max(ans,len(group_dict[key]))
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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m=map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a,b = map(int, input().split())
    uf.union(a-1,b-1)
a=uf.all_group_members()
ans=0
for v in a.values():
    ans=max(ans,len(v))
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 __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:
def main():
    n,m = [int(v) for v in input().split()]
    if m==0:
        print(1)
        return
    groups = []
    g = [-1]*(n+1)
    for _ in range(m):
        a,b = [int(v) for v in input().split()]
        if g[a]!=-1 and g[b]!=-1:
            if g[a]==g[b]: continue
            gb = g[b]
            for no in groups[gb]:
                g[no] = g[a]
                groups[g[a]].append(no)
            groups[gb] = []
        elif g[a]!=-1:
            g[b] = g[a]
            groups[g[a]].append(b)
        elif g[b]!=-1:
            g[a] = g[b]
            groups[g[b]].append(a)
        else:
            g[a] = g[b] = len(groups)
            groups.append([a,b])
    # print(groups, g)
    ans = max([len(v) for v in groups])
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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())

friend = [[0]]
for i in range(M):
    for f in friend:
        if A[i] not in f and B[i] not in f:
            friend.append([A[i], B[i]])
        elif A[i] in f and B[i] not in f:
            f.append(B[i])
        elif A[i] not in f and B[i] in f:
            f.append(A[i])
        else:
            pass

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

friends = [0 for _ in range(N)]
#print(friends)

for _ in range(M):
  A, B = map(int, input().split())
  if friends[A - 1] != 0:
    if friends[B - 1] != 0:
      friends = [friends[A - 1] if n == friends[B - 1] else n for n in friends]
      friends[B - 1] = friends[A - 1]
    else:
      friends[B - 1] = friends[A - 1]
  elif friends[B - 1] != 0:
    friends[A - 1] = friends[B - 1]
  else:
    friends[A - 1] = A
    friends[B - 1] = A
  #print(friends)


for i in range(N):
  if friends[i] == 0:
    friends[i] = i + 1
    
  #print(friends)
#print(Counter(friends))
print(max(Counter(friends).values()))

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)
for _ in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)

dic=uf.all_group_members()
max_size=0
for ss in dic.values():
  max_size=max(max_size,len(ss))

print(max_size)

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


   
class UnionFind():
    def __init__(self, n):  #初期化　最初はみんなばらばら
        self.n = n
        self.parents = [-1] * n
    def find(self, x):  #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)  #x,yの木の根
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x  #xをでかい木にする

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

    def size(self, x):  #xの含まれる木の要素数を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  #x,yが同じ気に属するか判定
        return self.find(x) == self.find(y)

    def members(self, x):  #xの含まれる木の要素を配列で返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):  #根をすべて返す
        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)
count = [[0]*N 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
    uf.union(a,b)
MAX = 0
for i in range(N):
    a = uf.size(i)
    MAX = max(MAX,a)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys


def _ia(): return map(int, sys.stdin.readline().strip().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 unite(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 main():
    n, m = _ia()
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: x-1, _ia())
        uf.unite(a, b)
    return max(len(uf.members(r)) for r in uf.roots())


if __name__ == "__main__":
    print(main())

Submission status: Time Limit Exceeded

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

for i in range(M):
    a,b=map(int,input().split())
    temp[a-1][b-1]=1
    temp[b-1][a-1]=1
ans=0
for i in range(N):
    ans=max(ans,sum(temp[i]))

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    frd=[[] for i in range(n)]
    #print(frd)
    for i in range(m):
        a,b=INTM()
        for k in range(n):
            if ((a in frd[k])or(b in frd[k])):
                if not(a in frd[k]):
                    frd[k].append(a)
                if not(b in frd[k]):
                    frd[k].append(b)
                break
            elif frd[k]==[]:
                frd[k].append(a)
                frd[k].append(b)
                break
            else:
                pass
                
    #print(frd)
    ans=1
    for i in range(n):
        ans=max(ans,len(frd[i]))
    
    print(ans)

                
if __name__=='__main__':
    do()