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: Runtime Error

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-08-29 22:53
# @url:https://atcoder.jp/contests/abc177/tasks/abc177_d
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
from decimal import *
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
def main():
    n,m=map(int,input().split())
    pairs=[]
    for i in range(m):
        a,b=map(int,input().split())
        temp=[]
        temp.append(a)
        temp.append(b)
        pairs.append(temp)
    fa=[i for i in range(n+1)]
    def find(x):
        if x!=fa[x]:
            fa[x]=find(fa[x])
        return fa[x]
    def union(x,y):
        x = find(x)
        y = find(y)
        if x == y:  
            return
        fa[x] = y
    for (i,j) in pairs:
        union(i,j)
    for (i,j) in pairs:
        union(j,i)
    d=collections.Counter(fa)
    sd=sorted(d.items(),key=lambda x:x[1])
    print (sd[-1][1])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

pg = [-1] * (N + 1)  # person's group
gpc = []  # group person count
gc = 0  # group count

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

	if pg[Ai] > -1 and pg[Bj] > -1:
		continue

	if pg[Ai] < 0 and pg[Bj] < 0:
		pg[Ai] = gc
		pg[Bj] = gc
		gpc.append(2)
		gc += 1

	if pg[Ai] < 0:
		pg[Ai] = pg[Bj]
		gpc[pg[Ai]] += 1

	if pg[Bj] < 0:
		pg[Bj] = pg[Ai]
		gpc[pg[Bj]] += 1

if not gpc:
	print(1)
print(max(gpc))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def main():
    n, m, *ab, = map(int, open(0).read().split())
    f = [set() for _ in range(n)]
    for i, j in zip(ab[::2], ab[1::2]):
        f[i].add(j)
        f[j].add(i)

    group = []
    i = 1
    g = {i}
    nx = {i}
    checked = set()
    m = 0
    ans = 0
    while i <= n:
        if i in checked:
            i += 1
            continue

        tmp = set()
        for j in list(nx):
            tmp |= f[j]
        tmp -= nx

        if len(tmp) == 0:
            checked |= g
            group.append(g)
            l = len(g)
            m += l
            r = n - m
            ans = max(ans, l)
            if l >= r:
                break
            i += 1
            g = {i}
        else:
            g |= tmp
            nx = tmp

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:

N,M=map(int, input().split())
l=[[]for j in range(N)]
field=[True]*N
for i in range(M):
    a,b=map(int,input().split())
    l[a-1].append(b-1)
    l[b-1].append(a-1)
for i in range(N):
    l[i]=list(set(l[i]))

def dfs(x):
    conn=1
    field[x]=False
    for j in range(len(l[x])):
        if field[l[x][j]]:
            conn+=dfs(l[x][j])
    return conn

nax=0
for i in range(N):
    temp=dfs(i)
    nax=max(nax,temp)

print(nax)

Submission status: Runtime Error

Solution code:
import collections

n, m = map(int, input().split())
if m == 0:
    print(1)
    exit()
if m == 1:
    print(2)
    exit()
ids = {i: 0 for i in range(1, n+1)}
id = 1
for _ in range(m):
    a, b = map(int, input().split())
    if ids[a] == 0 and ids[b] != 0:
        ids[a] = ids[b]
    elif ids[a] != 0 and ids[b] == 0:
        ids[b] = ids[a]
    elif ids[a] == 0 and ids[b] == 0:
        ids[a] = id
        ids[b] = id
        id += 1
tmp = collections.Counter(ids.values())
tmp.pop(0)
print(max(tmp.values()))

Submission status: Runtime Error

Solution code:

N,M=map(int, input().split())
l=[[]for j in range(N)]
field=[True]*N
for i in range(M):
    a,b=map(int,input().split())
    l[min(a,b)-1].append(max(a,b)-1)
for i in range(N):
    l[i]=list(set(l[i]))

def dfs(x):
    conn=1
    field[x]=False
    for j in range(len(l[x])):
        if field[l[x][j]]:
            conn+=dfs(l[x][j])
    return conn

nax=0
for i in range(N):
    temp=dfs(i)
    nax=max(nax,temp)

print(nax)

Submission status: Runtime Error

Solution code:
import sys

parents = [-1] * 20000

def main():

    input = sys.stdin.readline

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

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

    for i in range(M):
        A,B = AB[i]

        A = A - 1
        B = B - 1

        union(A,B)


    ans = 1
    for i in range(20000):
        ans = max(ans,size(i))

    print(ans)

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

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

    if x == y:
        return 0

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

    parents[x] += parents[y]
    parents[y] = x

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def search(x, num):
    nodes.remove(x)
    for y in edge[x]:
        edge[y].discard(x)
    for y in list(edge[x]):
        if y in nodes:
            num = search(y, num)
    return num + 1

(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = {}
for x in d:
    if x[0] in edge:
        edge[x[0]].add(x[1])
    else:
        edge[x[0]] = {x[1]}
    if x[1] in edge:
        edge[x[1]].add(x[0])
    else:
        edge[x[1]] = {x[0]}

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x in nodes:
        ans = max(ans, search(x, 0))
print(ans)

Submission status: Runtime Error

Solution code:
class UFTree():
  def __init__(self,n):
    self.N = n
    self.parent = {i:i for i in range(1,n+1)}
    
  def root(self,n):
    if self.parent[n]==n: return n
    else:
      self.parent[n] = self.root(self.parent[n])
      return self.parent[n]
      
  def unite(self,x,y):
    rx,ry = self.root(x), self.root(y)
    if rx>ry: rx,ry = ry,rx
    if rx!=ry: self.parent[rx] = ry
      
  def size(self,x):
    n = 0
    return sum([self.root(i+1)==x for i in range(self.N)])
  
N,M = map(int,input().split())
uft = UFTree(N)
for i in range(M):
  A,B = map(int,input().split())
  uft.unite(A,B)
print(max({i+1:uft.size(i+1) for i in range(N)}.values()))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys

parents = [-1] * 20000

def main():

    input = sys.stdin.readline

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


    for _ in range(M):
        A,B = map(int,input().split())

        A = A - 1
        B = B - 1

        union(A,B)

    ans = 1
    for i in range(20000):
        ans = max(ans,size(i))

    print(ans)

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

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

    if x == y:
        return 0

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

    parents[x] += parents[y]
    parents[y] = x

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

dic = dict()
dicSet = set()
dicList = dict()
count = 0
countList= set()

ans = 0

for i in range(m):
    a,b = list(map(int,input().split()))
    if not(a in dicSet) and not(b in dicSet):
        dic[count] = set()
        dic[count].add(a)
        dic[count].add(b)
        dicList[a] = count
        dicList[b] = count
        countList.add(count)
        count += 1
        dicSet.add(a)
        dicSet.add(b)

    elif a in dicSet and b in dicSet:
        if dicList[a] != dicList[b]:
            dic[count] = dic[dicList[a]] | dic[dicList[b]]
            countList.add(count)
            del dic[dicList[a]]
            countList.discard(dicList[a])
            del dic[dicList[b]]
            countList.discard(dicList[b])
            dicList[a] = count
            dicList[b] = count
            count += 1

    elif a in dicSet:
        dic[dicList[a]].add(b)
        dicList[b] = dicList[a]
        dicSet.add(b)
    else:
        dic[dicList[b]].add(a)
        dicList[a] = dicList[b]
        dicSet.add(a)


ans = 1

#print(dic)
#print(countList)

for i in countList:
    long = len(dic[i])
    if long > ans:
        ans = long

print(ans)

Submission status: Runtime Error

Solution code:
import array
#import random
import sys

#N, M = 100000, 100000
N, M = list(map(int, input().split()))
R = [[] for _ in range(N+1)]
sys.setrecursionlimit(200000)

def grp(R, i, S):
    S[i] = True
    ret = 1
    for j in range(len(R[i])):
        if S[ R[i][j] ]: continue
        ret += grp(R, R[i][j], S)
    return ret

for i in range(M):
    a, b = list(map(int, input().split()))
#    a, b = random.choice(range(N)), random.choice(range(N))
    R[a].append(b)
    R[b].append(a)

S = [False] * (N+1)
maxgrp = 1
for i in range(1, N+1):
    if S[i]: continue
    grpsize = grp(R, i, S)
#    print (grpsize)
    maxgrp = max(grpsize, maxgrp)

print(maxgrp)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
if M == 0:
    print(1)
else:
    D = {}
    count = 0
    friends = []
    while count < M:
        A, B = map(int,input().split())
        Info += {A,B}
        count += 1
    for i in Info:
        k = Info.index(i)
        for j in Info:
            if len(i.intersection(j)) != 0:
                Info[k] = i.union(j)
                Info = Info.remove(j)
    print(max(len(I) for I in Info))

Submission status: Runtime Error

Solution code:
import sys

parents = [-1] * 20000

def main():

    input = sys.stdin.readline

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


    for _ in range(M):
        A,B = map(int,input().split())

        A = A - 1
        B = B - 1

        union(A,B)

    ans = 1
    for i in range(20000):
        ans = max(ans,size(i))

    print(ans)

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

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

    if x == y:
        return

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

    parents[x] += parents[y]
    parents[y] = x

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
friends = {i:[] for i in range(1, n+1)}

for _ in range(m):
  a,b = map(int, input().split())
  friends[a].append(b)
  friends[b].append(a)

seen = []
def dfs(n):
  if n not in seen:
    seen.append(n)
    for f_i in friends[n]:
      if f_i in seen:
        continue
      else:
        dfs(f_i)

ans = 0
found = []
for i in range(1, n+1):
  dfs(i)
  ans = max(ans, len(seen)-len(found))
  found = seen
  
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')

Submission status: Runtime Error

Solution code:
import sys

parents = [-1] * 20000

def main():

    input = sys.stdin.readline

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


    for _ in range(M):
        A,B = map(int,input().split())

        A = A - 1
        B = B - 1

        union(A,B)

    ans = 1
    for i in range(N):
        ans = max(ans,size(i))

    print(ans)

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

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

    if x == y:
        return

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

    parents[x] += parents[y]
    parents[y] = x

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

lis = [[] for _ in range(N+1)]
for i in range(M):
    A,B = map(int,input().split())
    A,B = min(A,B),max(A,B)
    lis[A].append(B)

cnt = 0
seen = [False]*(N+1)
def dfs(v,graph):
    global cnt
    seen[v] = True
    for next_v in graph[v]:
        if seen[next_v] == True:
             continue
        if seen[next_v] == []:
             continue
        cnt += 1
        dfs(next_v,graph)
    return cnt

ma = 0
for j in range(N):
    cnt = 0
    if seen[j] == True:
        continue
    ma = max(ma,dfs(j,lis))
print(ma+1)

Submission status: Runtime Error

Solution code:
import array

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

def grp(R, i, S):
    S[i] = True
    ret = 1
    for j in range(len(R[i])):
        if S[ R[i][j] ]: continue
        ret += grp(R, R[i][j], S)
    return ret

for i in range(M):
    a, b = list(map(int, input().split()))
    R[a].append(b)
    R[b].append(a)

S = [False] * (N+1)
maxgrp = 1
for i in range(1, N+1):
    if S[i]: continue
    grpsize = grp(R, i, S)
#    print (grpsize)
    maxgrp = max(grpsize, maxgrp)

print(maxgrp)

Submission status: Runtime Error

Solution code:
def search(x, num):
    nodes.remove(x)
    for y in edge[x]:
        if x in edge[y]:
            edge[y].remove(x)
    for y in list(edge[x]):
        if y in nodes:
            num = search(y, num)
    return num + 1

(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x in nodes:
        ans = max(ans, search(x, 0))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

parents = [-1] * 20000

def main():

    input = sys.stdin.readline

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


    for _ in range(M):
        A,B = map(int,input().split())

        A = A - 1
        B = B - 1

        union(A,B)

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

    print(ans)

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

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

    if x == y:
        return

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

    parents[x] += parents[y]
    parents[y] = x

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

dic = dict()
dicSet = set()
dicList = dict()
count = 0

ans = 0

for i in range(m):
    a,b = list(map(int,input().split()))
    if not(a in dicSet) and not(b in dicSet):
        dic[count] = set()
        dic[count].add(a)
        dic[count].add(b)
        dicList[a] = count
        dicList[b] = count
        count += 1
        dicSet.add(a)
        dicSet.add(b)

    elif a in dicSet and b in dicSet:
        if dicList[a] != dicList[b]:
            dic[count] = dic[dicList[a]] | dic[dicList[b]]
            del dic[dicList[a]]
            del dic[dicList[b]]
            dicList[a] = count
            dicList[b] = count
            count += 1

    elif a in dicSet:
        dic[dicList[a]].add(b)
        dicList[b] = dicList[a]
        dicSet.add(b)
    else:
        dic[dicList[b]].add(a)
        dicList[a] = dicList[b]
        dicSet.add(a)


ans = 1

#print(dic)

for i in range(0,count):
    long = len(dic[i])
    if long > ans:
        ans = long

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split()))]
for _ in range(m-1):
    a, b = map(int, input().split())
    for i in ab:
        if a not in i and b in i:
            i.append(a)
            break
        elif b not in i and a in i:
            i.append(b)
            break
        elif a in i and b in i:
            break
    else:
        ab.append([a, b])
ab_m = []
for i in ab:
    ab_m.append(len(i))

print(max(ab_m))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = []
b = []
for i in range(m):
    aa, bb = input().split()
    a.append(aa)
    b.append(bb)
f1 = []
f1.append(a[0])
for i in range(m):
    if a[i] in f1:
        if not(b[i] in f1):
          f1.append(b[i])
    elif b[i] in f1:
        if not(a[i] in f1):
          f1.append(a[i])
ans = len(f1)
j = 1
while j < m:
    f2 = []
    if a[j] in f1 or b[j] in f1:
        j += 1
        continue
    if j < m:
      f2.append(a[j])
      f1.append(a[j])
      for k in range(j, m):
        if a[k] in f2:
          f2.append(b[k])
          f1.append(b[k])
        elif b[k] in f2:
          f2.append(a[k])
          f1.append(a[k])
      rans = len(f2)
      if rans > ans:
        ans = rans
    j += 1
print (ans)

Submission status: Runtime Error

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

f = []
f.append([])
nn=[]

for i in range(1,n+1):
    f[0].append(i)

for i in range(0,n+1):
    nn.append(0)


for i in range(m):
    a,b = map(int,input().split())
    if nn[a]==0 and nn[b]==0:
        f[0].remove(a)
        f[0].remove(b)
        f.append([a,b])
        nn[a]=len(f)-1
        nn[b]=len(f)-1

    elif nn[a]==0 and nn[b] !=0:
        f[nn[b]].append(a)
        nn[a] = nn[b]
        f[0].remove(a)

    elif nn[a]!=0 and nn[b] ==0:
        f[nn[a]].append(b)
        nn[b] = nn[a]
        f[0].remove(b)

    elif nn[a]!=nn[b]:
        f[nn[a]].extend(f[nn[b]])
        for j in f[nn[b]]:
            nn[j] = nn[a]
        f.remove(nn[b])


cm = 1

#print(f)
for l in f[1:]:
#    print(l)
    if cm < len(l):
        cm = len(l)



print(cm)

Submission status: Runtime Error

Solution code:

n, m = map(int, input().split())
a, b = map(int, input().split())
g = [[a, b]]
ma = 0
for i in range(0, m - 1, 1):
    a, b = map(int, input().split())
    for j in g:
        if a in j or b in j:
            j.extend([a, b])
            j = set(j)
            ma = len(j) if len(j) > ma else ma
        else:
            g.append([a, b])
print(ma)

Submission status: Runtime Error

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

f = []
f.append([])
nn=[]

for i in range(1,n+1):
    f[0].append(i)

for i in range(0,n+1):
    nn.append(0)


for i in range(m):
    a,b = map(int,input().split())
    if nn[a]==0 and nn[b]==0:
        f[0].remove(a)
        f[0].remove(b)
        f.append([a,b])
        nn[a]=len(f)-1
        nn[b]=len(f)-1

    elif nn[a]==0 and nn[b] !=0:
        f[nn[b]].append(a)
        nn[a] = nn[b]
        f[0].remove(a)

    elif nn[a]!=0 and nn[b] ==0:
        f[nn[a]].append(b)
        nn[b] = nn[a]
        f[0].remove(b)

    elif nn[a]!=nn[b]:
        f[nn[a]].extend(f[nn[b]])
        for j in f[nn[b]]:
            nn[j] = nn[a]
        f.remove(nn[b])

Submission status: Runtime Error

Solution code:
import array

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

def grp(R, i, S):
    S[i] = True
    ret = 1
    for j in range(len(R[i])):
        if S[ R[i][j] ]: continue
        ret += grp(R, R[i][j], S)
    return ret

for i in range(M):
    a, b = list(map(int, input().split()))
    R[a].append(b)
    R[b].append(a)

S = [False] * (N+1)
maxgrp = 1
for i in range(N):
    if S[i]: continue
    grpsize = grp(R, i, S)
#    print (grpsize)
    maxgrp = max(grpsize, maxgrp)

print(maxgrp)

Submission status: Runtime Error

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

f = []
f.append([])
nn=[]

for i in range(1,n+1):
    f[0].append(i)

for i in range(0,n+1):
    nn.append(0)


for i in range(m):
    a,b = map(int,input().split())
    if nn[a]==0 and nn[b]==0:
        f[0].remove(a)
        f[0].remove(b)
        f.append([a,b])
        nn[a]=len(f)-1
        nn[b]=len(f)-1

    elif nn[a]==0 and nn[b] !=0:
        f[nn[b]].append(a)
        nn[a] = nn[b]

    elif nn[a]!=0 and nn[b] ==0:
        f[nn[a]].append(b)
        nn[b] = nn[a]

    elif nn[a]!=nn[b]:
        f[nn[a]].extend(f[nn[b]])
        for j in f[nn[b]]:
            nn[j] = nn[a]
        f.remove(nn[b])


cm = 1

#print(f)
for l in f[1:]:
#    print(l)
    if cm < len(l):
        cm = len(l)



print(cm)

Submission status: Runtime Error

Solution code:
def search(x, num):
    for y in list(edge[x]):
        if y in nodes:
            nodes.remove(y)
            num = search(y, num)
    return num + 1

(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x in nodes:
        nodes.remove(x)
        ans = max(ans, search(x, 0))
print(ans)

Submission status: Runtime Error

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

groups = [1e10 for i in range(N)]
new_group = 0
for _ in range(M):
    i, j = map(int, input().split())
    i-=1
    j-=1
    if groups[i]==1e10 and groups[j]==1e10:
        groups[i] = new_group
        groups[j] = new_group
        new_group+=1
    elif groups[i]==1e10:
        group = groups[j]
        groups[i]=group
    else:
        group = groups[i]
        groups[j]=group

group_nums = [0 for _ in range(new_group)]
for g in groups:
    if g!=1e10:
        group_nums[g]+=1
print(max(group_nums))

Submission status: Runtime Error

Solution code:
class UFTree():
  def __init__(self,n):
    self.parent = {i:i for i in range(1,n+1)}
    
  def root(self,n):
    if self.parent[n]==n: return n
    else: return self.root(self.parent[n])
      
  def unite(self,x,y):
    rx,ry = self.root(x), self.root(y)
    if rx!=ry: self.parent[rx] = ry
  
  def same(self,x,y):
    return self.root(x)==self.root(y)
  
N,M = map(int,input().split())
uft = UFTree(N)
for i in range(M):
  A,B = map(int,input().split())
  uft.unite(A,B)
  
ans = {i+1:0 for i in range(N)}
for i in range(N):
  ans[uft.root(i+1)]+=1
print(max(ans.values()))

Submission status: Runtime Error

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

n, m = map(int, input().split())
edge = np.array([input().split() for _ in range(m)], dtype = np.int64).T
tmp = np.ones(m, dtype = np.int64).T
graph = csr_matrix((tmp, (edge[:] -1)), (n, n))

cnt = collections.Counter(connected_components(graph)[1])

print(max(cnt.values()))

Submission status: Runtime Error

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

import numpy as np
n, m = map(int, input().split( ))

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

for i in range(m):
    x,y=map(int,input().split(' '))
    unite(x,y)

# print(par)
print(-min(par))

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split()]
a, b = input().split()
s = {a,b}
tomodachi_list = [s] #同じグループにしてはいけないリスト

#print(tomodachi_list)
for _ in range(M-1):
    a,b = input().split()
    flag = 0
    for group in tomodachi_list:
        if a in group and b in group:
            break
        elif a in group and b not in group:
            group.add(b)
            break
        elif a not in group and b in group:
            group.add(a)
            break
        else:
            flag = 1
            pass
        if flag == 1:
            tomodachi_list.append({a, b})
        #print(tomodachi_list)
#print(tomodachi_list)
m = 0
for i in tomodachi_list:
    if m < len(i):
        m = len(i)
print(m)

Submission status: Runtime Error

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

visited = [0] * N
cnt = 0
def dfs(n):
    global cnt
    if visited[n]: return
    cnt += 1
    visited[n] = True
    for nv in edge[n]:
        dfs(nv)

ans = 0
for i in range(N):
    cnt = 0
    dfs(i)
    ans = max(ans, cnt)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import deque
n,m = map(int, input().split())

q = [0]*(n+1)

graph = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

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

d = deque()
a = 0
for l,j in enumerate(q):
    b = set()
    if j == 0:
        d.append(l)
        while d:
            v = d.popleft()
            b.add(v)
            q[i] = -1

            for i in graph[v]:
                b.add(i)
                q[i] = -1
                
                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
        a = max(a,len(b))
print(a)

Submission status: Runtime Error

Solution code:
def search(x, num):
    for y in list(edge[x]):
        if y in nodes:
            nodes.remove(y)
            edge[y].discard(x)
            num = search(y, num)
    return num + 1


(n,m),*d  = [list(map(int, s.split())) for s in open(0)]

edge = [set() for _ in range(n+1)]
for x in d:
    edge[x[0]].add(x[1])
    edge[x[1]].add(x[0])

nodes = set(range(1,n+1))
ans = 1
for x in list(nodes):
    if x not in nodes:
        continue
    nodes.remove(x)
    tmp = search(x, 0)
    ans = max(tmp, ans)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[140]:


def find(x):
    if par[x] < 0:
        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 False
    if par[x] > par[y]:
        x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

def size(x):
    return -par[find(x)]


# In[144]:


par = [-1]*N
N,M = map(int, input().split())
for _ in range(M):
    A,B = map(int, input().split())
    A -= 1; B -= 1
    unite(A,B)
ans = 0
for i in range(N):
    ans = max(ans, size(i))
print(ans)


# In[ ]:

Submission status: Runtime Error

Solution code:
import networkx as nx
n,m=map(int,input().split())
a=[[tuple(i) for i in input().split()] for _ in range(m)]
g=nx.Graph()
g.add_edges_from(a)
print(sorted([len(i) for i in nx.connected_components(g)])[-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
a = [] * m
b = [] * m
for i in range(m):
    aa, bb = input().split()
    a.append(aa)
    b.append(bb)
ans = n
f1 = []
f1.append(a[0])
for i in range(m):
    if a[i] in f1:
        f1.append(b[i])
    elif b[i] in f1:
        f1.append(a[i])
rans = len(f1)
if rans < ans:
    ans = rans
j = 1
while j < m:
    f2 = []
    if a[j] in f1 or b[j] in f1:
        j += 1
        continue
    if j < m:
      f2.append(a[j])
      f1.append(a[j])
      for k in range(j, m):
        if a[k] in f2:
          f2.append(b[k])
          f1.append(b[k])
        elif b[k] in f2:
          f2.append(a[k])
          f1.append(a[k])
      rans = len(f2)
      if rans > ans:
        ans = rans
    j += 1
print (ans)

Submission status: Runtime Error

Solution code:

N,M=map(int, input().split())
l=[[]for j in range(N)]
field=[True]*N
for i in range(M):
    a,b=map(int,input().split())
    l[min(a,b)-1].append(max(a,b)-1)

def dfs(x):
    conn=1
    field[x]=False
    for j in range(len(l[x])):
        if field[l[x][j]]:
            conn+=dfs(l[x][j])
    return conn

nax=0
for i in range(N):
    temp=dfs(i)
    nax=max(nax,temp)

print(nax)