Problem:


Score : 400 points

Problem Statement

There are N persons called Person 1 through Person N.

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

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

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

At least how many groups does he need to make?

Constraints

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

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

1\leq A_i,B_i\leq N

A_i \neq B_i

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

5 3
1 2
3 4
5 1

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 4
3 1
4 1
5 9
2 6

Sample Output 3

3



Sample input:
5 3
1 2
3 4
5 1


Sample output:
3

Submission status: Time Limit Exceeded

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

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

from collections import deque

over=[] #探索ずみ
before=[] #探索前
for i in range(N):
    before.append(i)

dist=[float('inf')]*N
cnt=0
cup=[]
while before:
    v=before.pop(0)
    que=deque([v])
    dist[v]=0
    cuppy=[]
    cuppy.append(v)
    while que:
        u=que.popleft()
        
        for e in G[u]:
            if dist[e] == float('inf'):
                
                que.append(e)
                before.remove(e)
                cuppy.append(e)
                dist[e]=dist[u] + 1
    
    cup.append(cuppy)
    cnt += 1


ans=0
for i in range(len(cup)):
    ans = max(ans,len(cup[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def main():
  N, M = map(int, input().split())
  lst = [list(map(int, stdin.readline().split())) for _ in range(M)]
  
  f_lst = [[0 for i in range(N)] for j in range(N)]
  count = [0] * N
  
  for A, B in lst:
    if f_lst[A-1][B-1] != 1:
      f_lst[A-1][B-1] = 1
      f_lst[B-1][A-1] = 1
      count[A-1] += 1
      count[B-1] += 1
  print(max(count)+1)

main()

Submission status: Time Limit Exceeded

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

if M == 0:
    print(1)
    exit()

group_list = []
group_index = [0] * N

for _ in range(M):
    a, b = map(int, input().split())
    if group_index[a-1] == 0 and group_index[b-1] == 0:
        group_index[a-1] = len(group_list) + 1
        group_index[b-1] = len(group_list) + 1
        group_list.append(set([a, b]))

    elif group_index[a-1] == 0:
        group_index[a-1] = group_index[b-1]
        group_list[group_index[b-1] - 1].add(a)

    elif group_index[b-1] == 0:
        group_index[b-1] = group_index[a-1]
        group_list[group_index[a-1] - 1].add(b)

    elif group_index[a-1] != group_index[b-1]:
        group_id_b = group_index[b-1] - 1
        for p in group_list[group_id_b]:
            group_index[p-1] = group_index[a-1]
            group_list[group_index[a-1] - 1].add(p)
        group_list[group_id_b] = set()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    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,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            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 all_group_members(self):
        #各ルート要素のグループに含まれる要素のリストの辞書
        return {r: self.members(r) for r in self.roots()}
    def all_group_members_list(self):
        #各ルート要素のグループに含まれる要素のリストのリスト
        #[[0, 2], [1, 3, 4, 5]]
        return list(self.all_group_members().values())
def main():
    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.unite(a, b)
    uf_lis = uf.all_group_members_list()
    ans = 0
    for l in uf_lis:
        ans = max(ans, len(l))
    print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

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

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

_INPUT = """\
5 3
1 2
3 4
5 1
"""

def main(*, input=input):
    sr = lambda: input()
    ir = lambda: int(sr())
    lr = lambda: list(map(int, sr().split()))

    n,m = lr()
    uf = UnionFind(n)
    for i in range(m):
        a,b = lr()
        a-=1
        b-=1
        uf.union(a,b)
    ans = 0
    for _,v in uf.all_group_members().items():
        ans = max(ans,len(v))
    print(ans)

if __name__ == "__main__":
    import io, sys

    # sys.stdin = io.StringIO(_INPUT)

    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[i+1 for i in range(n)] #[1,2,3,4,5]
    def find(self,x):
        if self.parents[x-1]==x: #list内のx-1番目がx
            return x
        else:
            self.parents[x-1]=self.find(self.parents[x-1]) 
            return self.parents[x-1]
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if x>y:
            self.parents[x-1]=y
        else:
            self.parents[y-1]=x
N,M=map(int,input().split())
AB=[]
for _ in range(M):
    AB.append(tuple(map(int,input().split())))
friends=UnionFind(N)
for ab in AB:
    friends.union(ab[0],ab[1])
maxnum=0
for num in range(N+1):
    a=friends.parents.count(num)
    maxnum=max(maxnum,a)
print(maxnum)

Submission status: Time Limit Exceeded

Solution code:
N,M = tuple(map(int,input().split()))
# matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = list(range(N))
# [所属先,[所属メンバー]]
gplist = [[i] for i in range(N)]
def match(ab):
    a,b=ab
    gpa=friendlist[a]
    gpb=friendlist[b]
    mema=gplist[gpa].copy()
    memb=gplist[gpb].copy()
    if gpa==gpb:
        return
    else:
        gplist[gpa].extend(memb)
        for i in memb:
            friendlist[i]=gpa
        gplist[gpb] = [-1]

# print(gplist)
for i in range(M):
    match(tuple(map(lambda x:int(x)-1,input().split())))
    # print(friendlist)
    # print(gplist)
print(max([len(item) for item in gplist]))

Submission status: Time Limit Exceeded

Solution code:
N,M = tuple(map(int,input().split()))
# matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
# friendlist = [0 for i in range(N)]
gplist = [[-1]]
def match(ab):
    a,b=ab
    igpa = 0
    igpb = 0
    for i,gp in enumerate(gplist):
        if a in gp:
            igpa = i
            if b in gp:
                return
        elif b in gp:
            igpb = i
        if bool(igpa) and bool(igpb):
            break
    if not bool(igpa) and not bool(igpb):
        gplist.append([a,b])
    elif bool(igpa) and not bool(igpb):
        gplist[igpa].append(b)
    elif not bool(igpa) and bool(igpb):
        gplist[igpb].append(a)
    else:
        gplist[igpa].extend(gplist[igpb])
        gplist.remove(gplist[igpb])


# print(gplist)
for i in range(M):
    # match(matchlist[i])
    match(tuple(map(lambda x:int(x)-1,input().split())))
    # print(gplist)
print(max([len(item) for item in gplist]))

Submission status: Time Limit Exceeded

Solution code:
N,M = tuple(map(int,input().split()))
matchlist = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = [[i] for i in range(N)]

def match(ab):
    a,b=ab
    lsa = friendlist[a].copy()
    lsb = friendlist[b].copy()
    if a in lsb:
        return
    else:
        for ip in lsa:
            friendlist[ip].extend(lsb)
        for ip in lsb:
            friendlist[ip].extend(lsa)

for i in range(M):
    match(matchlist[i])
print(max([len(item) for item in friendlist]))

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

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

uf = UnionFind(n)
for i in range(m):
    friends = list(map(int, input().split()))
    uf.union(friends[0]-1,friends[1]-1)

uf_list = list(uf.all_group_members().values())

ans = 0

for i in range(len(uf_list)):
    l = len(uf_list[i])
    if ans < l:
        ans = l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = tuple(map(int,input().split()))
matchlist = [tuple(map(int,input().split())) for i in range(M)]
#最大のグループの大きさを出す
friendlist = [[i+1] for i in range(N)]

def match(a,b):
    for i,friends in enumerate(friendlist):
        if a in friends:
            ia = i
        if b in friends:
            ib = i
    if ia == ib:
        return
    else:
        friendlist[ia].extend(friendlist[ib])
        friendlist.remove(friendlist[ib])

for i in range(M):
    match(matchlist[i][0],matchlist[i][1])

print(max([len(item) for item in friendlist]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def dfs(graph, N, start=0):
    visited = [False] * N
    visited[start] = True
    stack = [start]
    res = [start]
    while stack:
        index = stack.pop()
        for node in graph[index]:
            if not visited[node]:
                stack.append(node)
                visited[node] = True
                res.append(node)
    return res

def main():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        A, B = map(lambda i: int(i)-1, input().split())
        graph[A].append(B)
        graph[B].append(A)

    ans = 0
    for i in range(N):
        res = dfs(graph, N, start=i)
        ans = max(ans, len(res))

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().rstrip().split(" ")))
members = [1 for i in range(n)]
max_idx = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  tmp_a = a
  tmp_b = b
  while members[tmp_a-1] < 0:
    tmp_a = -members[tmp_a-1]
  while members[tmp_b-1] < 0:
    tmp_b = -members[tmp_b-1]
  if a != tmp_a:
    members[a-1] = -tmp_a
  if b != tmp_b:
    members[b-1] = -tmp_b
  if tmp_a != tmp_b:
    members[tmp_a-1] += members[tmp_b-1]
    members[tmp_b-1] = -tmp_a
    if members[tmp_a-1] > members[max_idx]:
      max_idx = tmp_a-1
print(members[max_idx])

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().rstrip().split(" ")))
members = [1 for i in range(n)]
max_idx = 0
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  while members[a-1] < 0:
    a = -members[a-1]
  while members[b-1] < 0:
    b = -members[b-1]
  if a != b:
    members[a-1] += members[b-1]
    members[b-1] = -a
    if members[a-1] > members[max_idx]:
      max_idx = a-1
print(members[max_idx])

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().rstrip().split(" ")))
friend_mat = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
  friend_mat[i][i] = 1
for mm in range(m):
  a, b = list(map(int, input().rstrip().split(" ")))
  if not friend_mat[a-1][b-1]:
    friend_mat[a-1][b-1] = 1
    friend_mat[b-1][a-1] = 1
print(max([sum(friend_mat[i]) for i in range(n)]))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10000000)

class UnionFind:
    def __init__(self, N: int) -> None:
        self.par = [i for i in range(N)]
    
    def root(self, x: int) -> bool:
        if self.par[x] == x: #親が自分自身なら頂点
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        else:
            self.par[rx] = ry
    
    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        uf.unite(a-1, b-1)
    
    g = Counter(uf.root(x) for x in range(N))
    ans = g.most_common(1)[0][1]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# solve using union find

N, M = map(int, input().split())  # M pieces of information for N people

# if a parent, -1 * number of members
# else index of its parent
UF = [-1] * N


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

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

    if a != b:
        UF[a] += UF[b]
        UF[b] = a

print(-1 * min(UF))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())  # M pieces of information for N people

# if a parent, -1 * number of members
# else index of its parent
UF = [-1] * N
out = 1

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

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

    if a == b:
        continue
    else:
        UF[a] += UF[b]
        UF[b] = a
        out = max(out, -1 * UF[a])

print(out)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())  # M pieces of information for N people

# if a parent, -1 * number of members
# else index of its parent
UF = [-1] * N


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

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

    if a == b:
        continue
    else:
        UF[a] += UF[b]
        UF[b] = a

print(-1 * min(UF))

Submission status: Time Limit Exceeded

Solution code:
import copy

def dfs(k,E,A,B):
#    print("lenA is "+str(len(A)))
    for i in range(len(A)):
#        print("i is "+str(i))
#        print("k is "+str(k))
        if i >= len(A):
#            print("damedesu")
            break
#        print("A[i] is "+str(A[i]))
#        print("B[i] is "+str(B[i]))

        if k == A[i]:
            l = B[i]
            if l in E:
                pass
#                print("dame")
            else:    
                E.append(l)
                C = copy.copy(A)
                D = copy.copy(B)
                C.pop(i)
                D.pop(i)
                dfs(l,E,C,D)
        elif k == B[i]:
            l = A[i]
            if l in E:
                pass
#                print("dame")
            else:    
                E.append(l)
                C = copy.copy(A)
                D = copy.copy(B)
                C.pop(i)
                D.pop(i)
                dfs(l,E,C,D)
    return E
            
import numpy as np
N, M = map(int, input().split())
A = []
B = []
for _ in range(M):
    AA, BB = map(int, input().split())
    A.append(AA)
    B.append(BB)
    
C = copy.copy(A)
D = copy.copy(B)
num = np.arange(1,N+1)
maxi = 0
for i in range(N):
#    print("ni is "+str(i))
#    print("lennum is "+str(len(num)))
    if i >= len(num):
#        print("damedame")
        break
    k = num[i]
    E = [k]
    a = dfs(k,E,C,D)
    maxi = max(maxi,len(E))  
#    print("maxi is "+str(maxi))      
    
print(maxi)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
pairs = []
for i in [0]*M:
    inp = sorted(list(map(int,input().split())))
    if inp not in pairs:
        pairs.append(inp)
def solver(N,M,pairs):
    group_list = []
    max_len = 1
    for i in pairs:
        pair = sorted(i)
        for j in range(len(group_list)):
            if pair[1] in group_list[j]:
                break
            elif pair[0] in group_list[j]:
                group_list[j].append(pair[1])
                if max_len < len(group_list[j]):
                    max_len = len(group_list[j])
                break
        else:
            if max_len < 2:
                max_len = 2
            group_list.append(pair)
    return max_len
print(solver(N,M,pairs))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    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
    
    # xの属する集合の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]
    
    # xとyが同じ集合に属するかを判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    # 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())
    
    # groupとそれに属するメンバーの辞書を返す
    # exp. {0: [0, 1, 4], 2: [2, 3]}
    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())

union = UnionFind(N)

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

ans = 0
members = union.all_group_members()

for v in 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 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 {root: self.members(root) for root in self.roots()}

    def __str__(self):
        return '\n'.join(f'{root}: {self.members(root)}' for root in self.roots())


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

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

print(max(len(members) for members in uf.all_group_members().values()))

Submission status: Time Limit Exceeded

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

class unionfind():
    def __init__(self,n):
        self.li = [i for i in range(n+1)]
        self.group = [1]*(n+1)

    def find(self, x):
        while self.li[x]!=x:
            x = self.li[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return;
        else:
            self.li[y] = x
            self.group[x] += self.group[y]
            self.group[y] = 1
x = unionfind(n)
ans = 0
for _ in range(m):
    a,b = map(int,input().split())
    x.union(a,b)
print(max(x.group))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a, b = [], []
for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  a.append(_)
  b.append(__)
  
# union-find

# 誰の肩に手を置いているか（先頭の場合は-1）
parent = [-1 for i in range(n)]

# 列車の深さ
depth = [0 for i in range(n)]

# kさんの「運転手」が誰かを調べる関数
def find_root(k):
  while parent[k] != -1:
    k = parent[k]
  return k 

for i in range(m):
  # a[i] と b[i] の合併
  root_a = find_root(a[i])
  root_b = find_root(b[i])
  if root_a == root_b: continue
  
  # # 浅い列車を持っている方が負けるようにする
  # if depth[root_a] > depth[root_b]:
  #   root_a, root_b = root_b, root_a
  parent[root_a] = root_b
  depth[root_b] = max(depth[root_a]+1, depth[root_b])
  
group = [find_root(i) for i in range(n)]

from collections import Counter
print(Counter(group).most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a, b = [], []
for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  a.append(_)
  b.append(__)
  
# union-find

# 誰の肩に手を置いているか（先頭の場合は-1）
parent = [-1 for i in range(n)]

# 列車の深さ
depth = [0 for i in range(n)]

# kさんの「運転手」が誰かを調べる関数
def find_root(k):
  while parent[k] != -1:
    k = parent[k]
  return k 

for i in range(m):
  # a[i] と b[i] の合併
  root_a = find_root(a[i])
  root_b = find_root(b[i])
  
  # 浅い列車を持っている方が負けるようにする
  if depth[root_a] > depth[root_b]:
    root_a, root_b = root_b, root_a
  parent[root_a] = root_b
  depth[root_b] = max(depth[root_a]+1, depth[root_b])
  
group = [find_root(i) for i in range(n)]

from collections import Counter
print(Counter(group).most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a, b = [], []
for i in range(m):
  _, __ = map(int, input().split())
  _ -= 1
  __ -= 1
  a.append(_)
  b.append(__)
  
# union-find

# 誰の肩に手を置いているか（先頭の場合は-1）
parent = [-1 for i in range(n)]

# kさんの「運転手」が誰かを調べる関数
def find_root(k):
  while parent[k] != -1:
    k = parent[k]
  return k 

for i in range(m):
  # a[i] と b[i] の合併
  root_a = find_root(a[i])
  root_b = find_root(b[i])
  # root_a が root_b に勝ったとする
  parent[root_b] = root_a
  
group = [find_root(i) for i in range(n)]

from collections import Counter
print(Counter(group).most_common()[0][1])

Submission status: Time Limit Exceeded

Solution code:
#ABC177
#D - Friends

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

friends=[]
member=[]

for i in range(M):
  x,y=map(lambda x :int(x)-1,input().split())
  j=sorted([x,y])
  if j not in friends:
    friends.append(j)
    member.extend(j)

member2=[i for i in set(member) if member.count(i)>1 ]

for i in member2:
  a=[k for j in friends if i in j for k in j]
  c=[j for j in friends if i not in j]
  friends=[list(set(a))]+c

group=[len(i) for i in friends]    

if len(group)==0:
  print(1)
else:
  print(max(group))

Submission status: Time Limit Exceeded

Solution code:
#ABC177
#D - Friends

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

friends=[[i] for i in range(N)]
member=[]
member2=[]
for i in range(M):
  x,y=map(lambda x :int(x)-1,input().split())
  friends.append([x,y])
  member.extend([x,y])



member2=[i for i in set(member) if member.count(i)>1 ]

for i in member2:
  a=[k for j in friends if i in j for k in j]
  c=[j for j in friends if i not in j]
  friends=[list(set(a))]+c

group=[len(i) for i in friends]    

if len(group)==0:
  print(1)
else:
  print(max(group))

Submission status: Time Limit Exceeded

Solution code:
#ABC177
#D - Friends

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

friends=[[i] for i in range(N)]
member=[]
member2=[]
for i in range(M):
  x,y=map(lambda x :int(x)-1,input().split())
  friends[x].append(y)
  friends[y].append(x)
  if x in member:
    member2.append(x)
  if y in member:
    member2.append(y)
  member.extend([x,y])


#friends=[sorted(set(i)) for i in friends if len(i)!=1]
#friends=list(map(list,set(map(tuple,friends))))

member2=sorted(set(member2))

for i in member2:

  a=[k for j in friends if i in j for k in j]
  c=[j for j in friends if i not in j]
  friends=[list(set(a))]+c

group=[len(i) for i in friends]    

if len(group)==0:
  print(1)
else:
  print(max(group))

Submission status: Time Limit Exceeded

Solution code:
#ABC177
#D - Friends

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

friends=[[i] for i in range(N)]
member=[]
member2=[]
for i in range(M):
  x,y=map(lambda x :int(x)-1,input().split())
  friends[x].append(y)
  friends[y].append(x)
  if x in member:
    member2.append(x)
  if y in member:
    member2.append(y)
  member.extend([x,y])


friends=[sorted(set(i)) for i in friends if len(i)!=1]
friends=list(map(list,set(map(tuple,friends))))

member2=sorted(set(member2))

for i in member2:
  a=[k for j in friends if i in j for k in j]
  c=[j for j in friends if i not in j]
  friends=[list(set(a))]+c

group=[len(i) for i in friends]    

if len(group)==0:
  print(1)
else:
  print(max(group))

Submission status: Time Limit Exceeded

Solution code:
#ABC177
#D - Friends

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

friends=[[i] for i in range(N)]
member=[]
member2=[]
for i in range(M):
  x,y=map(lambda x :int(x)-1,input().split())
  friends[x].append(y)
  friends[y].append(x)
  if x in member:
    member2.append(x)
  if y in member:
    member2.append(y)
  member.extend([x,y])


friends=[sorted(set(i)) for i in friends if len(i)!=1]

member2=sorted(set(member2))

for i in member2:
  a=[]
  c=[]
  for j in range(len(friends)):
    b=friends[j]
    if i in b:
      a.extend(b)
    else:
      c.append(b)
  friends=[list(set(a))]+c
  
group=[len(i) for i in friends]    

if len(group)==0:
  print(1)
else:
  print(max(group))

Submission status: Time Limit Exceeded

Solution code:
#ABC177
#D - Friends

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

friends=[[i] for i in range(N)]
member=[]
member2=[]
for i in range(M):
  x,y=map(lambda x :int(x)-1,input().split())
  friends[x].append(y)
  friends[y].append(x)
  if x in member:
    member2.append(x)
  if y in member:
    member2.append(y)
  member.extend([x,y])


friends=[sorted(set(i)) for i in friends if len(i)!=1]

#member=sorted(set(member))

for i in member2:
  a=[]
  c=[]
  for j in range(len(friends)):
    b=friends[j]
    if i in b:
      a.extend(b)
    else:
      c.append(b)
  friends=[list(set(a))]+c
  
group=[len(i) for i in friends]    

if len(group)==0:
  print(1)
else:
  print(max(group))

Submission status: Time Limit Exceeded

Solution code:
#ABC177
#D - Friends

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

friends=[[i] for i in range(N)]
member=[]

for i in range(M):
  x,y=map(lambda x :int(x)-1,input().split())
  friends[x].append(y)
  friends[y].append(x)
  member.extend([x,y])

friends=[sorted(set(i)) for i in friends if len(i)!=1]

member=sorted(set(member))

for i in member:
  a=[]
  c=[]
  for j in range(len(friends)):
    b=friends[j]
    if i in b:
      a.extend(b)
    else:
      c.append(b)
  friends=[list(set(a))]+c
  
group=[len(i) for i in friends]    

if len(group)==0:
  print(1)
else:
  print(max(group))