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 = [set() for i 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)

checked = [False for _ in range(N)]
ans = 0
for i in range(N):
    if checked[i]:
        continue

    checked[i] = True
    A = G[i]
    tmp = 1
    while len(A) > 0:
        e = A.pop()
        if checked[e]:
            continue
        checked[e] = True
        tmp += 1
        A = A | G[e]

    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {}

for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    if a in friends_map:
        friends_map[a].add(b)
    else:
        friends_map[a] = {b}

    if b in friends_map:
        friends_map[b].add(a)
    else:
        friends_map[b] = {a}

stack = deque()
stack.appendleft(0)

remain_user = {i for i in range(N)}

max_group = 0
watch = set()
while stack:
    now = stack.popleft()
    remain_user.discard(now)
    watch.add(now)

    if now in friends_map:
        for next_node in friends_map[now]:
            if not next_node in watch:
                stack.appendleft(next_node)
                remain_user.discard(next_node)

    if not stack:
        if len(watch) > max_group:
            max_group = len(watch)

        if remain_user:
            stack.appendleft(remain_user.pop())
            watch = set()

print(max_group)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]

friends_map = {}

for m in range(M):
    a, b = [int(x) - 1 for x in input().split()]

    if a in friends_map:
        friends_map[a].add(b)
    else:
        friends_map[a] = {b}

    if b in friends_map:
        friends_map[b].add(a)
    else:
        friends_map[b] = {a}

stack = deque()
stack.appendleft(0)

remain_user = {i for i in range(N)}

max_group = 0
watch = set()
while stack:
    now = stack.popleft()
    remain_user.discard(now)
    watch.add(now)

    if now in friends_map:
        for next_node in friends_map[now]:
            if not next_node in watch:
                stack.appendleft(next_node)
                remain_user.discard(next_node)

    if len(watch) > max_group:
        max_group = len(watch)

    if not stack:
        if remain_user:
            stack.appendleft(remain_user.pop())
            watch = set()

print(max_group)

Submission status: Time Limit Exceeded

Solution code:
# 連結成分に分解、異なる連結成分から一人ずつ集めたグループが１セット。
# これを全ての連結成分が空になるまで繰り返す。
# 全ての連結成分が空になる <===> 連結成分の最大の要素数回この操作を繰り返せば良い。
# Union FInd が一番適してそう。
class UnionFind():
    
    def __init__(self,N):
        self.N = N
        self.par = [-1]*N
    
    def find(self,x):
        if self.par[x]<0:return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return 
        
        if self.par[x]>self.par[y]:
            x,y = y,x
        
        self.par[x] += self.par[y]
        self.par[y] = x
    
    def members(self,x):
        root = self.find(x)
        return len([i for i in range(self.N) if self.find(i)==root])

    def roots(self):
        return [i for i,x in enumerate(self.par) if x < 0]
    
    def calc_max_mem(self):
        root = self.roots()
        nums = [self.members(r) for r in root]
        return max(nums)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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 all_group_memberss(self):
        return [len(self.members(r)) for r in self.roots()]

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


def main():
    N, M = [int(x) for x in input().split()]
    AB = [[int(x) for x in input().split()] for _ in range(M)]

    uf = UnionFind(N)

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

    hq = []
    for k in uf.all_group_memberss():
        heapq.heappush(hq, k)

    ans = 0
    prev = 0
    while hq:
        c = heapq.heappop(hq)
        if prev != c:
            ans += (c - prev)
            prev = c

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def uf_find(x):
  if x == p[x]:
    return x
  else:
    p[x] = uf_find(p[x])
    return p[x]

def uf_unite(x,y):
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    if r[y]>r[x]:
      x,y = y,x
    if r[x]==r[y]:
      r[x]+= 1
    p[y] = x
    #print(r)


N, M = map(int, input().split())
p = list(range(N))
r = [0]*N

for i in range(M):
  A, B = [int(j)-1 for j in input().split()]
  uf_unite(A,B)
  #print(p)
  
#for i in range(N):
  #p[i] = uf_find(i)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Time Limit Exceeded

Solution code:
def uf_find(x):
  if x == p[x]:
    return x
  else:
    p[x] = uf_find(p[x])
    return p[x]

def uf_unite(x,y):
  global rand
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    if r[y]>r[x]:
      x,y = y,x
    if r[x]==r[y]:
      r[x]+= 1
    p[y] = x


N, M = map(int, input().split())
p = list(range(N))
r = [0]*N

rand = 0

for i in range(M):
  A, B = [int(j)-1 for j in input().split()]
  uf_unite(A,B)
  #print(p)
  
for i in range(N):
  p[i] = uf_find(i)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Time Limit Exceeded

Solution code:
def uf_find(x):
  z = x
  while z != p[z]:
    z = p[z]
  p[x] = z
  return z

def uf_unite(x,y):
  global rand
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    if r[y]>r[x]:
      x,y = y,x
    if r[x]==r[y]:
      r[x]+= 1
    p[y] = x


N, M = map(int, input().split())
p = list(range(N))
r = [0]*N

rand = 0

for i in range(M):
  A, B = [int(j)-1 for j in input().split()]
  uf_unite(A,B)
  #print(p)
  
for i in range(N):
  p[i] = uf_find(i)


q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
import sys
sys.setrecursionlimit(10**7)

# 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())
uf=UnionFind(n)
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  uf.union(a,b)
ans=0
d=uf.all_group_members()
for c in d.values():
  ans=max(ans,len(c))
print(ans)

Submission status: Time Limit Exceeded

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

# 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())
uf=UnionFind(n)
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  uf.union(a,b)
ans=0
d=uf.all_group_members()
for c in d.values():
  ans=max(ans,len(c))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def uf_find(x):
  z = x
  while z != p[z]:
    z = p[z]
  p[x] = z
  return z

def uf_unite(x,y):
  global rand
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    rand += 1
    if rand % 2 ==0:
      p[y] = x
    else:
      p[x] = y

N, M = map(int, input().split())
p = list(range(N))
rand = 0

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

  
for i in range(N):
  p[i] = uf_find(i)


q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
from networkx.utils.union_find import UnionFind
n,m=map(int,input().split())
a=[[i for i in input().split()] for _ in range(m)]
g=nx.Graph()
uf=UnionFind([i for i in range(n)])
for x in a:
     uf.union(x[0],x[1])
print(len(max(uf.to_sets(),key=len)))

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

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.union(a, b)
  
  max_len = 0
  for g in list(uf.all_group_members().values()):
    len_g = len(g)
    if len_g > max_len:
      max_len = len_g
      
  print(max_len)
  
main()

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
n,m=map(int,input().split())
a=[[i for i in input().split()] for _ in range(m)]
g=nx.Graph()
g.add_nodes_from([i for i in range(n)])
for x in a:
     g.add_edge(x[0],x[1])
print(len(sorted(nx.connected_components(g),key=len,reverse=True)[0]))

Submission status: Time Limit Exceeded

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

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

R = [set(map(int, input().split(" "))) for i in range(M)]

groups = []
while len(R) > 0:
    r = R.pop()
    for r_ in R:
        if len(r & r_) > 0:
            R.remove(r_)
            r |= r_
    groups.append(r)

print(max(map(len, groups)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math
import itertools
INF = float('inf')
from heapq import heapify, heappop, heappush


n,m = map(int, input().split())
par = [i for i in range(n)]
rank = [0]*n

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def main():
    for _ in range(m):
        a,b = map(int, input().split())
        unite(a-1,b-1)
    ans = 0
    for i in range(len(par)):
        tmp = 0
        for j in range(len(par)):
            if par[j] == i:
                tmp += 1
        ans = max(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
G = Graph()
G.add_nodes_from(range(1, n+1))
G.add_edges_from(edges)
ccs = connected_components(G)
ans = max(map(len, ccs))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
am_bm = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_min = min([a, b])
    ab_max = max([a, b])
    am_bm.append((ab_min, ab_max))
am_bm.sort(key=lambda x: x[0])

groups = []
for ai, bi in am_bm:
    ag = None
    bg = None
    for g, group in enumerate(groups):
        if ai in group:
            ag = g
        if bi in group:
            bg = g
    if ag is None:
        if bg is None:
            groups.append({ai, bi})
        else:
            groups[bg].add(ai)
    else:
        if bg is None:
            groups[ag].add(bi)
        else:
            if ag != bg:
                groups[ag] = groups[ag].union(groups[bg])
                del groups[bg]

# max_gr_len = 1
# for group in groups:
#     if max_gr_len < len(group):
#         max_gr_len = len(group)
max_gr_len = max([len(group) for group in groups] + [1])

print(max_gr_len)

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
am = []
bm = []
for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_min = min([a, b])
    ab_max = max([a, b])
    am.append(ab_min)
    bm.append(ab_max)
am.sort()
bm.sort()

groups = []
for ai, bi in zip(am, bm):
    ag = None
    bg = None
    for g, group in enumerate(groups):
        if ai in group:
            ag = g
        if bi in group:
            bg = g
    if ag is None:
        if bg is None:
            groups.append([ai, bi])
        else:
            groups[bg].append(ai)
    else:
        if bg is None:
            groups[ag].append(bi)
        else:
            if ag != bg:
                groups[ag].extend(groups[bg])
                del groups[bg]

# max_gr_len = 1
# for group in groups:
#     if max_gr_len < len(group):
#         max_gr_len = len(group)
max_gr_len = max([len(group) for group in groups] + [1])

print(max_gr_len)

Submission status: Time Limit Exceeded

Solution code:
info_str = input()

human_num, info_num = info_str.split()

rel_list = []

for i in range(int(info_num)):
    rel_list.append(input().split())

friends_group = []

for x, y in rel_list:
    found = False
    for group in friends_group:
        found = False
        if y in group:
            group.extend([x, y])
            found = True
            break
    if not found:
        friends_group.append([x, y])

max_member_num = 1

for group in friends_group:
    member_num = len(set(group))
    if max_member_num < member_num:
        max_member_num = member_num




print(max_member_num)

Submission status: Time Limit Exceeded

Solution code:
info_str = input()

human_num, info_num = info_str.split()

rel_list = []

for i in range(int(info_num)):
    rel_list.append(input().split())

friends_group = []

for x, y in rel_list:
    found = False
    for group in friends_group:
        found = False
        if y in group:
            group.add(x)
            group.add(y)
            found = True
            break
    if not found:
        friends_group.append(set([x, y]))

max_member_num = 1

for group in friends_group:
    member_num = len(group)
    if max_member_num < member_num:
        max_member_num = member_num




print(max_member_num)

Submission status: Time Limit Exceeded

Solution code:
def uf_find(x):
  z = x
  while z != p[z]:
    z = p[z]
  p[x] = z
  return z

def uf_unite(x,y):
  x = uf_find(x)
  y = uf_find(y)
  if x != y:
    p[y] = x

N, M = map(int, input().split())
p = list(range(N))

for i in range(M):
  A, B = [int(i)-1 for i in input().split()]
  uf_unite(A,B)
  #print(p)

for i in range(N):
  p[i] = uf_find(i)
#print(p)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
	N, M = map(int, input().strip().split())

	groups = []

	for _ in range(M):
		Ai, Bj = map(int, input().strip().split())

		g_ai = -1
		g_bj = -1

		for i, group in enumerate(groups):
			if Ai in group:
				g_ai = i
			if Bj in group:
				g_bj = i
			if g_ai > -1 and g_bj > -1:
				break

		if g_ai < 0 and g_bj < 0:
			new_g = set([Ai, Bj])
			groups.append(new_g)

		elif g_ai < 0 and g_bj > -1:
			groups[g_bj].add(Ai)

		elif g_ai > -1 and g_bj < 0:
			groups[g_ai].add(Bj)

		elif g_ai != g_bj:
			new_g = groups[g_ai] | groups[g_bj]
			groups.append(new_g)
			del groups[g_ai]
			del groups[g_bj]

	if not groups:
		print(1)
	else:
		print(max([len(g) for g in groups]))

main()

Submission status: Time Limit Exceeded

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

	groups = []

	for _ in range(M):
		Ai, Bj = map(int, input().strip().split())

		g_ai = -1
		g_bj = -1

		for i, group in enumerate(groups):
			if Ai in group:
				g_ai = i
			if Bj in group:
				g_bj = i
			if g_ai > -1 and g_bj > -1:
				break

		if g_ai < 0 and g_bj < 0:
			new_g = set([Ai, Bj])
			groups.append(new_g)

		elif g_ai < 0 and g_bj > -1:
			groups[g_bj].add(Ai)

		elif g_ai > -1 and g_bj < 0:
			groups[g_ai].add(Bj)

		elif g_ai != g_bj:
			new_g = groups[g_ai] | groups[g_bj]
			groups.append(new_g)
			del groups[g_ai]
			del groups[g_bj]

	if not groups:
		print(1)
	else:
		print(max([len(g) for g in groups]))

main()

Submission status: Time Limit Exceeded

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

groups = []

for _ in range(M):
	Ai, Bj = map(int, input().strip().split())

	g_ai = -1
	g_bj = -1

	for i, group in enumerate(groups):
		if Ai in group:
			g_ai = i
		if Bj in group:
			g_bj = i
		if g_ai > -1 and g_bj > -1:
			break

	if g_ai < 0 and g_bj < 0:
		new_g = set([Ai, Bj])
		groups.append(new_g)

	elif g_ai < 0 and g_bj > -1:
		groups[g_bj].add(Ai)

	elif g_ai > -1 and g_bj < 0:
		groups[g_ai].add(Bj)

	elif g_ai != g_bj:
		new_g = groups[g_ai] | groups[g_bj]
		groups.append(new_g)
		del groups[g_ai]
		del groups[g_bj]

if not groups:
	print(1)
else:
	print(max([len(g) for g in groups]))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        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

    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]

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

    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = MAP()
    
    tree = UnionFind(N)
    for _ in range(M):
        a, b = MAP()
        tree.union(a - 1, b - 1)

    ans = 0
    for l in tree.all_group_members().values():
        ans = max(ans, len(l))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def uf_find(x):
  while x != p[x]:
    x = p[x]
  return(x)

def uf_unite(x,y):
  x = uf_find(x)
  y = uf_find(y)
  if x == y:
    pass
  else:
    p[x] = y

N, M = map(int, input().split())
p = list(range(N))

for i in range(M):
  A, B = [int(i)-1 for i in input().split()]
  uf_unite(A,B)
  #print(p)

for i in range(N):
  p[i] = uf_find(i)
#print(p)

q = [0]*N
for i in range(N):
  q[i] = p.count(i)
  
print(max(q))

Submission status: Time Limit Exceeded

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

groups = []

for _ in range(M):
	Ai, Bj = map(int, input().strip().split())

	g_ai = -1
	g_bj = -1

	for i, group in enumerate(groups):
		if Ai in group:
			g_ai = i
		if Bj in group:
			g_bj = i

	if g_ai < 0 and g_bj < 0:
		new_g = set([Ai, Bj])
		groups.append(new_g)

	elif g_ai < 0 and g_bj > -1:
		groups[g_bj].add(Ai)

	elif g_ai > -1 and g_bj < 0:
		groups[g_ai].add(Bj)

	elif g_ai != g_bj:
		new_g = groups[g_ai] | groups[g_bj]
		groups.append(new_g)
		groups[g_ai] = set()
		groups[g_bj] = set()

if not groups:
	print(1)
else:
	print(max([len(g) for g in groups]))

Submission status: Time Limit Exceeded

Solution code:
def find(e):
  if parent[e] == e:
    return e
  return find(parent[e])
n, m = map(int,input().split())
l = []
for _ in range(m):
  p, q = map(int,input().split())
  p -= 1
  q -= 1
  if (p,q) not in l:
    l.append((p,q))
parent = [i for i in range(n)]
for i,j in l:
  x = find(i)
  y = find(j)
  if x > y:
      x, y = y, x
  parent[y] = x
mx = 0
for i in set(parent):
    mx = max(mx,parent.count(i))
print(mx)

Submission status: Time Limit Exceeded

Solution code:
def find(e):
  if parent[e] == e:
    return e
  return find(parent[e])
n, m = map(int,input().split())
l = []
for _ in range(m):
  p, q = map(int,input().split())
  p -= 1
  q -= 1
  if (p,q) not in l:
    l.append((p,q))
parent = [i for i in range(n)]
for i,j in l:
  x = find(i)
  y = find(j)
  if x > y:
      x, y = y, x
  parent[y] = x
dic = {}
for i in parent:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
mx = 0
for i in dic.values():
    mx = max(mx,i)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
def find(e):
  if parent[e] == e:
    return e
  return find(parent[e])
n, m = map(int,input().split())
l = []
for _ in range(m):
  p, q = map(int,input().split())
  p -= 1
  q -= 1
  if (p,q) not in l:
    l.append((p,q))
parent = [i for i in range(n)]
rank = [0 for i in range(n)]
for i,j in l:
  x = find(i)
  y = find(j)
  if rank[x]<rank[y]:
      parent[x] = y
      rank[y] += 1
  else:
      parent[y] = x
      rank[x] += 1
dic = {}
for i in parent:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1
mx = 0
for i in dic.values():
    mx = max(mx,i)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
branch = set(tuple(map(int,input().split())) for i in range(m))
que = range(n)
flag = -1
friend = [{0}]

for a,b in branch:
    for i in range(len(friend)):
        if (a in friend[i]) and (b in friend[i]):
            break
        if (a in friend[i]) or (b in friend[i]):
            friend[i].add(a)
            friend[i].add(b)
            if flag >= 0:
                friend[flag] = friend[flag]|friend[i]
                friend.pop(i)
                break
            flag = i
    if flag == -1:
        friend.append({a,b})
    else: flag = -1

len_friend = list(len(i) for i in friend)
print(max(len_friend))

Submission status: Time Limit Exceeded

Solution code:
def main():
 
    def find(target):
        if parent[target] < 0:
            return target
        else:
            parent[target] = find(parent[target])
            return parent[target]
 
    def is_same(x, y):
        return find(x) == find(y)
 
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x == root_y:
            return
        if parent[root_x] > parent[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_x] += parent[root_y]
        parent[root_y] = root_x

    def members(n, x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]
 
    def get_size(x):
        return -parent[find(x)]
 
    def get_root():
        return [i for i, root in enumerate(parent) if root < 0]

    n, m = map(int, input().split())
    parent = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        union(a, b)
        # print(parent)
    # ans = 0
    # for i in range(n):
    #     ans = max(ans, get_size(i))
    # print(ans)
    max_member = 0
    for i in get_root():
        # print(i, members(n, i))
        max_member  = max(max_member, len(members(n, i)))
    print(max_member)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
(N,M),*A=[[*map(int,t.split())] for t in open(0)]
if M==0:
    print(1)
else:
    frends=[{*A[0]}]
    for (a,b) in A:
        flg = True
        for ifre in range(len(frends)):
            if a in frends[ifre]:
                frends[ifre].add(b)
                flg=False
                break   
            if b in frends[ifre]:
                frends[ifre].add(a)
                flg=False
                break
        if flg:
            frends.append({a,b})
    print(max([len(f) for f in frends]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

# from pprint import pprint
# import math
# import collections

# n = stdin.readline().rstrip()
# n = int(n)

n, m = [int(x) for x in stdin.readline().rstrip().split()]
# a = [int(x) for x in l]

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

d = [stdin.readline().rstrip().split() for _ in range(m)]
d = [tuple(map(int, x)) for x in d]

tomo_grp = []

for rel in d:
    if tomo_grp:
        a = rel[0]
        b = rel[1]

        for i in range(len(tomo_grp)):
            if a in tomo_grp[i] or b in tomo_grp[i]:
                tomo_grp[i].add(a)
                tomo_grp[i].add(b)
                # elif b in tomo_grp[i]:
                #     tomo_grp[i].add(a)
                break
            else:
                # print(i,rel)
                tomo_grp.append(set(rel))

    else:
        tomo_grp.append(set(rel))

tomos = [len(grp) for grp in tomo_grp]
# print(tomos)
max_tomo = max(tomos)
print(max_tomo)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
branch = set(tuple(map(int,input().split())) for i in range(m))
que = range(n)
flag = -1
friend = [{0}]

for a,b in branch:
    for i in range(len(friend)):
        if (a in friend[i]) or (b in friend[i]):
            friend[i].add(a)
            friend[i].add(b)
            if flag >= 0:
                friend[flag] = friend[flag]|friend[i]
                friend.pop(i)
                break
            flag = i
    if flag == -1:
        friend.append({a,b})
    else: flag = -1

len_friend = list(len(i) for i in friend)
print(max(len_friend))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())

root = [-1]*n

def find(n):
    if root[n] < 0:
        return n
    else:
        root[n] = find(root[n])
        return root[n]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    else:
        root[x] += root[y]
        root[y] = x

def size(n):
    return -root[find(n)]

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

ans = max(map(size, range(n)))
print(ans)