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 UnionFindByRank():
    def __init__(self, n):
        self.number = n
        self.parents = list(range(n))
        self.rank = [0] * n

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 全ての要素の親を求める
    def calc_parents(self):
        self.parents = [self.find(i) for i in self.parents]

    # 根を出力する
    def roots(self):
        self.calc_parents()
        return list(set(self.parents))

    # rootを親として持つ
    def groupcounts(self, root):
        return self.parents.count(root)


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

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

groups = uf.roots()
counts = [uf.groupcounts(group) for group in groups]
print(max(counts))

Submission status: Time Limit Exceeded

Solution code:

class UnionFindByRank():
    def __init__(self, n):
        self.number = n
        self.parents = list(range(n))
        self.rank = [0] * n

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 全ての要素の親を求める
    def calc_parents(self):
        self.parents = [self.find(i) for i in self.parents]

    # 根を出力する
    def roots(self):
        self.calc_parents()
        return list(set(self.parents))

    # rootを親として持つ
    def groupcounts(self, root):
        self.calc_parents()
        return self.parents.count(root)


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

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

groups = uf.roots()
counts = [uf.groupcounts(group) for group in groups]
print(max(counts))

Submission status: Time Limit Exceeded

Solution code:
n,m=[int(x) for x in input().split()]
l=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
# print(l)

done=[0]*n


def dfs(j):
  que=[j]
  cnt=1
  done[j]=1
  while(que):
    now=que.pop(0)

    for i in l[now]:
      if done[i]!=1:
        que.append(i)
        done[i]=1
        cnt+=1

  return cnt

ma=0
for j in range(n):
  if done[j]!=1:
    now=dfs(j)
  else:
    now=0
  ma=max(now,ma)
  
print(ma)

Submission status: Time Limit Exceeded

Solution code:
def remove(ref_list, target):
    # リスト内部からtargetを削除する
    ref_list.remove(target)
    return ref_list[0]


    # 友達関係の把握
[N, M] = list(map(int, input().split()))
relations_list = []
for i in range(M):
    relations_list.append(list(map(int, input().split())))
relations_list = list(map(sorted, relations_list))
# グループ分け
remain_list = list(range(1, 1+N))
group_list = []
while remain_list != []:
    # グループ構成員を求める
    group = []
    group.append(remain_list[0])
    search_list = []
    search_list.append(remain_list[0])
    while search_list != []:
        search = search_list.pop(0)
        # searchに関わるrelationの抽出
        candidate_relations = [
            relation for relation in relations_list if search in relation]
        # 今後検索しないため，relations_listからcandidate_relationsを削除
        for candidate_relation in candidate_relations:
            relations_list.remove(candidate_relation)
        candidate_list = [remove(i, search) for i in candidate_relations]
        search_list.extend(candidate_list)
        group.extend(candidate_list)
        # 検索候補とグループ内部の重複をなくす
        search_list = list(set(search_list))
        group = list(set(group))
    for student in group:
        remain_list.remove(student)
    group_list.append(group)

# 最小グループ数の求め
print(max([len(group) for group in group_list]))

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=[int(i) for i in input().split(" ")]
uf = UnionFind(N)
for i in range(M):
    A,B=[int(i) for i in input().split(" ")]
    uf.union(A-1,B-1)

print(max([len(i) for i in uf.all_group_members().values()]))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
grp = []
grpf = set()
if m == 0:
    print(1)
else:
    a, b = map(int, input().split())
    grp.append({a,b})
    for _ in range(m - 1):
        grpf.add(a)
        grpf.add(b)
        a, b = map(int, input().split())
        if a not in grpf and b not in grpf:
            grp.append({a,b})
            continue
        for i in grp:
            if a in i or b in i:
                i.add(a)
                i.add(b)
                break
    ans = 0
    for i in grp:
        ans = max(ans, len(i))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain

n, m = map(int,input().split())
grp = []
if m == 0:
    print(1)
else:
    a, b = map(int, input().split())
    grp.append({a,b})
    for _ in range(m - 1):
        grpf = set(list(chain.from_iterable(grp)))
        a, b = map(int, input().split())
        if a not in grpf and b not in grpf:
            grp.append({a,b})
            continue
        for i in grp:
            if a in i or b in i:
                i.add(a)
                i.add(b)
    ans = 0
    for i in grp:
        ans = max(ans, len(i))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int,input().split())
grp = []
if m == 0:
    print(1)
else:
    a, b = map(int, input().split())
    grp.append({a,b})
    for _ in range(m - 1):
        a, b = map(int, input().split())
        for i in range(len(grp)):
            if a in grp[i]:
                grp[i].add(b)
                break
            elif b in grp[i]:
                grp[i].add(a)
                break
            if i == len(grp) - 1:
                grp.append({a,b})
    ans = 0
    for i in grp:
        ans = max(ans, len(i))
    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)
ans = 0
a = list(uf.all_group_members().values())
for i in range(len(a)):
    ans = max(ans,len(a[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

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

seen = [0] * N
visitm = [True] * M
listm = np.arange(M)
q = deque()
group = []

for i in range(N):
    if seen[i]:
        continue
    q.append(i)
    seen[i] = 1
    k = 1
    while q:
        t = q.popleft()
        for j in listm[visitm]:
            if AB[j][0] == i + 1 and seen[AB[j][1] - 1] != 1:
                q.append(AB[j][1])
                seen[AB[j][1] - 1] = 1
                k += 1
            if AB[j][1] == i + 1 and seen[AB[j][0] - 1] != 1:
                q.append(AB[j][0] - 1)
                seen[AB[j][0] - 1] = 1
                k += 1
            visitm[j] = False
    group.append(k)

print(max(group))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


N, M = map(int,input().split())
mymap = [ [] for n in range(N) ]
for m in range(M):
    a, b = map(int, input().split())
    mymap[a-1].append(b-1)
    mymap[b-1].append(a-1)
#print(mymap)
myans = 0
for n in range(N):
    mylist = mymap[n]
    #print(mylist)
    myd = deque()
    for mm in mylist:
        myd.append(mm)
    #print(myd)
    check_list = [0 for n in range(N)]
    mycnt = 1
    check_list[n] = 1
    while myd:
        tgt = myd.popleft()
        #print(tgt)
        if check_list[tgt] == 0 :
            for e in mymap[tgt]:
                if e > n :
                    myd.append(e)
            mycnt += 1
            check_list[tgt] = 1
    if myans < mycnt:
        myans = mycnt
print(myans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


N, M = map(int,input().split())
mymap = [ [] for n in range(N) ]
for m in range(M):
    a, b = map(int, input().split())
    mymap[a-1].append(b-1)
    mymap[b-1].append(a-1)
#print(mymap)
myans = 0
for n in range(N):
    mylist = mymap[n]
    #print(mylist)
    myd = deque()
    for mm in mylist:
        myd.append(mm)
    #print(myd)
    check_list = [0 for n in range(N)]
    mycnt = 1
    check_list[n] = 1
    while myd:
        tgt = myd.popleft()
        #print(tgt)
        if check_list[tgt] == 0:
            for e in mymap[tgt]:
                myd.append(e)
            mycnt += 1
            check_list[tgt] = 1
    if myans < mycnt:
        myans = mycnt
print(myans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = dict()
ab = list()
if m == 0:
    print(1)
    exit()
for i in range(m):
    a,b = map(int, input().split())
    if b > a:
        b, a = a, b  
    if [a, b] not in ab: 
        ab.append([a,b])
for a, b in ab:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
    if b not in d:
        d[b] = 1
    elif b in d:
        d[b] += 1
print(max(d.values()) + 1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
d = dict()
ab = list()
if m == 0:
    print(1)
    exit()
for i in range(m):
    a,b = map(int, input().split())
    if b > a:
        b, a = a, b  
    if [a, b] not in ab: 
        ab.append([a,b])
        if a not in d:
            d[a] = 1
        else:
            d[a] += 1
        if b not in d:
            d[b] = 1
        elif b in d:
            d[b] += 1
    else:
        continue
print(max(d.values()) + 1)

Submission status: Time Limit Exceeded

Solution code:
class uinon_find():
    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 = uinon_find(n)
for i in range(m):
    a,b = list(map(int,input().split()))
    a-=1
    b-=1
    uf.union(a,b)
#print(uf.all_group_members())
d = uf.all_group_members()
ans=0
for i in d:
    ans = max(len(d[i]),ans)
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())
alist,blist = [],[]
for i in range(m):
    a,b=map(int,input().split())
    alist.append(a)
    blist.append(b)

uf = UnionFind(n)
for i in range(m):
    uf.union(alist[i]-1,blist[i]-1)

aaa = []
aaa = uf.all_group_members()
ans = 0
for i in aaa.values():
    ans = max(len(i),ans)

print(ans)

Submission status: Time Limit Exceeded

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

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

def parent(x):
    if root[x] < 0:
        return x
    return parent(root[x])


def union(x, y):
    x_parent = parent(x)
    y_parent = parent(y)
    if x_parent == y_parent:
        return
    root[x_parent] += root[y_parent]
    root[y_parent] = x


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

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    union(a, b)


max_size = 0
for i in range(N):
    max_size = max(size(i), max_size)

print(max_size)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def main():

    N,M = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(M)]
    '''
    import random
    N = 4 * 10**4 
    M = N - 1
    X = [[random.randint(1,N),random.randint(1,N)] for i in range(M)] 
    '''        
    Y = [-1 for _ in range(N+1)]
    Z = [[] for _ in range(N+1)]
    '''
    # 前処理　大小関係の整理と重複の削除
    for x in X:
        a = x[0]
        b = x[1]
        if a == b:
            X.remove(x)
        elif a > b:
            x[0],x[1] = b,a
            
    X.sort()
    for i in reversed(range(len(X)-1)):
        if X[i+1]==X[i]:
            X.pop(i+1)
    '''
    if M==0:
        print(1)
    else:
        for x in X:
            a = x[0]
            b = x[1]
            if Y[a] == -1:
                if Y[b] == -1:
                    Y[a] = Y[b] = a
                    Z[a] = [a,b]
                else:
                    Y[a] = Y[b]
                    Z[Y[b]] += [a]
            else:
                if Y[b] == -1:
                    Y[b] = Y[a]
                    Z[Y[a]] += [b]
                else:
                    ya = Y[a]
                    yb = Y[b]
                    if ya != yb:
                        for y in Z[Y[b]]:
                            Y[y] = ya
                        Z[ya] += Z[yb]
                        Z[yb].clear()
            #print(x,Y,Z)
        
        Yf = set(Y)
        Yf.remove(-1)
        maxc = 0
        for i in Yf:
            maxc = max(maxc,len(Z[i]))
        print(maxc)
    
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def resolve():
    N, M = map(int, input().split())
    Friend = [[False]*(N+1) for _ in range(N+1)]
    for i in range(M):
        A, B = map(int, input().split())
        Friend[A][B] = True
        Friend[B][A] = True
    seen = [False]*(N+1)
    Max = 0
    for i in range(N+1):
        if seen[i]:
            continue
        stack = deque()
        stack.append(i)
        Max = max(DFS(stack, seen, N, Friend), Max)
    print(Max)

def DFS(stack, seen, N, Friend):
    c = 0
    while stack:
        i = stack.pop()
        if seen[i]:
            continue
        c += 1
        seen[i] = True
        for j in range(N+1):
            if seen[j]:
                continue
            if Friend[i][j]:
                stack.append(j)
    return c
  
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def resolve():
    N, M = map(int, input().split())
    Friend = [[False]*(N+1) for _ in range(N+1)]
    for i in range(M):
        A, B = map(int, input().split())
        Friend[A][B] = True
        Friend[B][A] = True
    seen = [False]*(N+1)
    Max = 0
    for i in range(N+1):
        if not seen[i]:
            stack = deque()
            stack.append(i)
            Max = max(DFS(stack, seen, N, Friend), Max)
    print(Max)

def DFS(stack, seen, N, Friend):
    c = 0
    while stack:
        i = stack.pop()
        if seen[i]:
            continue
        c += 1
        seen[i] = True
        for j in range(N+1):
            if Friend[i][j]:
                stack.append(j)
    return c
  
resolve()

Submission status: Time Limit Exceeded

Solution code:
def DFS(i):
    Checked[i] = True
    C = 1
    for j in range(N+1):
        if Friend[i][j] and not Checked[j]:
            C += DFS(j)
    return C
  
N, M = map(int, input().split())
Friend = [[False]*(N+1) for _ in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    Friend[A][B] = True
    Friend[B][A] = True
Checked = [False]*(N+1)
Max = 0
for i in range(N+1):
    if not Checked[i]:
        Max = max(DFS(i), Max)
print(Max)

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())
    a -= 1
    b -= 1
    uf.union(a, b)

ans = 0

for group in uf.roots():
    ans = max(ans, len(uf.members(group)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

seen = [0] * N
q = deque()
group = []

for i in range(N):
    if seen[i]:
        continue
    q.append(i)
    seen[i] = 1
    k = 1
    while q:
        t = q.popleft()
        for j in range(M):
            if AB[j][0] == i + 1 and seen[AB[j][1] - 1] != 1:
                q.append(AB[j][1])
                seen[AB[j][1] - 1] = 1
                k += 1
            if AB[j][1] == i + 1 and seen[AB[j][0] - 1] != 1:
                q.append(AB[j][0] - 1)
                seen[AB[j][0] - 1] = 1
                k += 1
    group.append(k)

print(max(group))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

seen = [0] * N
q = deque()
group = []

for i in range(N):
    if seen[i]:
        continue
    q.append(i)
    seen[i] = 1
    k = 1
    while q:
        t = q.pop()
        for j in range(M):
            if AB[j][0] == i + 1 and seen[AB[j][1] - 1] != 1:
                q.append(AB[j][1])
                seen[AB[j][1] - 1] = 1
                k += 1
            if AB[j][1] == i + 1 and seen[AB[j][0] - 1] != 1:
                q.append(AB[j][0] - 1)
                seen[AB[j][0] - 1] = 1
                k += 1
    group.append(k)

print(max(group))

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])



#UnionFind
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 = inpm()
AB = inplt(m)

uf = UnionFind(n)
for a,b in AB:
    uf.union(a-1,b-1)

ans = 0
for x in uf.all_group_members().values():
    ans = max(ans,len(x))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])



#UnionFind
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 = inpm()
AB = inplt(m)

uf = UnionFind(n)
for a,b in AB:
    uf.union(a-1,b-1)

ans = 0
for x in uf.all_group_members().values():
    ans = max(ans,len(x))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

for i in range(m):
    a,b = map(int,input().split())
    g[a].add(b)
    g[b].add(a)
    
seen = {i:0 for i in range(n+1)}
seen[0]=1
seen[1]=1
q = deque()
q.append(1)
grpsize=1

while 0 in seen.values():
    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.values()))

Submission status: Time Limit Exceeded

Solution code:
# Python program to print connected 
# components in an undirected graph 
class Graph: 
	
	# init function to declare class variables 
	def __init__(self,V): 
		self.V = V 
		self.adj = [[] for i in range(V)] 

	def DFSUtil(self, temp, v, visited): 

		# Mark the current vertex as visited 
		visited[v] = True

		# Store the vertex to list 
		temp.append(v) 

		# Repeat for all vertices adjacent 
		# to this vertex v 
		for i in self.adj[v]: 
			if visited[i] == False: 
				
				# Update the list 
				temp = self.DFSUtil(temp, i, visited) 
		return temp 

	# method to add an undirected edge 
	def addEdge(self, v, w): 
		self.adj[v].append(w) 
		self.adj[w].append(v) 

	# Method to retrieve connected components 
	# in an undirected graph 
	def connectedComponents(self): 
		visited = [] 
		cc = [] 
		for i in range(self.V): 
			visited.append(False) 
		for v in range(self.V): 
			if visited[v] == False: 
				temp = [] 
				cc.append(self.DFSUtil(temp, v, visited)) 
		return cc 

n,m = map(int,input().split())
g = Graph(n);
cc = [[n]]
for i in range(m):
    a,b = map(int,input().split())
    g.addEdge(a-1,b-1) 
    cc = g.connectedComponents()
ans = 1
for i in cc:
    ans = max(ans,len(i))
print(ans)
# This code is contributed by Abhishek Valsan

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 = {i:0 for i in range(n+1)}
seen[0]=1
seen[1]=1
q = deque()
q.append(1)
grpsize=1

while 0 in seen.values():
    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.values()))