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

    g = uf.all_group_members().values()
    maxv = max([len(gi) for gi in g])
    print(maxv)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/08/29

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,M=map(int,pin().split())
  cnt=[0]*N 
  dp=[[0]*N for _ in range(N)]
  for i in range(M):
    A,B=map(int,pin().split())
    t=max(A,B)
    s=min(A,B)
    if dp[s-1][t-1]==0:
      cnt[s-1]+=1
      cnt[t-1]+=1
      dp[s-1][t-1]=1
  print(max(cnt)+1)
  return 
main()

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())
      
    def main(self):
      return max([len(self.members(r)) for r in self.roots()])
uf = UnionFind(N)

for _ in range(M):
  A, B  = map(int, input().split())
  uf.union(A-1,B-1)
  
#L = list(uf.all_group_members().values())

#ans = max( [ len(l) for l in L ] )
#print(ans)
print(uf.main())

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
fr = {i:[] for i in range(N)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    if b-1 not in fr[a-1]:
        fr[a-1].append(b-1)
    if a-1 not in fr[b-1]:
        fr[b-1].append(a-1)

remain = [i for i in range(N)]
groups = []
while remain!=[]:
    g = []
    o = remain.pop(0)
    g.append(o)
    cands = fr[o]
    while cands!=[]:
        n = cands.pop(0)
        g.append(n)
        remain.remove(n)
        cands.extend([num for num in fr[n] if num not in g and num not in cands])
    groups.append(g)

ans = 0
for one in groups:
    if len(one)>ans:
        ans = len(one)
print(ans)

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

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

    def union(i, j):
        uf[root(i)] = root(j)

    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:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def solve():
    N, M = MI()

    uf = UnionFind(N)
    for i in range(M):
        a, b = MI1()
        uf.union(a, b)
    
    tmp = []
    # print(uf.all_group_members())
    for gp in uf.all_group_members().values():
        l = len(gp)
        tmp.append(l)
    s = sorted(tmp, reverse=True)
    # print(s)
    if len(s) == 1:
        print(s[0])
    else:
        print(s[1] + s[0] - s[1])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000+10)

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

#xの木の根を求める
def root(x,li): 
    if li[x] == x:
        return x
    else:
        li[x] = root(li[x],li)
        return li[x]

#xとyが同じ集合に属するかの判定
def find(x,y,li):
    return root(x,li) == root(y,li)

#xとｙを併合
def union(x,y,li):
    x = root(x,li)
    y = root(y,li)
    if x==y:
        return
    else:
        li[x] = y

li = [i for i in range(N+20)]

for i in range(len(AB)):
    AB[i][0] -= 1
    AB[i][1] -= 1
    union(AB[i][0], AB[i][1], li)

for i in range(N):
    root(i, li)

cnt = [0 for i in range(N+20)]
for i in range(N):
    cnt[li[i]] += 1
print(max(cnt))

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):
        '''
        要素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が属するグループと要素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):
        '''
        要素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())


G = UnionFind(N)

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

ans = 0
for g, mem in G.all_group_members().items():
    l = len(mem)
    if ans < l:
        ans = l
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())
  a -= 1
  b -= 1
  uf.union(a,b)
  
ans = 0
for v in uf.all_group_members().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 same(self, x, y):
        return self.find(x) == self.find(y)

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

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

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

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

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

    def max_group_members(self):
        ret = 1
        for r in self.roots():
            ret = max(len(self.members(r)), ret)
        return ret

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


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

print(Groups.max_group_members())

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)
    
dic=uf.all_group_members()

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

input = sys.stdin.readline

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

uf = UnionFind(N)
for a, b in relations:
    uf.union(a, b)

max_n = 0
for i in range(uf.group_count()):
    max_n = max(max_n, len(uf.members(i)))

print(max_n)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind: 
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
        self.sizes = [1] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        sx, sy = self.sizes[x], self.sizes[y]
        if x == y: return (0, 0)
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
            self.sizes[y] += sx
        else:
            self.pars[y] = x
            self.sizes[x] += sy
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
        return (sx, sy)
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)
    def getSize(self, x):
        return self.sizes[self.getRoot(x)]


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

uf = UnionFind(n)
e = [[] for i in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    if not b in e[a]:
        uf.merge(a,b)
        e[a].append(b)
        e[b].append(a)

print(max(uf.sizes))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(20000)


def _ia(): return map(int, sys.stdin.readline().strip().split())


class UnionFind:
    def __init__(self, n: int) -> None:
        self._par = [i for i in range(n)]
        self._rank = [0] * n

    def root(self, n: int) -> int:
        p = self._par[n]
        if p == n:
            return p
        else:
            # compress
            self._par[n] = self.root(p)
            return self._par[n]

    def same(self, n: int, m: int) -> bool:
        return self.root(n) == self.root(m)

    def unite(self, n: int, m: int) -> None:
        pn = self.root(n)
        pm = self.root(m)
        if pn == pm:
            return
        self._par[pm] = pn


def main():
    n, m = _ia()
    uf = UnionFind(n)
    for _ in range(m):
        a, b = map(lambda x: x-1, _ia())
        uf.unite(a, b)
    c = Counter([uf.root(i) for i in range(n)])
    return max(c.values())


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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
#for _ in range(n):
#  x, y, z = map(int, stdin.readline().split())

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

uf=[i for i in range(n+1)]

def uff(x):
    while x!=uf[x]:
        x=uf[x]
    return x

for i in range(m):
    a,b= map(int, stdin.readline().split())
    ua=uff(a)
    ub=uff(b)
    if ua<ub:
        uf[ub]=ua
    else:
        uf[ua]=ub

cnt=[0 for i in range(n+1)]
for i in range(1,n+1):
    cnt[uff(i)]+=1
print(max(cnt))

Submission status: Time Limit Exceeded

Solution code:
# https://note.nkmk.me/python-union-find/
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
for i in uf.all_group_members().values():
    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)  # この変数xに格納されているものは必ず根のノード
        y = self.find(y)  # この変数yに格納されているものは必ず根のノード
        if x == y:
            return  # もし同じ親ならば何も起こらない

        if self.parents[x] > self.parents[y]:  # それぞれ、要素の個数が負で格納されている
            # yのグループの方が要素が多いの場合（yの方が値が小さいということは、負の世界では値が大きいため）
            x, y = y, x  # 必ずxの方が要素が多い状態にする

        self.parents[x] += self.parents[y]  # 負の値だが、これでいい
        self.parents[y] = x  # yは親ではなくなったため、新しい親であるxの値を正でもつ

    def size(self, x):
        return -self.parents[self.find(x)]  # 親まで辿ればグループの大きさが負で格納されているため、それにマイナスをつけてreturnする

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 親が同じならTrueが返却される

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

ans = 0
for k, v in uf.all_group_members().items():
    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())

uf = UnionFind(N)

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

all_group_members = uf.all_group_members()
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


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)

hoge = list(uf.all_group_members().values())
Max = 0
for i in range(len(hoge)):
    Max = max(Max,len(hoge[i]))

print(Max)

Submission status: Time Limit Exceeded

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

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

l = [[0 for _ in range(N)] for _ in range(N)]

for i in range(M):
    l[ab[i][0]-1][ab[i][1]-1] = 1
    l[ab[i][1]-1][ab[i][0]-1] = 1

a = np.array(l)
n, labels = connected_components(a)

print(collections.Counter(labels).most_common()[0][1])

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)

root = uf.roots()
print( max(len(uf.members(r)) for r in root) )

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

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)
x = list(uf.all_group_members().values())
#print(x)
ans = 0
for i in range(len(x)):
    ans = max(ans,len(x[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

l = []
for _ in range(n):
  l.append([False] * n)

for x in range(n):
  l[x][x] = True

for a, b in ab:
  a -= 1
  b -= 1
  l[a][b] = True
  l[b][a] = True

c = [None] * n

for i in range(n):
  if c[i] is None:
    c[i] = i
  for j in range(n):
    if l[i][j]:
      if c[j] is None:
        c[j] = i

vs = []
for k, v in collections.Counter(c).items():
  vs.append(v)

print(max(vs))