Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

You are given M facts that "Person A_i and Person B_i are friends." The same fact may be given multiple times.

If X and Y are friends, and Y and Z are friends, then X and Z are also friends. There is no friendship that cannot be derived from the M given facts.

Takahashi the evil wants to divide the N persons into some number of groups so that every person has no friend in his/her group.

At least how many groups does he need to make?

Constraints

2 \leq N \leq 2\times 10^5

0 \leq M \leq 2\times 10^5

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

Dividing them into three groups such as \{1,3\}, \{2,4\}, and \{5\} achieves the goal.

Sample Input 2

4 10
1 2
2 1
1 2
2 1
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
D = defaultdict(set)
N, M = map(int,input().split())

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

Q = []
ans = 0
S = set()
for i in range(N):
  if i in S:continue
  vstd = set()
  Q.append(i)
  while Q:
    a = Q.pop()
    S.add(a)
    vstd.add(a)
    for j in D[a]:
      if not j in vstd:
        Q.append(j)
  ans = max(ans,len(vstd))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
D = defaultdict(set)
N, M = map(int,input().split())

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

Q = []
ans = 0
for i in range(N):
  vstd = set()
  Q.append(i)
  while Q:
    a = Q.pop()
    vstd.add(a)
    for j in D[a]:
      if not j in vstd:
        Q.append(j)
  ans = max(ans,len(vstd))
print (ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())

l = list(range(1,N+1))
q = set()

for _ in range(M):
  a,b = map(int,input().split())
  src = max(l[a-1],l[b-1])
  dst = min(l[a-1],l[b-1])
  for i in range(N):
    if l[i] == src:
      l[i] = dst
      
print(max([len([i for i in l if i == j]) for j in set(l)]))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())

l = list(range(1,N+1))

for _ in range(M):
  a,b = map(int,input().split())
  src = l[max(a,b)-1]
  dst = l[min(a,b)-1]
  for i in range(N):
    if l[i] == src:
      l[i] = dst
    
print(max([len([i for i in l if i == j]) for j in set(l)]))

Submission status: Time Limit Exceeded

Solution code:

#スタック、キューを使う
from collections import deque

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

G = [ set() for row in range(N)]

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

for i in range(N):
    G[i] = list(G[i])

#1グループに所属する最大数
ans = 0

#友達グループの数
count = 0

#各頂点の状態を色で表す WHITE:未訪問 GRAY:訪問中 BLACK:訪問完了
color = ['WHITE' for i in range(N)]

#訪問途中の頂点を退避しておくスタック
S = deque()

#次の要素を取り出す
def next(u):    
    #G[u]に格納されているまだ未訪問のノードを返す
    for i in range(len(G[u])):
        if color[G[u][i]] == 'WHITE':
            return G[u][i]
    return -1

def dfs(u):
    #始点uをスタックに追加
    S.append(u)
    color[u] = 'GRAY'
    global count
    count += 1
    #dequeは空のとき偽を返す
    while S:
        u = S[-1]    #スタックの頂点をuに格納
        v = next(u)
        #uに未訪問の隣接ノードがある
        if v != -1:
            color[v] = 'GRAY'
            count += 1
            S.append(v)
        else:
            S.pop()
            color[u]='BLACK'

#未訪問のuを始点として深さ優先探索
for i in range(N):
    count = 0
    if color[i] == 'WHITE':
        dfs(i)
        if count >= ans:
            ans = count

print(ans)

Submission status: Time Limit Exceeded

Solution code:

#スタック、キューを使う
from collections import deque

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

G = [ [] for row in range(N)]

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

#1グループに所属する最大数
ans = 0

#友達グループの数
count = 0

#各頂点の状態を色で表す WHITE:未訪問 GRAY:訪問中 BLACK:訪問完了
color = ['WHITE' for i in range(N)]

#訪問途中の頂点を退避しておくスタック
S = deque()

#次の要素を取り出す
def next(u):    
    #G[u]に格納されているまだ未訪問のノードを返す
    for i in range(len(G[u])):
        if color[G[u][i]] == 'WHITE':
            return G[u][i]
    return -1

def dfs(u):
    #始点uをスタックに追加
    S.append(u)
    color[u] = 'GRAY'
    global count
    count += 1
    #dequeは空のとき偽を返す
    while S:
        u = S[-1]    #スタックの頂点をuに格納
        v = next(u)
        #uに未訪問の隣接ノードがある
        if v != -1:
            color[v] = 'GRAY'
            count += 1
            S.append(v)
        else:
            S.pop()
            color[u]='BLACK'

#未訪問のuを始点として深さ優先探索
for i in range(N):
    count = 0
    if color[i] == 'WHITE':
        dfs(i)
        if count >= ans:
            ans = count

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=list(map(int,input().split()))
n=N[0]
m=N[1]
A = []
for i in range(m):
  array = list(map(int,input().split()))
  array.sort()
  A.append(array)
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

X=get_unique_list(A)
#print(X)
R=[]

for j in range(1,n+1):
  c=1
  for h in range(len(X)):
    if j in X[h]:
      c+=1
  R.append(c)
    
  
print(max(R))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数



    # 入力を整数に変換して受け取る
    def input_int():
        return int(input())

    def map_int_input():
        return map(int, input())

    MII = map_int_input

    def MII_split():
        return map(int, input().split())

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

    def LII_split():
        return list(map(int, input().split()))

    # 2次元リスト化
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    class UnionFind:
        def __init__(self, n):
            """
            :param n: 人数
            :type n: int
            """
            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 = MII_split()


    # groups = []
    uf = UnionFind(N)

    for _ in range(M):
        A, B = MII_split()
        uf.union(A-1, B-1)  # unionfindを使い、結合の計算量を減らす
        # is_in_groups = False
        # for group in groups:
        #     if A in group and B not in group:
        #         group.append(B)
        #         break
        #     elif B in group and A not in group:
        #         group.append(A)
        #         break
        #     elif A in group and B in group:
        #         is_in_groups = True
        #         break
        # if not is_in_groups:
        #     groups.append([A, B])

    print(max(map(lambda x: len(x), uf.all_group_members().values())))
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

class UnionFind(object):
    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 = MI()
    uf = UnionFind(N)

    for i in range(M):
        a, b = MI()
        uf.union(a-1, b-1)

    ret = [len(i) for i in uf.all_group_members().values()]

    print(max(ret))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

friend_list = []
for i in range(M):
  pair = list(map(int, input().split()))
  friend_list.append(set(pair))

group_num_people = []
for i, group in enumerate(friend_list):
  group_list = [group]
  for j, target in enumerate(friend_list):
    if i == j:
      continue
    else:
      if len(group.intersection(target)) >= 1:
        group_list.append(target)
  group_num_people.append(len(set().union(*group_list)))


if M == 0:
  print(1)
else:
  print(max(group_num_people))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

friend_list = []
for i in range(M):
  pair = list(map(int, input().split()))
  friend_list.append(set(pair))

group_num_people = []
for i, group in enumerate(friend_list):
  for j in range(M):
    if i == j:
      continue
    else:
      target = friend_list[j]
      if len(group.intersection(target)) >= 1:
        group = group.union(target)
  group_num_people.append(len(group))


if M == 0:
  print(1)
else:
  print(max(group_num_people))

Submission status: Time Limit Exceeded

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

def dfs(node, edge, vis):
    if vis[node]:
        return 0
    vis[node] = True
    count = 1
    vq = []
    vq.append(node)
    while vq:
        fnode = vq[0]
        del vq[0]
        for b in edge[fnode]:
            if not vis[b]:
                count += 1
                vq.append(b)
                vis[b] = True
    return count

n, m = [int(i) for i in input().split(' ')]

edge = [[] for i in range(n)]

for _ in range(m):
    a, b = [int(i) for i in input().split(' ')]
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

vis = [False]*n

count = 0

for i in range(n):
    if not vis[i]:
        count = max(count, dfs(i, edge, vis))

print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [1]*(n+1)
b = [0]*(n+1)
for i in range(m):
  x,y = map(int,input().split())
  u = x
  while a[u]==0:
    u = b[u]
  v = y
  while a[v]==0:
    v = b[v]
  if u!=v:
    b[v] = u
    a[u] += a[v]
    a[v] = 0
print(max(a))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
S = []
for i in range(M):
    A_i, B_i = map(int, input().split())
    A_i, B_i = min(A_i, B_i), max(A_i, B_i)
    S.append([A_i, B_i])
S.sort(key=lambda x: x[0])
T = [set()]
m_len = 1
for s in S:
    for t in T:
        if s[0] in t or s[1] in t:
            t.add(s[0])
            t.add(s[1])
            m_len = max(m_len, len(t))
            break
        if t == T[-1]:
            T.append({s[0], s[1]})
            m_len = max(m_len, len({s[0], s[1]}))
print(m_len)

Submission status: Time Limit Exceeded

Solution code:
# Union Find
class UnionFind():
    # parents:親要素の番号，要素が根なら-グループの要素数
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    # xとyのグループを併合
    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 max_size_group(self):
        ret = 0
        for mem in self.all_group_members():
            ret = max(ret, len(self.members(mem)))
            # print(self.members(mem))
        return ret


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)
print(uf.max_size_group())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


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

ans_list = []
for i in range(M):
    X, Y = map(int, input().split())
    X_bin = bin(1 << (X - 1))
    Y_bin = bin(1 << (Y - 1))
    com_bin = bin(int(X_bin, 2) | int(Y_bin, 2))

    flag = False
    for j in range(len(ans_list)):
        if ans_list[j] == com_bin:
            break

        ans_int = int(ans_list[j], 2)
        if bin((X & ans_int)) == X_bin or bin((Y & ans_int)) == Y_bin:
            ans_list[j] = bin(ans_int | int(com_bin, 2))
            flag = True

    if not flag:
        ans_list.append(com_bin)


max_count = 1
for j in range(len(ans_list)):
    count = popcount(int(ans_list[j], 2))
    if max_count < count:
        max_count = count

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


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

ans_list = []
for i in range(M):
    X, Y = map(int, input().split())
    X_bin = bin(1 << (X - 1))
    Y_bin = bin(1 << (Y - 1))
    com_bin = bin(int(X_bin, 2) | int(Y_bin, 2))

    flag = False
    for j in range(len(ans_list)):
        if ans_list[j] == com_bin:
            break

        if bin((int(X_bin, 2) & int(ans_list[j], 2))) == X_bin or bin((int(Y_bin, 2) & int(ans_list[j], 2))) == Y_bin:
            ans_list[j] = bin(int(ans_list[j], 2) | int(com_bin, 2))
            flag = True

    if not flag:
        ans_list.append(com_bin)


max_count = 1
for j in range(len(ans_list)):
    count = popcount(int(ans_list[j], 2))
    if max_count < count:
        max_count = count

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


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

ans_list = []
for i in range(M):
    X, Y = map(int, input().split())
    X_bin = bin(1 << (X - 1))
    Y_bin = bin(1 << (Y - 1))
    com_bin = bin(int(X_bin, 2) | int(Y_bin, 2))

    flag = False
    for j in range(len(ans_list)):
        if bin((int(X_bin, 2) & int(ans_list[j], 2))) == X_bin or bin((int(Y_bin, 2) & int(ans_list[j], 2))) == Y_bin:
            ans_list[j] = bin(int(ans_list[j], 2) | int(com_bin, 2))
            flag = True

    if not flag:
        ans_list.append(com_bin)


max_count = 1
for j in range(len(ans_list)):
    count = popcount(int(ans_list[j], 2))
    if max_count < count:
        max_count = count

print(max_count)

Submission status: Time Limit Exceeded

Solution code:
def solve(N, M, fridens):
    groups = {}
    for x in range(N):
        groups[x] = [x]

    for A, B in friends:
        if B in groups:
            groups[A].append(B)
            del groups[B]

    ans = len(max(groups.values(), key=len))
    print(ans)


if __name__ == "__main__":
    N, M = map(int, input().split())
    friends = []
    for _ in range(M):
        AB = sorted([x - 1 for x in map(int, input().split())])
        if AB not in friends:
            friends.append(AB)
    solve(N, M, friends)

Submission status: Time Limit Exceeded

Solution code:
def solve(N, M, fridens):
    parents = [-1 for _ in range(N)]
    groups = {}
    for x in range(N):
        groups[x] = [x]

    for A, B in friends:
        if B in groups:
            parents[B] = A
            groups[A].append(B)
            del groups[B]

    ans = len(max(groups.values(), key=len))
    print(ans)


if __name__ == "__main__":
    N, M = map(int, input().split())
    friends = []
    seen = []
    for _ in range(M):
        AB = sorted([x - 1 for x in map(int, input().split())])
        if AB not in seen:
            friends.append(AB)
            seen.append(AB)
    solve(N, M, friends)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

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

adj_mat = [[False] * N for i in range(N)]
friends_list = [1] * N 

for i in range(M):
    a, b = AB[i][0], AB[i][1]
    a -= 1;
    b -= 1;

    if (not adj_mat[a][b]):
        friends_list[a] += 1
    if (not adj_mat[b][a]):
        friends_list[b] += 1

    adj_mat[a][b] = True
    adj_mat[b][a] = True

max_friends = 0
for f_num in friends_list:
    max_friends = max(f_num, max_friends)

print(max_friends)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

adj_mat = [[False] * N for i in range(N)]
friends_list = [1] * N 

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

    if (not adj_mat[a][b]):
        friends_list[a] += 1
    if (not adj_mat[b][a]):
        friends_list[b] += 1

    adj_mat[a][b] = True
    adj_mat[b][a] = True

max_friends = 0
for f_num in friends_list:
    max_friends = max(f_num, max_friends)

print(max_friends)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
d = {}
for _ in range(m):
    a,b = map(int,input().split())
    d[a] = d.get(a,[]) + [b]
    d[b] = d.get(b,[]) + [a]
ans = 1
visited = set()
for i in range(1,n+1):
    if i in visited: continue
    stack = [i]
    visited.add(i)
    cur = 1
    while stack:
        node = stack.pop()
        for nei in d.get(node,[]):
            if nei not in visited:
                stack.append(nei)
                visited.add(nei)
                cur += 1
    ans = max(ans,cur)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())

f = [{} for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    f[a][b] = True
    f[b][a] = True

for i in range(N):
    koho = set()
    for k in f[i].keys():
        for ff in f[k].keys():
            if not(ff in f[i]):
                koho.add(ff)
    for k in koho:
        f[i][k] = True

ans = 0
zumi = set()
for i in range(N):
    if i in zumi:
        continue

    koho = set()
    ans += 1
    for j in range(N):
        if j in koho or j in zumi:
            continue
        for k in koho:
            if j in f[k]:
                break
        else:
            koho.add(j)
            zumi.add(j)
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 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 group_members(self):
        return [self.members(r) for r in self.roots()]

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


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

uf = UnionFind(n+1)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x, y)

print(max([len(g) for g in uf.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 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 group_members(self):
        return [self.members(r) for r in self.roots()]

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


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

uf = UnionFind(n+1)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x, y)

print(max([len(g) for g in uf.group_members()]))

Submission status: Time Limit Exceeded

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

if m==0:
    print(1)
    exit()
else:
    ab = [map(int, input().split()) for _ in range(m)]
    a,b = [list(i) for i in zip(*ab)]

indexlist=[-1]*n

def findroot(x):
    while 1:
        if indexlist[x-1] < 0:
            return x
        else:
            x=indexlist[x-1]
            


def merge(a,b):
    art=findroot(a)
    brt=findroot(b)
    if not art == brt:
        indexlist[art-1]+=indexlist[brt-1]
        indexlist[brt-1]=a
        return
    else:
        return
        

for j in range(m):
    a1=a[j]
    b1=b[j]
    merge(a1,b1)

ans=min(indexlist)*(-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())

class Union_Find():

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

    #xの木の根を返す関数
    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]

    #xの木とyの木を統合する関数
    def unite(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)

        if x==y:
            return
        else:
            if self.root[x]<self.root[y]:
                x,y=y,x
            self.root[x]+=self.root[y]
            self.root[y]=x 
        """
        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
        """



    #xとyの木の根が同じならTrueを返す関数
    def same(self,x,y):
        return self.find_root(x)==self.find_root(y)

    #xの木の要素数を返す関数
    def cnt(self,x):
        return -self.root[self.find_root(x)]

G=Union_Find(N)
ans=0
for i in range(M):
    a,b=map(int,input().split())
    G.unite(a,b)

for i in range(1,N+1):
    ans = max(ans,G.cnt(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,M = map(int,input().split())

class Union_Find():

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

    #xの木の根を返す関数
    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]

    #xの木とyの木を統合する関数
    def unite(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)

        if x==y:
            return
        else:
            self.root[x]+=self.root[y]
            self.root[y]=x 
        """
        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
        """


    #xとyの木の根が同じならTrueを返す関数
    def same(self,x,y):
        return self.find_root(x)==self.find_root(y)

    #xの木の要素数を返す関数
    def cnt(self,x):
        return -self.root[self.find_root(x)]

G=Union_Find(N)
ans=0
for i in range(M):
    a,b=map(int,input().split())
    G.unite(a,b)

for i in range(1,N+1):
    ans = max(ans,G.cnt(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n, m = map(int, input().split())
par = list(range(2 * n))

# print(par)


# union find(parには0も入れているので、par[1]=1になる)
def find(x):
    while par[x] != x:
        x = par[x]
    return x


def union(x, y):
    x1 = find(x)
    y1 = find(y)
    par[x1] = y1


# 各要素をunionする
for j in range(m):
    a, b = map(int, input().split())
    union(a - 1, b - 1)

s = [0 for i in range(n + 5)]

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(n):
    s[find(k)] += 1

print(max(s))

Submission status: Time Limit Exceeded

Solution code:
N,M=[int(a) for a in input().split()]
AB=list()
for i in range(M):
    AB.append([int(a) for a in input().split()])
#print(N,M,AB)

flists=list()
for pair in AB:
    list0=-1
    list1=-1
    for j,flist in enumerate(flists):
        if pair[0] in flist:
            list0=j
        if pair[1] in flist:
            list1=j
    if list0==-1 and list1==-1:
        flists.append(set([pair[0],pair[1]]))
    elif list0!=-1 and list1!=-1 and list0!=list1:
        flists[list0]=flists[list0]|flists[list1]
        flists.pop(list1)
    elif list0==-1 and list1!=-1:
        flists[list1].add(pair[0])
    elif list0!=-1 and list1==-1:
        flists[list0].add(pair[1])
#print(flists)

ans=1        
for flist in flists:
    l=len(flist)
    if l>ans:
        ans=l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
path = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    path[a-1] += [b-1]
    path[b-1] += [a-1]
visited = [1] + [0] * (N-1)

u = 0
ans = 1
curr = 1
next_u = [u]
while True:
    if len(next_u) == 0:
        ans = max(ans, curr)
        curr = 1
        for i in range(N):
            if visited[i] == 0 and len(path[i])!= 0:
                visited[i] = 1
                next_u = path[i]
                break
        else:
            break
    u = next_u.pop()
    for v in path[u]:
        if visited[v] == 1:
            continue 
        visited[v] = 1
        next_u += [v]
        curr += 1

print(ans)