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:
def dfs(visited, graph, node):
    if node not in visited:
        visited[node]=1
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

def insert_adj_list(graph,f,t):

    if (t not in graph[f]):
        graph[f].append(t)

    if (f not in graph[t]):
        graph[t].append(f)

def init_dict(dict,n):
    for i in range(1,n+1):
        dict[i]=[]

def rem_item(graph, n):
    if n in graph:
        del graph[n]

def gen_dict(p,n):
    dict={}
    for i in range(0,n):
        dict[p[i]]=i

    return dict

t=1
# t= int(input())

for some_num in range(0,t):
    n,m=[int(i) for i in input().split(" ")]
    graph={}
    init_dict(graph, n)
    for j in range(0,m):
        f, t = [int(i) for i in input().split(" ")]
        insert_adj_list(graph,f,t)

    p = [int(i) for i in range(1,n+1)]

    vc=[0 for i in range(0,n)]
    count=0
    dsets=[]
    for i in range(0,n):
        if(vc[i]==0):
            count+=1
            visited={}
            dfs(visited,graph,p[i])
            # print(visited)
            for k in visited:
                vc[k-1]=1
            dsets.append(visited)
        else:
            pass
    max_len=0
    for i in range(0,len(dsets)):
        max_len=max(max_len,len(dsets[i]))

    print(max_len)

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())
par=[i for i in range(N+1)]
def find(x):
    if par[x] ==x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x]=y
for i in range(Q):
    a,b=map(int,input().split())
    unite(a,b)
ans=dict()
for i in par:
    tmp=find(i)
    if tmp in ans:
        ans[tmp]+=1
    else:
        ans[tmp]=1
print(max(ans.values()))

Submission status: Runtime Error

Solution code:
"""
https://atcoder.jp/contests/abc177/tasks/abc177_d
"""


def solve(n, m, a):
    grp = []

    for f in a:
        if len(grp) == 0:
            grp.append(set(f))

        else:

            u = False
            for gi, g in enumerate(grp):

                if f[0] in g or f[1] in g:
                    grp[gi] = g.union(set(f))
                    u = True

            if not u:
                grp.append(set(f))

    ugrp = [grp[0]]
    for i in range(1, len(grp)):
        u = False
        for gi, g in enumerate(ugrp):
            if not grp[i].isdisjoint(g):
                ugrp[gi] = g.union(grp[i])
                u = True
        if not u:
            ugrp.append(grp[i])

    ml = 0
    for g in ugrp:
        if len(g) > ml:
            ml = len(g)

    return ml

# solve(10, 4, [[3, 1], [4, 1], [5, 9], [2, 6]])

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

print(solve(n, m, a))

Submission status: Runtime Error

Solution code:
class disjoint:
    def __init__(self, x: int):
        self.a = [-1] * x

    def root(self, x: int):
        if self.a[x] < 0:
            return x
        self.a[x] = self.root(self.a[x])
        return self.a[x]

    def unite(self, x: int, y: int):
        x, y = self.root(x), self.root(y)
        if x == y:
            return
        if x < y:
            x, y = y, x
        self.a[x] += self.a[y]
        self.a[y] = x

    def size(self, x: int):
        if self.a[x] < 0:
            return -self.a[x]
        return self.size(self.a[x])


n, m = [int(i) for i in input().split()]
solution = disjoint(n)
for _ in range(m):
    a, b = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    solution.unite(a, b)

ans = 1
for i in range(n):
    ans = max(ans, solution.size(i))

print(int(ans))

Submission status: Runtime Error

Solution code:
from statistics import mode

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

rels = [i for i in range(n + 1)]
inf = []
count = [0] * n

for i in range(m):
    rel = list(map(int, input().split()))
    rel = sorted(rel)
    inf.append(rel)

inf = sorted(inf)

for rel in inf:
    a = rel[0] - 1
    b = rel[1] - 1
    rels[b] = rels[a]

for rel in rels:
    count[rel] = count[rel] + 1

res = rels.count(mode(rels))

while res < sum(count) - res:
    res = res + 1

print(res)

Submission status: Runtime Error

Solution code:
from statistics import mode

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

rels = [i for i in range(n)]
#count = [0] * n
#print(count)

for i in range(m):
    rel = list(map(int, input().split()))
    rel = sorted(rel)
    a = rel[0] - 1
    b = rel[1] - 1
    rels[b] = rels[a]
    count[a] = count[a] + 1
    #print(count)
    
print(mode(rels))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
import collections

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            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

        self.parents[y] = x


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

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

hoge = [uf.find(i) for i in range(N)]

#print(hoge)
hogehoge = collections.Counter(hoge).most_common()

print(hogehoge[0][1])

Submission status: Runtime Error

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

class UnionFind:
    par = []
    def __init__(self, n):
        for i in range(n):
            self.par.append(i)

    def root(self, x):
        if self.par[x] == x:
            return x
        return self.root(self.par[x])

    def unite(self, x, y):
        if x > y:
            x, y = y, x
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[ry] = rx

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    def return_par(self):
        return self.par

uf = UnionFind(n)
for a, b in ab:
    uf.unite(a-1, b-1)
par = uf.return_par()
d = dict()
for p in par:
    if p not in d.keys():
        d[p] = 1
    else:
        d[p] += 1
print(max(d.values()))

Submission status: Runtime Error

Solution code:
class disjoint:
    def __init__(self, x: int):
        self.a = [-1 for i in range(x)]

    def root(self, x: int):
        if self.a[x] < 0:
            return x
        self.a[x] = self.root(self.a[x])
        return self.a[x]

    def unite(self, x: int, y: int):
        x, y = self.root(x), self.root(y)
        if x == y:
            return
        if x < y:
            x, y = y, x
        self.a[x] += self.a[y]
        self.a[y] = x

    def size(self, x: int):
        if self.a[x] < 0:
            return -self.a[x]
        return self.size(self.a[x])

n, m = [int(i) for i in input().split()]
solution = disjoint(n)
for _ in range(m):
    a, b = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    solution.unite(a, b)

ans = 1
for i in range(n):
    ans = max(ans, solution.size(i))

print(int(ans))

Submission status: Runtime Error

Solution code:
from networkx import*;_,*n=map(str.split,open(0));print(max(map(len,[*connected_components(Graph(n))]),1,1))

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
graph = [[] for i in range(n)]

for _ in range(m):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

vis = [False] * n

def dfs(x):
    vis[x] = False
    count = 1
    for i in graph[x]:
        if not vis[i]:
            count += dfs(i)
    return count


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

print(int(ans))

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
graph = [[] for i in range(n)]

for _ in range(m):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

vis = [False] * n


def dfs(x: int):
    count = 1
    for i in graph[x]:
        if not vis[i]:
            vis[i] = True
            count += dfs(i)
    return count


ans = 1
for i in range(n):
    if not vis[i]:
        vis[i] = True
        ans = max(ans, dfs(i))

print(int(ans))

Submission status: Runtime Error

Solution code:
n, m = [int(i) for i in input().split()]
graph = [[] for i in range(n)]

for _ in range(m):
    x, y = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

vis = [False] * n

def dfs(x):
    count = 1
    for i in graph[x]:
        if vis[i] == False:
            vis[i] = True
            count += dfs(i)
    return count

ans = 1
for i in range(n):
    if vis[i] == False:
        vis[i] = True
        ans = max(ans, dfs(i))

print(int(ans))

Submission status: Runtime Error

Solution code:
from collections import Counter

n,m = map(int,input().split())
ab = list(list(map(int,input().split())) for _ in range(m))
a,b = [list(i) for i in zip(*ab)]

group = [-1]*(n+1)
group_name = 0

for i in range(m):
  if group[a[i]] == -1 and group[b[i]] == -1:
    group[a[i]] = group_name
    group[b[i]] = group_name
    group_name += 1
  elif group[a[i]] == -1 and group[b[i]] != -1:
    group[a[i]] = group[b[i]]
  elif group[a[i]] != -1 and group[b[i]] == -1:
    group[b[i]] = group[a[i]]
  else:
    if group[a[i]] != group[b[i]]:
      for j,k in enumerate(group):
        if k == group[b[i]]:
          group[j] = group[a[i]]

d = Counter(group).most_common()[0][1]
if Counter(group).most_common()[0][0] == -1:
  d = Counter(group).most_common()[1][1]
print(d)

Submission status: Runtime Error

Solution code:
#n = int(input())
import random
n, m = map(int, input().split())
#al = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]
adjl = [[] for _ in range(n+1)]
NIL = -1
appear = {}
isalone = {}
for i in range(m):
    a, b = map(int, input().split())
    if appear.get((a, b), False) or appear.get((a, b), False):
        continue
    appear[(a, b)] = True
    appear[(b, a)] = True
    isalone[a] = False
    isalone[b] = False
    adjl[a].append(b)
    adjl[b].append(a)

color = [NIL for i in range(n+1)]
color_id = 0


def dfs(u, color_id):
    global color
    color[u] = color_id
    for v in adjl[u]:
        if color[v] == NIL:  # 未到達なら再起呼び出し
            color[v] = color_id
            dfs(v, color_id)


for u in range(1, n+1):
    if color[u] == NIL:
        color_id += 1
        dfs(u, color_id)

group = {}
for i in range(1, n+1):
    if isalone.get(i, True):
        continue
    group[color[i]] = group.get(color[i], 0)+1

mx = 1
for k, v in group.items():
    mx = max(mx, v)
print(mx)

Submission status: Runtime Error

Solution code:
from collections import Counter

n,m = map(int,input().split())
ab = list(list(map(int,input().split())) for _ in range(m))
a,b = [list(i) for i in zip(*ab)]

group = [-1]*(n+1)
group_name = 0

for i in range(m):
  if group[a[i]] == -1 and group[b[i]] == -1:
    group[a[i]] = group_name
    group[b[i]] = group_name
    group_name += 1
  elif group[a[i]] == -1 and group[b[i]] != -1:
    group[a[i]] = group[b[i]]
  elif group[a[i]] != -1 and group[b[i]] == -1:
    group[b[i]] = group[a[i]]
  else:
    if group[a[i]] != group[b[i]]:
      group.replace(max(group[a[i]],group[b[i]]),min(group[a[i]],group[b[i]]))

d = Counter(group).most_common()[0][1]
if Counter(group).most_common()[0][0] == -1:
  d = Counter(group).most_common()[1][1]
print(d)

Submission status: Runtime Error

Solution code:
from networkx import*
_,*n=map(str.split,open(0))
print(len(max([*connected_components(Graph(n))],key=len)))

Submission status: Runtime Error

Solution code:
from networkx import*;_,*n=map(str.split,open(0));print(max(map(len,[*connected_components(Graph(n))])))

Submission status: Runtime Error

Solution code:
#n = int(input())
n, m = map(int, input().split())
#al = list(map(int, input().split()))
#l = [list(map(int,input().split())) for i in range(n)]

fgroup = {i: 0 for i in range(1, n+1)}
g_id = 0
for i in range(m):
    a, b = map(int, input().split())
    if fgroup[a] != 0:
        fgroup[b] = fgroup[a]
    elif fgroup[b] != 0:
        fgroup[a] = fgroup[b]
    else:
        g_id += 1
        fgroup[a] = g_id
        fgroup[b] = g_id

gid_num = {}
for person, gid in fgroup.items():
    gid_num[gid] = gid_num.get(gid, 0)+1
mx = 1
for i in range(1, g_id+1):
    mx = max(mx, gid_num[i])
print(mx)

Submission status: Runtime Error

Solution code:
from collections import Counter

class UnionFind:
    def __init__(self,num:int):
        self.r = [-1 for i in range(num)]
    def root(self,x:int):
        if(self.r[x] < 0):
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    def unite(self,x:int,y:int):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return False
        if(self.r[x] > self.r[y]):
            x,y = y,x
        self.r[x] += self.r[y]
        self.r[y] = x
        return True
    def size(self,x:int):
        return -self.r[self.root(x)]

N,M = map(int,input().split())
group = UnionFind(N)
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    group.unite(A-1,B-1)
ans = 0
for i in range(N):
    ans = max(ans,group.size(i))
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

class Graph:
    def __init__(self,n,side):
        self.side = side
        self.neighbor = [set() for i in range(n+1)]
        self.visited = [False]*(n+1)
        self.group =[0]*n
        self.product()
    def product(self):
        for a,b in self.side:
            self.neighbor[a].add(b)
            self.neighbor[b].add(a)
    def dfs(self,x,a):
        self.group[a] += 1
        self.visited[x] = True
        for i in self.neighbor[x]:
            if self.visited[i]:continue
            self.dfs(i,a)
    def all_dfs(self):
        a = 0
        for i in range(1,n+1):
            if not self.visited[i]:
                self.dfs(i,a)
                a += 1

n,m = map(int,input().split())
side = list(tuple(map(int,input().split()))for i in range(m))
graph1 = Graph(n,side)
graph1.all_dfs()
print(max(graph1.group))

Submission status: Runtime Error

Solution code:
sys.setrecursionlimit(10000)

class Graph:
    def __init__(self,n,side):
        self.side = side
        self.neighbor = [set() for i in range(n+1)]
        self.visited = [False]*(n+1)
        self.group =[0]*n
        self.product()
    def product(self):
        for a,b in self.side:
            self.neighbor[a].add(b)
            self.neighbor[b].add(a)
    def dfs(self,x,a):
        self.group[a] += 1
        self.visited[x] = True
        for i in self.neighbor[x]:
            if self.visited[i]:continue
            self.dfs(i,a)
    def all_dfs(self):
        a = 0
        for i in range(1,n+1):
            if not self.visited[i]:
                self.dfs(i,a)
                a += 1

n,m = map(int,input().split())
side = list(tuple(map(int,input().split()))for i in range(m))
graph1 = Graph(n,side)
graph1.all_dfs()
print((graph1.group))

Submission status: Runtime Error

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

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

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

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

        if x == y:
            return

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

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

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

    def 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 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())
      
uni = UnionFind(N)
for i in range(M):
  uni.union(List[i][0],List[i][1])
res = 0
for i in range(N):
  res = max(res,uni.size(i))
print(res)

Submission status: Runtime Error

Solution code:
class Graph:
    def __init__(self,n,side):
        self.side = side
        self.neighbor = [set() for i in range(n+1)]
        self.visited = [False]*(n+1)
        self.product()
        self.group =[0]*n
    def product(self):
        for a,b in self.side:
            self.neighbor[a].add(b)
            self.neighbor[b].add(a)
    def dfs(self,x,a):
        self.group[a] += 1
        self.visited[x] = True
        for i in self.neighbor[x]:
            if self.visited[i]:continue
            self.dfs(i,a)
    def all_dfs(self):
        a = 0
        for i in range(1,n+1):
            if not self.visited[i]:
                self.dfs(i,a)
                a += 1

n,m = map(int,input().split())
side = list(tuple(map(int,input().split()))for i in range(m))
graph1 = Graph(n,side)
graph1.all_dfs()
print(max(graph1.group))

Submission status: Runtime Error

Solution code:
class Graph:
    def __init__(self,n,m,side):
        self.side = side
        self.neighbor = [set() for i in range(n+1)]
        self.visited = [False]*(n+1)
        self.product()
        self.group =[0]*(n+1)
    def product(self):
        for a,b in self.side:
            self.neighbor[a].add(b)
            self.neighbor[b].add(a)
    def dfs(self,x,a):
        self.group[a] += 1
        self.visited[x] = True
        for i in self.neighbor[x]:
            if self.visited[i]:continue
            self.dfs(i,a)
    def all_dfs(self):
        a = 0
        for i in range(1,n+1):
            if not self.visited[i]:
                self.dfs(i,a)
                a += 1

n,m = map(int,input().split())
side = list(tuple(map(int,input().split()))for i in range(m))
graph1 = Graph(n,m,side)
graph1.all_dfs()
print(max(graph1.group))

Submission status: Runtime Error

Solution code:
class UnionFindTree():
    def __init__(self, num_leaves):
        #self.num_leaves = num_leaves
        self.root = [i for i in range(num_leaves+1)]
        
    def find(self, leaf):
        if self.root[leaf] == leaf:
            return self.root[leaf]
        else:
            self.root[leaf] = self.find(self.root[leaf])
            return self.root[leaf]
        
    def union(self, leaf_a, leaf_b):
      	# find roots
        root_a = self.find(leaf_a)
        root_b = self.find(leaf_b)
        if root_a != root_b:
            # then union roots
            self.root[leaf_b] = root_a
            
        
N, M = map(int, input().split())
uft = UnionFindTree(N)
for m in range(M):
  a, b = map(int, input().split())
  uft.union(a, b)
  
# 経路圧縮
for n in range(N):
  uft.find(n)
  
max_size = [uft.root.count(n) for n in range(N)].max()
print(num_group)

Submission status: Runtime Error

Solution code:
from collections import Counter

class UnionFind:
    def __init__(self,num:int):
        self.parents = [i for i in range(num)]
    def root(self,x:int):
        if(self.parents[x] == x):
            return x
        return self.root(self.parents[x])
    def unite(self,x:int,y:int):
        rx = self.root(x)
        ry = self.root(y)
        if(rx == ry):
            return
        self.parents[rx] = ry
    def same(self,x:int,y:int):
        rx = root(x)
        ry = root(y)
        return rx == ry

N,M = map(int,input().split())
group = UnionFind(N)
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    group.unite(A-1,B-1)
a = [group.root(i) for i in range(N)]
ans = Counter(a)
print(ans.most_common()[0][1])

Submission status: Runtime Error

Solution code:
N, M = [int(k) for k in input().split()]
nodes = {k:set() for k in range(1,N+1)}
visited = [False for i in range(N+2)]

for i in range(M):
  a, b = [int(k) for k in input().split()]
  nodes[a].add(b)
  nodes[b].add(a)
  
def dfs(i):
  visited[i] = True
  cnt = 1
  for j in nodes[i]:
    if not visited[j]:
      cnt += dfs(j)
      
  return cnt
  
   
ans = 1
if M > 0:
  for z in nodes:
    if not visited[z]:
      m = dfs(z)
      ans = max(m,ans)

print(ans)

Submission status: Runtime Error

Solution code:
# データ構造: Union Find (素集合データ構造)
#  前提
#    グラフ（頂点と辺からなる集合）上の各頂点が、どの連結成分に属しているかを管理するときに使う
#    具体的には、各連結成分ごとに適当な1点を親として、同じ連結成分に属する他の点が子になるように配置する
#  できること
#    1, ある頂点の親を返す (つまり、どの連結成分に属するかがわかる)
#    2, 新たな辺が与えられた時、必要なら連結成分の統合を行う

# 以下、事前準備。(本処理は42行目から)
# 上記1,2を実現する関数を作成する。

# 0, 前提
par = [-1]*n
#  配列parの要素par[i]には、
#    頂点iが子の場合に 親頂点の番号
#    頂点iが親の場合に 属する連結成分の頂点数を格納する。(区別のため負数として表記)
#  例: par = [2, 2, -3, -1, 5, -1]
#    点0,1,2からなる連結成分、点3からなる連結成分、点4,5からなる連結成分がある場合。

# 1, 頂点xの親を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
      
# 2, 頂点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

# 以下、本処理
# 求めるもの：各連結成分の頂点数のうち、最大のもの
n, m = map(int,input().split())
#初期化
#根なら-size,子なら親の頂点
par = [-1 for _ in range(n)]
 
for _ in range(m): #各辺について
  a, b = map(int,input().split())
  a -= 1
  b -= 1
  unite(a,b) #辺の両端(頂点aとb)が統合される
  
print(-min(par))
# 各連結成分の頂点数は、配列parの中に負数として記録されている。
# 連結成分の最大の頂点数を求めたければ、そのminをとって-1倍すればよい。

Submission status: Runtime Error

Solution code:
N, M = [int(k) for k in input().split()]
nodes = {k:set() for k in range(1,N+1)}
visited = [False for i in range(N+1)]

for i in range(M):
  a, b = [int(k) for k in input().split()]
  nodes[a].add(b)
  nodes[b].add(a)
  
def dfs(i):
  visited[i] = True
  cnt = 1
  for j in nodes[i]:
    if not visited[j]:
      cnt += dfs(j)
      
  return cnt
  
   
ans = 1
if M > 0:
  for i in nodes:
    if not visited[i]:
      ans = max(dfs(i),ans)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
N=int(input())
A=list(map(int,input().split()))


def sieve_of_eratosthenes(n): #エラトステネスのふるい
    candidate = list(range(2, n+1)) #候補
    prime = []
    limit = n**0.5 + 1 #+1がないと平方数を素数にしてしまう

    while True:
        p = candidate[0] 
        if limit <= p:
            prime.extend(candidate) #この時点での残っているのは素数
            break
        prime.append(p) #pを素数リストに登録

        candidate = [i for i in candidate if i % p != 0]

        # i = 0
        # while True:
            # if i >= len(candidate): #iはcandidateの長さ分
                # break
            # elif candidate[i] % p == 0: #余りがゼロなら
                # candidate.pop(i) #素数ではないのでpop(取り除く)する
            # i += 1

    return prime



maxA=max(A)

prime = sieve_of_eratosthenes(maxA)

X=[0]*(maxA+1)
for i in range(N):
    X[A[i]]+=1

check=0
for i in prime:
    count=0
    for j in range(1,int(maxA/i)+1):
        count+=X[j*i]
    if count==N:
        print('not coprime')
        sys.exit()
    elif count>1:
        check=1
        
if check==1:
    print('setwise coprime')
else:
    print('pairwise coprime')

Submission status: Runtime Error

Solution code:
N, M = [int(k) for k in input().split()]
nodes = {k:[] for k in range(1,N+1)}
visited = [False for i in range(N+1)]

for i in range(M):
  a, b = [int(k) for k in input().split()]
  nodes[a].append(b)
  nodes[b].append(a)
  
def dfs(i):
  visited[i] = True
  cnt = 1
  for j in nodes[i]:
    if not visited[j]:
      cnt += dfs(j)
      
  return cnt
   
ans = 0
for z in nodes:
  if not visited[z]:
    ans = max(dfs(z),ans)

print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(k) for k in input().split()]
nodes = {k:set() for k in range(1,N+1)}
visited = [False for i in range(N+1)]

for i in range(M):
  a, b = [int(k) for k in input().split()]
  nodes[a].add(b)
  nodes[b].add(a)
  
def dfs(i):
  visited[i] = True
  cnt = 1
  for j in nodes[i]:
    if not visited[j]:
      cnt += dfs(j)
      
  return cnt
   
ans = 0
for z in nodes:
  if not visited[z]:
    ans = max(dfs(i),ans)

print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(k) for k in input().split()]
nodes = {k:set() for k in range(1,N+1)}
visited = [False for i in range(N+1)]

for i in range(M):
  a, b = [int(k) for k in input().split()]
  nodes[a].add(b)
  nodes[b].add(a)
  
def dfs(i):
  visited[i] = True
  cnt = 1
  for j in nodes[i]:
    if not visited[j]:
      cnt += dfs(j)
      
  return cnt
  

   
ans = -1
if M == 0:
  ans = N
else:
  for i in nodes:
    if not visited[i]:
      ans = max(dfs(i),ans)

print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(a) for a in input().split()]
lol = []
for i in range(M):
  a, b = [int(a) for a in input().split()]
  found_a = -10
  found_b = -10
  for j in range(len(lol)):
    if a in lol[j]:
      found_a = j
    if b in lol[j]:
      found_b = j
    if found_a >= 0 and found_b >= 0:
      break
  
  if found_a < 0 and found_b < 0:
    lol.append(set([a,b]))
  elif found_a >= 0 and found_b < 0:
    lol[found_a].add(b)
  elif found_b >= 0 and found_a < 0:
    lol[found_b].add(a)
  elif found_a >= 0 and found_b >=0 and found_a != found_b:
    lol[found_a] += lol[found_b]
    lol.pop(found_b)
    
ans = -1
for z in lol:
  if len(z) > ans:
    ans = len(z)

print(ans)

Submission status: Runtime Error

Solution code:
from networkx import *
n,m = map(int, input().split())
G = Graph()
for i in range(m):
    a,b = map(int, input().split())
    G.add_edges_from([(a,b)])

print(len(max(connected_components(G))))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.r = [-1 for i in range(n)]
    
    def root(self, x):
        if self.r[x] < 0:
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] < self.r[y]:
            temp = x
            x = y
            y = temp
        self.r[x] += self.r[y]
        self.r[y] = x
        return True
    
    def size(self, x):
        return -self.r[self.root(x)]

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

ans = 0
for i in range(n):
    ans = max(ans, UF.size(i))

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.r = [-1 for i in range(n)]
    
    def root(self, x):
        if self.r[x] < 0:
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] < self.r[y]:
            temp = x
            x = y
            y = temp
        self.r[x] += self.r[y]
        self.r[y] = x
        return True
    
    def size(self, x):
        return -self.r[self.root(x)]

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

ans = 0
for i in range(n):
    ans = max(ans, UF.size(i))

print(UF.r)
print(ans)

Submission status: Runtime Error

Solution code:
import sys,heapq
input = sys.stdin.buffer.readline


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

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

#True:訪問済み False:未訪問
flag = [False]*n

def dfs(now):
    if flag[now]:
        return 0
    
    flag[now] = True

    size = 0
    for nxt in edge[now]:
        if not flag[nxt]:
            size += dfs(nxt)

    return size + 1

res = 0

for i in range(n):
    if flag[i]:
        continue
    res = max(res,dfs(i))

print(res)

Submission status: Runtime Error

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


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)
    return


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

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

print(max(ans))

Submission status: Runtime Error

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


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)
    return


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].add(b)
    friends[b].add(a)

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

print(max(ans))

Submission status: Runtime Error

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


def dfs(i):
    ans[-1] += 1
    flg[i] = 1
    for j in friends[i]:
        if not flg[j]:
            dfs(j)


for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    friends[a].add(b)
    friends[b].add(a)

flg = [0]*n
ans = []

for i in range(n):
    ans.append(0)
    if not flg[i]:
        dfs(i)

print(max(ans))

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

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

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


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)

ans=0

for i in range(N):
    ans = max(ans, UF.size(i))
 
 print(ans)