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:
class Node():
    def __init__(self,index):
        self.index = index
        self.parent = self 

    @staticmethod
    def find_set(node):
        if node.parent == node:
            return node 
        root = Node.find_set(node.parent)
        node.parent = root
        return root

    @staticmethod
    def union(node_a,node_b):
        root_a = Node.find_set(node_a)
        root_b = Node.find_set(node_b)
        if root_a != root_b:
            root_a.parent = root_b



if __name__ == "__main__":
    n,m = [int(val) for val in input().split()]
    
    persons = []
    count = []
    for i in range(n):
        persons.append(Node(i))
        count.append(0)
    
    for i in range(m):
        a,b = [int(val) for val in input().split()]
        if a > b:
            Node.union(persons[a-1],persons[b-1])
        else:
            Node.union(persons[b-1],persons[a-1])


    for idx,person in enumerate(persons):
        count[Node.find_set(person).index] += 1
    
    # print(count)
    result = max(count)
    print(result)

Submission status: Runtime Error

Solution code:
class UnionTree:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
    def get_root(self,m):
        if self.parent[m] == m:
            return m
        else:
            self.parent[m] = self.get_root(self.parent[m])
            return self.parent[m]
    def have_same_root(self,n,m):
        if self.get_root[n] == self.get_root[m]:
            return True
        else:
            return False
    def unite(self,n,m):
        root_n = self.get_root(n)
        root_m = self.get_root(m)
        if root_n != root_m:
            self.parent[root_n] = root_m
N, M = map(int, input().split())
ut = UnionTree(N)
for _ in range(M):
    a, b = map(int, input().split())
    ut.unite(a-1, b-1)
child_num = [0]*N
for num in range(N):
    temp = ut.get_root(num)
    child_num[temp] += 1
if M == 0:
  print(0)
else:
  print(max(child_num))

Submission status: Runtime Error

Solution code:
class UnionTree:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
    def get_root(self,m):
        if self.parent[m] == m:
            return m
        else:
            self.parent[m] = self.get_root(self.parent[m])
            return self.parent[m]
    def have_same_root(self,n,m):
        if self.get_root[n] == self.get_root[m]:
            return True
        else:
            return False
    def unite(self,n,m):
        root_n = self.get_root(n)
        root_m = self.get_root(m)
        if root_n != root_m:
            self.parent[root_n] = root_m
N, M = map(int, input().split())
ut = UnionTree(N)
for _ in range(M):
    a, b = map(int, input().split())
    ut.unite(a-1, b-1)
child_num = [0]*N
for num in range(N):
    temp = ut.get_root(num)
    child_num[temp] += 1
print(max(child_num))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

N, M = map(int, input().split())
root = [-1] * N

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


def union(x, y):
    x_parent = parent(x)
    y_parent = parent(y)
    if x_parent == y_parent:
        return
    root[x_parent] += root[y_parent]
    root[y_parent] = x


def size(x):
    return -root[x]
    

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


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

print(max_size)

Submission status: Runtime Error

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

par = [-1 for n in range(N)]

def root(a):
  if par[a - 1] < 0:
    return a
  return root(par[a - 1])

def same(a, b):
  if root(a) == root(b):
    return True
  else:
    return False
  
def unite(a, b):
  if not same(a, b):
    a = root(a)
    b = root(b)
    par[a - 1] += par[b - 1]
    par[b - 1] = root(a)
    

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

print(-min(par))

Submission status: Runtime Error

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

l = [set(map(int, input().split()))]
max_cnt = 0
for _ in range(M-1):
  flg = False
  t = set(map(int, input().split()))

  for i in range(len(l)):
    s = l[i]
    if t & s:
      l[i] = t | s
      flg = True
      max_cnt = max(max_cnt, len(l[i]))
      break

  if not flg:
    l.append(t)

print(max_cnt)

Submission status: Runtime Error

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

par = [-1 for n in range(N)]

def root(a):
  if par[a - 1] < 0:
    return a
  return root(par[a - 1])

def same(a, b):
  if root(a) == root(b):
    return True
  else:
    return False
  
def unite(a, b):
  if not same(a, b):
    a = root(a)
    b = root(b)
    par[a - 1] += par[b - 1]
    par[b - 1] = root(a)
    

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

print(-min(par))

Submission status: Runtime Error

Solution code:
class Node():
    def __init__(self,index):
        self.index = index
        self.parent = self 

    @staticmethod
    def find_set(node):
        if node.parent == node:
            return node 
        return Node.find_set(node.parent)

    @staticmethod
    def union(node_a,node_b):
        root_a = Node.find_set(node_a)
        root_b = Node.find_set(node_b)
        if root_a != root_b:
            node_a.parent = root_b



if __name__ == "__main__":
    n,m = [int(val) for val in input().split()]
    
    persons = []
    count = []
    for i in range(n):
        persons.append(Node(i))
        count.append(0)
    
    for i in range(m):
        a,b = [int(val) for val in input().split()]
        if a > b:
            Node.union(persons[a-1],persons[b-1])
        else:
            Node.union(persons[b-1],persons[a-1])


    for idx,person in enumerate(persons):
        count[Node.find_set(person).index] += 1
    
    # print(count)
    result = max(count)
    print(result)

Submission status: Runtime Error

Solution code:
N, M=map(int, input().split())
AB= [map(int, input().split()) for _ in range(M)]
A, B = [list(i) for i in zip(*AB)]

G=[0]*(N+1)
sw=1
for i in range(M):
    if G[A[i]]+G[B[i]]==0:
        G[A[i]]=sw
        G[B[i]]=sw
        sw+=1
    if G[A[i]]!=0:
        G[B[i]]=G[A[i]]
    else:
        G[A[i]]=G[B[i]]
G=G[1:]
import collections
c=collections.Counter(G)
print(c.most_common()[0][1])

Submission status: Runtime Error

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

par = [-1 for n in range(N)]

def root(a):
  if par[a - 1] < 0:
    return a
  return root(par[a - 1])

def same(a, b):
  if root(a) == root(b):
    return True
  else:
    return False
  
def unite(a, b):
  if not same(a, b):
    par[root(a) - 1] += par[root(b) - 1]
    par[root(b) - 1] = root(a)
    

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

print(-min(par))

Submission status: Runtime Error

Solution code:

N, M=map(int, input().split())
AB= [map(int, input().split()) for _ in range(M)]
A, B = [list(i) for i in zip(*AB)]
G=[[A[0],B[0]]]

for i in range(1,M):
    count=0
    for j in range(len(G)):
        if A[i] in G[j]:
            if B[i] not in G[j]:
                G[j].append(B[i])
                count=1
        elif B[i] in G[j]:
            if A[i] not in G[j]:
                G[j].append(A[i])
                count=1
    if count==0:
        G.append([A[i],B[i]])
print(max([len(v) for v in G]))

Submission status: Runtime Error

Solution code:
def main(N, M, C):
    lst = []
    for c in C:
        for l in lst:
            if c[0] in l:
                l.add(c[1])
                break
            elif c[1] in l:
                l.add(c[0])
                break
        else:
            lst.append(set(c))
    # print(lst)
    print(max({len(l) for l in lst}))


if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    C = set()
    for _ in range(M):
        C.add(tuple(map(int, input().split())))
    main(N, M, C)

Submission status: Runtime Error

Solution code:
# Union find
# かっつぱさんの解説と公式のスライドみた
# https://www.youtube.com/watch?time_continue=916&v=zxor0DdwoXA&feature=emb_logo
# https://www.slideshare.net/chokudai/union-find-49066733

import sys
sys.setrecursionlimit(10 ** 9)

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

root = [-1]*n

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

def unite(x, y):
    gx = find(x)
    gy = find(y)
    
    if gx == gy:
        return
      
    if root[gx] > root[gy]:
        gx, gy = gy, gx
        
    root[gx] += root[gy]
    root[gy] = gx
    print(root)

def size(x):
    x = find(x)
    return -root[x]

for a, b in AB:
    a -= 1
    b -= 1
    unite(a, b)

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

Submission status: Runtime Error

Solution code:
from collections import *
n,m = map(int,input().split())
par = [-1 for _ in range(n)]#par<0なら自身が親で要素の個数、>0なら子で親の位置示す

def root(i):
    if par[i] < 0:
        return i
    else:
        return root(par[i])

def size(a):
    return -par[root(a)]

def union(a,b):
    a = root(a)
    b = root(b)
    if a == b:#親が等しい
        return False
    if size(a) < size(b):#サイズが大きい方に繋げる
        a,b = b,a
    par[a] += par[b]
    par[b] = a
    return True

for i in range(m):
    a = [int(j)-1 for j in input().split()]#数字を一つ減らして足を揃える
    if root(a[0]) != root(a[1]):
        union(a[0],a[1])
par = [ i for i in par if i >= 0]
print(Counter(par).most_common()[0][1]+1)

Submission status: Runtime Error

Solution code:
# union-find
# https://note.nkmk.me/python-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 x > y:
        if self.parents[x] > self.parents[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            return
        self.parents[y] += self.parents[x]   
        self.parents[x] = y
        return
    
    def size(self, x):
        x = self.find(x)    
        return self.parents[x]*(-1)

def main():
    n, m = map(int, input().split())
    friend = UnionFind(n)

    for _ in range(m):
        a, b = map(int, input().split())
        friend.union(a-1, b-1)
    
    ans = 0
    for i in range(n):
        ans = max(ans, friend.size(i))
    print(ans)

if  __name__ == "__main__":
     main()

Submission status: Runtime Error

Solution code:
from collections import *
n,m = map(int,input().split())
par = [-1 for _ in range(n)]#par<0なら自身が親で要素の個数、>0なら子で親の位置示す

def root(i):
    if par[i] < 0:
        return i
    else:
        return root(par[i])

def size(a):
    return -par[root(a)]

def union(a,b):
    a = root(a)
    b = root(b)
    if a == b:#親が等しい
        return False
    if size(a) < size(b):#サイズが大きい方に繋げる
        a,b = b,a
    par[a] += par[b]
    par[b] = a
    return True

for i in range(m):
    a = [int(j)-1 for j in input().split()]#数字を一つ減らして足を揃える
    if root(a[0]) != root(a[1]):
        union(a[0],a[1])
par = [ i for i in par if i > 0]
print(Counter(par).most_common()[0][1]+1)

Submission status: Runtime Error

Solution code:
# union-find
# https://note.nkmk.me/python-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 x > y:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            return
        self.parents[y] += self.parents[x]   
        self.parents[x] = y
        return
    
    def size(self, x):
        x = self.find(x)    
        return self.parents[x]*(-1)

def main():
    n, m = map(int, input().split())
    friend = UnionFind(n)

    for _ in range(m):
        a, b = map(int, input().split())
        friend.union(a-1, b-1)
    
    ans = 0
    for i in range(n):
        ans = max(ans, friend.size(i))
    print(ans)

if  __name__ == "__main__":
     main()

Submission status: Runtime Error

Solution code:
ans = 1
n, m = map(int, input().split())
d = dict()
vis = set()
def dfs(key, size):
    global ans
    for friend in d[key]:
        if friend not in vis:
            size+=1
            vis.add(friend)
            ans = max(ans, size)
            # print("key", friend,"ans",  ans,"s", size)
            dfs(friend, size)
rep = set()
for _ in range(m):
    a, b = map(int, input().split())
    if (a, b) in rep or (b, a) in rep:
        continue
    rep.add((a, b))
    if a in d:
        d[a].append(b)
    else:
        d[a] = []
        d[a].append(b)
    if b in d:
        d[b].append(a)
    else:
        d[b] = []
        d[b].append(a)
# print(d)
size = 0
for key in d.keys():
    if key not in vis:
        size+=1
        vis.add(key)
        ans = max(ans, size)
        # print("key", key,"ans",  ans,"s", size)
        dfs(key, size)
        size = 0
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
root = [-1] * n

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

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

def size(x):
    x = r(x)
    return -root[x]


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

"""
max_size = 0
for i in range(n):
    max_size = max(size(i), max_size)
"""
max_size = max(map(size, range(n)))

print(max_size)

Submission status: Runtime Error

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

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

info = tuple(set(info))

comp = [[info[0][0],info[0][1]]]
for i in range(len(info)):
    for k,group in enumerate(comp):
        if info[i][0] in group and info [i][1] in group:
            break
        elif info[i][0] in group:
            group.append(info[i][1])
            break
        elif info[i][1] in group:
            group.append(info[i][0])
            break
        if k+1 == len(comp):
            comp.append([info[i][0],info[i][1]])
    
max_n = 0    
for group in comp:
    max_n = max(len(group), max_n)
    
print(max_n)

Submission status: Runtime Error

Solution code:
ans = 0
n, m = map(int, input().split())
d = dict()
vis = set()
def dfs(key, size):
    global ans
    for friend in d[key]:
        if friend not in vis:
            size+=1
            vis.add(friend)
            ans = max(ans, size)
            # print("key", friend,"ans",  ans,"s", size)
            dfs(friend, size)
rep = set()
for _ in range(m):
    a, b = map(int, input().split())
    if (a, b) in rep or (b, a) in rep:
        continue
    rep.add((a, b))
    if a in d:
        d[a].append(b)
    else:
        d[a] = []
        d[a].append(b)
    if b in d:
        d[b].append(a)
    else:
        d[b] = []
        d[b].append(a)
# print(d)
size = 0
for key in d.keys():
    if key not in vis:
        size+=1
        vis.add(key)
        ans = max(ans, size)
        # print("key", key,"ans",  ans,"s", size)
        dfs(key, size)
        size = 0
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
root = [-1] * n

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

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

def size(x):
    x = r(x)
    return -root[x]


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

max_size = 0
for i in range(n):
    max_size = max(size(i), max_size)


print(max_size)

Submission status: Runtime Error

Solution code:
ans = 0
n, m = map(int, input().split())
d = dict()
vis = set()
def dfs(key, size):
    global ans
    for friend in d[key]:
        if friend not in vis:
            size+=1
            vis.add(friend)
            ans = max(ans, size)
            # print("key", friend,"ans",  ans,"s", size)
            dfs(friend, size)
rep = set()
for _ in range(m):
    a, b = map(int, input().split())
    if (a, b) in rep or (b, a) in rep:
        continue
    rep.add((a, b))
    if a in d:
        d[a].append(b)
    else:
        d[a] = []
        d[a].append(b)
    if b in d:
        d[b].append(a)
    else:
        d[b] = []
        d[b].append(a)
size = 0
for key in d.keys():
    if key not in vis:
        size+=1
        vis.add(key)
        ans = max(ans, size)
        # print("key", key,"ans",  ans,"s", size)
        dfs(key, size)
        size = 0
print(ans)

Submission status: Runtime Error

Solution code:
ans = 0
n, m = map(int, input().split())
d = dict()
vis = set()
def dfs(key, size):
    global ans
    for friend in d[key]:
        if friend not in vis:
            size+=1
            vis.add(friend)
            ans = max(ans, size)
            # print("key", friend,"ans",  ans,"s", size)
            dfs(friend, size)
rep = set()
for _ in range(m):
    a, b = map(int, input().split())
    if (a, b) in rep or (b, a) in rep:
        continue
    rep.add((a, b))
    if a in d:
        d[a].append(b)
    else:
        d[a] = []
        d[a].append(b)
    if b in d:
        d[b].append(a)
    else:
        d[b] = []
        d[b].append(a)
print(d)
size = 0
for key in d.keys():
    if key not in vis:
        size+=1
        vis.add(key)
        ans = max(ans, size)
        # print("key", key,"ans",  ans,"s", size)
        dfs(key, size)
        size = 0
print(ans)

Submission status: Runtime Error

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

    groups = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if a in groups and b in groups:
            group[a] = groups[a] | groups[b]
            groups[b] = groups[a]
        elif a in groups:
            groups[a].add(b)
            groups[b] = groups[a]
        elif b in groups:
            groups[b].add(a)
            groups[a] = groups[b]
        else:
            groups[a] = set([a,b])
            groups[b] = groups[a]

    if M == 0:
        print(0)
        return

    x = groups.values()
    ans = max(map(len, groups.values()))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

    groups = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        if a in groups and b in groups:
            group[a] = groups[a] | groups[b]
            groups[b] = groups[a]
        elif a in groups:
            groups[a].add(b)
            groups[b] = groups[a]
        elif b in groups:
            groups[b].add(a)
            groups[a] = groups[b]
        else:
            groups[a] = set([a,b])
            groups[b] = groups[a]

    if M == 0:
        print(01
        return

    x = groups.values()
    ans = max(map(len, groups.values()))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit

def find(par,i):
    if par[i]<0:
        return i
    par[i] = find(par,par[i])
    return par[i]

def unite(par,i,j):
    ri = find(par,i)
    rj = find(par, j)
    if ri==rj:
        return
    par[rj] += par[ri]
    par[ri] = rj
    
setrecursionlimit(10**6)
n,m = map(int,input().split())

parent = [-1]*n
for _ in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    unite(parent,a,b)
    print(parent)
    

print(-min(parent))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
k=[]
l=[-1 for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    a,b=a-1,b-1
    if l[a]<0 and l[b]<0:
        k+=[[a,b]]
        l[a],l[b]=len(k)-1,len(k)-1
    elif l[a]<0:
        k[l[b]]+=[a]
        l[a]=l[b]
    elif l[b]<0:
        k[l[a]]+=[b]
        l[b]=l[a]
    else:
        if l[a]!=l[b]:
            p=k[l[b]]
            k.remove(p)
            k[l[a]]+=p
            l[a]=l[b]
p=0
for i in k:
    p=max([len(i),p])
print(p)

Submission status: Runtime Error

Solution code:
#unionfind木_

def find(k):#要素k
    if par[k] == k:
        return par[k]
    else:
        par[k] = find(par[k])
        return par[k]

def union(i, j):
    i = find(i)
    j = find(j)
    if i==j: return False
    else:
        if rank[i] == rank[j]:#ランクが同じ場合
            par[j] = par[i]
            rank[i] += 1
        if rank[j] > rank[i]:
            i, j = j, i
            par[i] = par[j]
        else:
            par[i] = par[j]

n, m= map(int, input().split())
par = list(range(n))#初めは自分自身が親
rank = [1]*n

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

ans = [0]*n
for i in range(n):
    ans[find(ini_list[i])]+=1
print(max(ans))

Submission status: Runtime Error

Solution code:
#unionfind木_
class unionfind():
    def __init__(self, init_list, ide_ele=1):
        self.par = init_list #初めは自分自身が親
        self.rank = [ide_ele]*len(init_list)

    def find(self, k):#要素k
        if self.par[k] == k:
            return self.par[k]
        else:
            self.par[k] = self.find(self.par[k])
            return self.par[k]

    def union(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if i==j: return False
        else:
            if self.rank[i] == self.rank[j]:#ランクが同じ場合
                self.par[j] = self.par[i]
                self.rank[i] += 1
            if self.rank[j] > self.rank[i]:
                i, j = j, i
                self.par[i] = self.par[j]
            else:
                self.par[i] = self.par[j]

n, m= map(int, input().split())
ini_list = list(range(n))
uni_tree = unionfind(ini_list)
for i in range(m):
    a, b = map(lambda x:int(x)-1, input().split())
    uni_tree.union(a, b)

ans = [0]*n
for i in range(n):
    ans[uni_tree.find(ini_list[i])]+=1
print(max(ans))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
root = [-1] * n

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

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

def size(x):
    x = r(x)
    return -root[x]


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

max_size = 0
for i in range(m):
    max_size = max(size(i), max_size)


print(max_size)

Submission status: Runtime Error

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


def main():
    N,M = list(map(int, sys.stdin.readline().split()))
    AB_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(M) ]


    edge = {}
    # { int : set }
    # { the number of human : {friends} }

    for a,b in AB_list:
        edge.setdefault(a, set())
        edge[a].add(b)

        edge.setdefault(b, set())
        edge[b].add(a)
    

    visited = [None] + [0]*N
    #  0: not visited,  1:visited

    max_relation = 0

    for i in range(1, N+1):
        if visited[i] == 0:
            visited[i] = 1
            ret = dfs(edge, visited, i)
            max_relation = max(max_relation, ret)
    
    
    print( max_relation )


def dfs(edge, visited, num):
    res =[]

    if num in edge:
        for next_node in edge[num]:
            if visited[next_node] == 0:
                visited[next_node] = 1
                
                d = dfs(edge, visited, next_node)
                res.append(d)


    if res:
        return 1 + sum(res)
    else:
        return 1


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

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


for i in range(m):
    if M==[]:
        M.append(L[i])
    else:
        for j in range(len(L)):
            if L[i][0] in M[j] or L[i][1] in M[j]:
                M[j]=get_unique_list(M[j]+L[i])
                break
            else:
                 M.append(L[i])

print(max(len(x) for x in M))

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(0,n+1)]
# print(par)
s = list()

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

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

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(1,n+1):
    s.append(find(k))
# print(s)
c = collections.Counter(par)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(0,n+1)]
# print(par)
s = list()

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

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

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(1,n+1):
    s.append(find(k))
# print(par)
# print(s)
c = collections.Counter(par)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(0,n+1)]
# print(par)
s = list()

# union find(parには0も入れているためインデックスを変える必要はない)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        par[x] = y

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

# 1～nの親を探してsに入れていき、一番多い親を答えにする
for k in range(1,n+1):
    s.append(find(k))
# print(s)
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.num = [1 for i in range(n)]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.parent[x] = y
            self.num[y] += self.num[x]

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

    def count(self, x):
        return self.num[self.root(x)]

N, M = map(int, input().split())
un = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    un.unite(a, b)
ans = 0
for i in range(N):
    ans = max(ans, un.count(i))
print(ans)

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(0,n+1)]
# print(par)
s =list()
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        par[x] = y
for j in range(m):
    a, b = map(int, input().split())
    union(a,b)
for i in range(1,n+1):
    s.append(find(i))
# print(s)
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(0,n+1)]
# print(par)
s =list()
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        par[x] = y
for j in range(m):
    a, b = map(int, input().split())
    union(a,b)
for i in range(n+1):
    s.append(find(i))
s.remove(0)
# print(s)
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
par = [i for i in range(n+1)]
s =list()
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
        par[x] = y
for j in range(m):
    a, b = map(int, input().split())
    union(a,b)
for i in range(n+1):
    s.append(find(i))
# print(s)
c = collections.Counter(s)
print(max(c.values()))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
A = [0] * (M-1)
B = [0] * (M-1)
for i in range(M):
    A[i], B[i] = map(int, input().split())

class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        self.par = [-1 for i in range(n + 1)]
        # 木の高さを格納する（初期状態では0）
        """self.rank = [0] * (n + 1)"""

    # 検索
    # 根ならその番号を返す
    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:
            if self.par[x] < self.par[y]:  # par<0の小さい方に合わせる
                self.par[y] += self.par[x]
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                # 木の高さが同じなら片方を1増やす
                """if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1"""

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.par[self.find(x)]
    
    
u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])
    
ans = 1
for i in range(1, N+1):
    ans = max(ans, u.size(i))
print(ans)