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: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

def main():

    N,M = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(M)]
    '''
    import random
    N = 4 * 10**4 
    M = N - 1
    X = [[random.randint(1,N),random.randint(1,N)] for i in range(M)] 
    '''        
    Y = [-1 for _ in range(N+1)]
    Z = [[] for _ in range(N+1)]
    '''
    # 前処理　大小関係の整理と重複の削除
    for x in X:
        a = x[0]
        b = x[1]
        if a == b:
            X.remove(x)
        elif a > b:
            x[0],x[1] = b,a
            
    X.sort()
    for i in reversed(range(len(X)-1)):
        if X[i+1]==X[i]:
            X.pop(i+1)
    '''
    for x in X:
        a = x[0]
        b = x[1]
        if Y[a] == -1:
            if Y[b] == -1:
                Y[a] = Y[b] = a
                Z[a] = [a,b]
            else:
                Y[a] = Y[b]
                Z[Y[b]] += [a]
        else:
            if Y[b] == -1:
                Y[b] = Y[a]
                Z[Y[a]] += [b]
            else:
                ya = Y[a]
                yb = Y[b]
                if ya != yb:
                    for y in Z[Y[b]]:
                        Y[y] = ya
                    Z[ya] += Z[yb]
                    Z[yb].clear()
        #print(x,Y,Z)
    
    Yf = set(Y)
    Yf.remove(-1)
    maxc = 0
    for i in Yf:
        maxc = max(maxc,len(Z[i]))
    print(maxc)
    
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

seen = [0] * N
q = deque()
group = []

for i in range(N):
    if seen[i]:
        continue
    q.append(i)
    seen[i] = 1
    k = 1
    while q:
        t = q.popleft()
        for j in range(M):
            if seen[AB[j][0] - 1] == 1 or seen[AB[j][1] - 1] == 1:
                break
            if AB[j][0] == i + 1 and seen[AB[j][1] - 1] != 1:
                q.append(AB[j][1])
                seen[AB[j][1] - 1] = 1
                k += 1
            if AB[j][1] == i + 1 and seen[AB[j][0] - 1] != 1:
                q.append(AB[j][0] - 1)
                seen[AB[j][0] - 1] = 1
                k += 1
    group.append(k)

print(max(group))

Submission status: Wrong Answer

Solution code:
class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    def find(self, x):
        if(self.parents[x] < 0):
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
        
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if(x == y):
            return
        
        if(self.parents[x] > self.parents[y]):
            x, y = y, x
            
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}:{}'.format(r, self.members(r)) for r in self.roots())

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

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

num = []
for idx in uf.roots():
    if(uf.members(idx)):
        num.append(len(uf.members(idx))-1)

cnt = num[0]
for i in range(1, len(num)):
    cnt = abs(cnt-num[i])
    
ans = len(num)-num.count(0)+cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
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)]

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

print(max(Counter(par).values()) + 1)

Submission status: Wrong Answer

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:
            return self.find(self.par[k])
    def union(self, i, j):
        if self.find(i)==self.find(j):
            return
        elif self.rank[i]>self.rank[j]:
            self.par[self.par[j]] = self.par[i]
        elif self.rank[i] < self.rank[j]:
            self.par[self.par[i]] = self.par[j]
        else:#ランクが同じ場合
            self.par[self.par[j]] = self.par[i]
            self.rank[i] += 1
n, m= map(int, input().split())
ini_list = list(range(n))
uni_tree = unionfind(ini_list)
for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    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: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

def main():
    N,M = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(M)]

    Y = [-1 for _ in range(N+1)]
    Z = [[] for _ in range(N+1)]

    # 前処理　大小関係の整理と重複の削除
    for x in X:
        a = x[0]
        b = x[1]
        if a > b:
            x[0],x[1] = b,a
    X.sort()
    for i in reversed(range(len(X)-1)):
        if X[i+1]==X[i]:
            X.pop(i+1)

    for x in X:
        a = x[0]
        b = x[1]
        if Y[a] == -1:
            if Y[b] == -1:
                Y[a] = Y[b] = a
                Z[a] = [a,b]
            else:
                Y[a] = Y[b]
                Z[Y[b]].append(a)
        else:
            if Y[b] == -1:
                Y[b] = Y[a]
                Z[Y[a]].append(b)
            else:
                ya = Y[a]
                yb = Y[b]
                if not ya == yb:
                    for y in Z[Y[b]]:
                        Y[y] = Y[a]
                    Z[ya].extend(Z[yb])
                    Z[yb] = []

    Yf = set(Y)
    maxc = 0
    for i in Yf:
        maxc = max(maxc,len(Z[i]))
    print(maxc)
        
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

list0=[]
list1=[]

listA3=[]
listA2=[]

for i in range(m):
  a,b=map(int, input().split())
  c=max(a,b)
  d=min(a,b)
  list0.append((d,c))
  list0.sort()
  list1=set(list0)

  
for i in list1:
  a2=str(i[0])
  b2=str(i[1])
  listA2.append(a2)
  listA2.append(b2)
  
for i in range(n):
  a3=listA2.count(str(i))
  listA3.append(int(a3))

ans=0
ans=max(listA3)

if ans==1:
  print(1)
else:
  ans=ans+1
  print(ans)

Submission status: Wrong Answer

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

list0=[]
list1=[]

listA3=[]
listB3=[]
listA2=[]
listB2=[]

for i in range(m):
  a,b=map(int, input().split())
  c=max(a,b)
  d=min(a,b)
  list0.append((d,c))
  list0.sort()
  list1=set(list0)

for i in list1:
  a2=str(i[0])
  b2=str(i[1])
  listA2.append(a2)
  listB2.append(b2)
  
for i in range(n):
  a3=listA2.count(str(i))
  listA3.append(int(a3))
  b3=listB2.count(str(i))
  listB3.append(int(b3))

ans=0
ans=max(listB3+listA3)

if ans==1:
  print(1)
else:
  ans=ans+1
  print(ans)

Submission status: Wrong Answer

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

listA3=[]
listB3=[]
listA2=[]
listB2=[]

for i in range(m):
  a,b=map(int, input().split())
  c=max(a,b)
  d=min(a,b)
  list1.append((d,c))
  list1.sort()

for i in list1:
  a2=str(i[0])
  b2=str(i[1])
  listA2.append(a2)
  listB2.append(b2)
  
for i in range(n):
  a3=listA2.count(str(i))
  listA3.append(int(a3))
  b3=listB2.count(str(i))
  listB3.append(int(b3))

ans=0
ans=max(listB3+listA3)

if ans==1:
  print(1)
else:
  ans=ans+1
  print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
dp=[0]*(N+1)
p=[0]*(N+1)
a=0
for _ in range(M):
  A,B=map(int,input().split())
  if dp[A]==0 and dp[B]==0:
    a+=1
    dp[A]=a
    dp[B]=a
    p[a]+=2
  elif dp[A]!=0 and dp[B]!=0:
    continue
  else:
    if dp[A]==0 and dp[B]!=0:
      dp[A]=dp[B]
      p[dp[B]]+=1
    else:
      dp[B]=dp[A]
      p[dp[A]]+=1
print(max(p))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
dp=[0]*(N+1)
p=[0]*(N+1)
a=0
for _ in range(M):
  A,B=map(int,input().split())
  if dp[A]==0 and dp[B]==0:
    a+=1
    dp[A]=a
    dp[B]=a
    p[a]+=2
  elif dp[A]!=0 and dp[B]!=0:
    continue
  else:
    if dp[A]==0 and dp[B]!=0:
      dp[A]=dp[B]
      p[dp[B]]+=1
    else:
      dp[B]=dp[A]
      p[dp[A]]+=1
ans=0
for i in range(N+1):
  ans=max(ans,p[i])
if sum(p)!=N:
  ans=max(N-sum(p),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
dp=[0]*(N+1)
p=[0]*(N+1)
a=0
for _ in range(M):
  A,B=map(int,input().split())
  if dp[A]==0 and dp[B]==0:
    a+=1
    dp[A]=a
    dp[B]=a
    p[a]+=2
  elif dp[A]!=0 and dp[B]!=0:
    continue
  else:
    if dp[A]==0 and dp[B]!=0:
      dp[A]=dp[B]
      p[dp[B]]+=1
    else:
      dp[B]=dp[A]
      p[dp[A]]+=1
ans=0
print(p)
for i in range(N+1):
  ans=max(ans,p[i])
if sum(p)!=N:
  ans=max(N-sum(p),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
dp=[0]*(N+1)
p=[0]*(N+1)
a=0
for _ in range(M):
  A,B=map(int,input().split())
  if dp[A]==0 and dp[B]==0:
    a+=1
    dp[A]=a
    dp[B]=a
    p[a]+=2
  elif dp[A]!=0 and dp[B]!=0:
    continue
  else:
    if dp[A]==0 and dp[B]!=0:
      dp[A]=dp[B]
      p[dp[B]]+=1
    else:
      dp[B]=dp[A]
      p[dp[A]]+=1
ans=0
for i in range(N+1):
  ans=max(ans,p[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
print(1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
print(1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N,M = map(int,input().split())
count = [[0]*N for _ in range(N)]
fr = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    a,b = a-1,b-1
    if count[a][b] == 1:
        continue
    count[a][b] = 1
    count[b][a] = 1
    fr[a].append(b)
    fr[b].append(a)
used = [-1]*N 
MAX = 0
def dfs(fr,cur,parent,cnt):
    global MAX
    MAX = max(cnt,MAX)
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        print(chi, used)
        used[chi] = 0
        cnt += 1
        dfs(fr,chi,cur,cnt)
    return

for i in range(N):
    print(i, 999)
    cnt = 1
    if used[i] != -1:
        continue
    used[i] = 0
    dfs(fr,i,-1,cnt)
print(MAX)

Submission status: Wrong Answer

Solution code:
NM = input()
N = int(NM.split()[0])
M = int(NM.split()[1])
info = []
for i in range(M):
    info += [input()]

info_friend = [info[i].split() for i in range(M)]
print(info)
friends = ['']*N
for j in range(N):
    friends[j] = str(j+1)
    for i in range(M):
        AB = info[i].split()
        A = AB[0]
        B = AB[1]
        if str(j+1) == A:
            friends[j] += B
        if str(j+1) == B:
            friends[j] += A
friends = [len(''.join(set(friends[i]))) for i in range(N)]
print(max(friends))

Submission status: Wrong Answer

Solution code:
# union-find

import collections

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

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

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

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

for i in list:
    unite(i[0],i[1])

c = collections.Counter(par)

print(c.most_common()[0][1])

Submission status: Wrong Answer

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

#AB = [tuple(map(int, input().split())) for i in range(M)]
#丸暗記。隣接リストの初期化
graph = [[i+1] for i in range(N)]

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

ans = 0
for g in graph:
  ans = max(ans, len(set(g)))
print(ans)

Submission status: Wrong Answer

Solution code:
def bfs(d,visit,i):
    q=[i]
    visit[i]=1
    count=1
    while(len(q)!=0):
        val=q.pop()
        for k in d[val]:
            if(visit[k]==0):
                count+=1
                visit[k]=1
                q.append(k)
    return count
    

n,m=map(int,input().split())
d=dict()
for i in range(1,n+1):
    d[i]=set()
for i in range(m):
    l,r=map(int,input().split())
    d[l].add(r)
    d[r].add(l)

visit=[0]*(n+1)

count=0
for i in range(1,n+1):
    if(visit[i]==0 and len(d[i])!=0):
        count=max(count,bfs(d,visit,i))
print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
tree=[[] for i in range(N+1)]

for i in range(M):
    A,B=map(int,input().split())
    tree[A].append(B)
    tree[B].append(A)
kazoe=tree.copy()
for i in range(1,N+1):
    for j in tree[i]:
        kazoe[i]+tree[j]
        #print(kazoe[i])
        kazoe[i]=list(set(kazoe[i]))
ans=0
for i in range(1,N+1):
    ans=max(len(kazoe[i]),ans)
print(ans+1)

Submission status: Wrong Answer

Solution code:
import numpy as np
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
N, M = map(int, input().split())
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])

p_lst = np.array(u.par)
_, count = np.unique(p_lst, return_counts=True)
max_count = count.max()
#print(p_lst)
print(max_count)

Submission status: Wrong Answer

Solution code:
import numpy as np
class UnionFind():
    def __init__(self, N):
        """
        それぞれの要素のルートを自分自身を指定する。
        それぞれの要素の高さを保持しておく
        
        args:
            - N (int) : 全データの要素数
        """
        self.parent = [i for i in range(N)]
        self.height = [0] * N
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.find(self.parent[x])
        
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        #print(self.parent)
        #print(self.height)
        if root_x==root_y:
          return
        
        
        if self.height[root_y] > self.height[root_x]:# x を yにくっつける
            self.parent[root_x] = root_y
        else: # y を xにくっつける
            self.parent[root_y] = root_x
            if self.height[root_x] == self.height[root_y]:
                self.height[root_x] += 1
    
    def count_group(self, x):
        """xが含まれるグループの要素数を得る"""
        root_x = self.find(x)
        return self.parent.count(root_x)

    
N, M = map(int, input().split())
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])

p_lst = np.array(u.parent)
_, count = np.unique(p_lst, return_counts=True)
max_count = count.max()
#print(p_lst)
print(max_count)

Submission status: Wrong Answer

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

N,M = map(int,input().split())
dic = {}
for _ in range(M):
  a,b = map(int,input().split())
  if a in dic.keys():
    dic[a].add(b)
  elif b in dic.keys():
    dic[b].add(a)
  else:
    if a<b:
      dic[a] = {b}
    else:
      dic[b] = {a}

mx = 0

for val in dic.values():
  mx = max(mx,len(val)+1)
print(mx)

Submission status: Wrong Answer

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

N,M = map(int,input().split())
dic = {}
for _ in range(M):
  a,b = map(int,input().split())
  if a in dic.keys():
    dic[a].append(b)
  elif b in dic.keys():
    dic[b].append(a)
  else:
    if a<b:
      dic[a] = [b]
    else:
      dic[b] = [a]

mx = 0

for val in dic.values():
  mx = max(mx,len(val)+1)
print(mx)

Submission status: Wrong Answer

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

N,M = map(int,input().split())
dic = {}
for _ in range(M):
  a,b = map(int,input().split())
  if a in dic.keys():
    dic[a].append(b)
  elif b in dic.keys():
    dic[b].append(a)
  else:
    if a<b:
      dic[a] = [b]
    else:
      dic[b] = [a]

mx = 0
print(dic)
for val in dic.values():
  mx = max(mx,len(val)+1)
print(mx)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
check = [-1]*N
friend = []
count = 0 
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    if((check[A-1]==-1) and (check[B-1]==-1)):
        friend.append([A,B])
        check[A-1]=count
        check[B-1]=count
        count +=1

    elif((check[A-1]==-1) and (check[B-1]!=-1)):
        friend[check[B-1]].append(A)
        check[A-1]=check[B-1]
    elif((check[A-1]!=-1) and (check[B-1]==-1)):
        friend[check[A-1]].append(B)
        check[B-1]=check[A-1]
    elif(check[A-1]!=check[B-1]):
        friend[check[A-1]].extend(friend[check[B-1]])
        for j in range(len(friend[check[B-1]])):
            test=friend[check[B-1]].pop()
            check[test-1]=check[A-1]
for i in range(len(friend)):
    ans = max(ans,len(friend[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
class UnionFind():
    def __init__(self, N):
        """
        それぞれの要素のルートを自分自身を指定する。
        それぞれの要素の高さを保持しておく
        
        args:
            - N (int) : 全データの要素数
        """
        self.parent = [i for i in range(N)]
        self.height = [0] * N
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.find(self.parent[x])
        
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        
        if self.height[root_y] > self.height[root_x]:# x を yにくっつける
            self.parent[root_x] = root_y
        else: # y を xにくっつける
            self.parent[root_y] = root_x
            if self.height[root_x] == self.height[root_y]:
                self.height[root_x] += 1
    
    def count_group(self, x):
        """xが含まれるグループの要素数を得る"""
        root_x = self.find(x)
        return self.parent.count(root_x)

    
N, M = map(int, input().split())
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a-1)
    B.append(b-1)

u = UnionFind(N)
for i in range(M):
    u.union(A[i], B[i])

p_lst = np.array(u.parent)
_, count = np.unique(p_lst, return_counts=True)
max_count = count.max()
print(max_count)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            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 return_par(self):
        return self.par

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


unionfind = UnionFind(n)
a = set()
for _ in range(m):
    x, y = sorted(map(int, input().split()))
    a.add((x, y))

for x, y in a:
    unionfind.union(x, y)
    
par = unionfind.return_par()

import collections
c = collections.Counter(par)
print(max(list(c.values())))

Submission status: Wrong Answer

Solution code:
def zero_origin(s: str):
  return int(s) - 1


class UnionFindTree:
  """Union Find Tree for disjoint-set data structure.

  Args:
    n (int): number of the vertices.
  """
  def __init__(self, n: int):
    self.parent = list(range(n))
    self.rank = [0] * n
    self.size = [1] * n

  def find(self, i: int) -> int:
    if self.parent[i] != i:
      self.parent[i] = self.find(self.parent[i])
    return self.parent[i]

  def unite(self, i: int, j: int):
    ri = self.find(i)
    rj = self.find(j)
    size = self.size[ri] + self.size[rj]
    self.size[ri] = size
    self.size[rj] = size
    if ri != rj:
      if self.rank[ri] < self.rank[rj]:
        self.parent[ri] = rj
      else:
        self.parent[rj] = ri
        if self.rank[ri] == self.rank[rj]:
          self.rank[ri] += 1

  def is_same(self, i: int, j: int) -> bool:
    return self.find(i) == self.find(j)


n, m = map(int, input().split())
uft = UnionFindTree(n)
for _ in range(m):
  a, b = map(zero_origin, input().split())
  uft.unite(a, b)
print(max(uft.size))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
check = [-1]*N
friend = []
count = 0 
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    if((check[A-1]==-1) and (check[B-1]==-1)):
        friend.append([A,B])
        check[A-1]=count
        check[B-1]=count
        count +=1

    elif((check[A-1]==-1) and (check[B-1]!=-1)):
        friend[check[B-1]].append(A)
        check[A-1]=check[B-1]
    elif((check[A-1]!=-1) and (check[B-1]==-1)):
        friend[check[A-1]].append(B)
        check[B-1]=check[A-1]
for i in range(len(friend)):
    ans = max(ans,len(friend[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
l=lambda:map(int, input().split())
n,m=l()
p=[-1]*n
def r(x):
  while p[x]>=0: x=p[x]
  return x
def u(x,y):
  x,y=r(x),(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def e(x,y):
  return r(x)==r(y)
def s(x):
  return -p[r(x)]
for _ in range(m):
  a,b=l()
  u(a-1,b-1)
print(-min(p))

Submission status: Wrong Answer

Solution code:
def bfs(i):
  stk = [i]
  check[i] = 1
  m = 1
  while stk != []:
    l = stk[-1]
    for val in mat[l]:
      if check[val] == 0:
        stk.append(val)
        check[val] = 1
        m += 1
    if len(stk) == 1:
      stk = []
    else:
      stk = stk[1:]
      
  return m
      
N, M = list(map(int, input().split(" ")))
check = [0 for _ in range(N+1)]
mat = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = list(map(int, input().split()))
  mat[a].append(b)
  mat[b].append(a)

ma = 1
for i in range(1, N+1):
  if check[i] == 0:
    ma = max(ma, bfs(i))
    
print(ma)

Submission status: Wrong Answer

Solution code:
l=lambda:map(int, input().split())
n,m=l()
p=[-1]*n
def r(x):
  while p[x]>=0: x=p[x]
  return x
def u(x,y):
  x,y=r(x),(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def e(x,y):
  return r(x)==r(y)
def s(x):
  return -p[r(x)]
for _ in range(m):
  a,b=l()
  u(a-1,b-1)
print(-min(p))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split(" "))
    if y-1 not in ar[x-1]:
        ar[x-1].append(y-1)
    if x-1 not in ar[y-1]:
        ar[y-1].append(x-1)
while True:
    count = 0
    for i in range(n):
        for j in range(n):
            if i != j and i in ar[j]:
                for r in ar[j]:
                    if r not in ar[i] and r != i:
                        ar[i].append(r)
                        count += 1
                        print(ar)
    if count == 0:
        break
br = []
for r in ar:
    br.append(len(set(r)))
print(max(br) + 1)

Submission status: Wrong Answer

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

  def get_root(self, i):
    while self.parent[i] != -1:
      i = self.parent[i]
    return i

  def is_same_tree(self, i, j):
    return self.get_root(i) == self.get_root(j)

  def merge(self, i, j):
    i = self.get_root(i)
    j = self.get_root(j)
    if i == j:
      return

    if self.rank[i] > self.rank[j]:
      self.parent[j] = i
      self.rank[i] = max(self.rank[i], self.rank[j] + 1)
      self.count[i] += self.count[j]
    else:
      self.parent[i] = j
      self.rank[j] = max(self.rank[j], self.rank[i] + 1)
      self.count[j] += self.count[i]


n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = [int(i) - 1 for i in input().split()]
  uf.merge(a, b)
print(max(uf.count))

Submission status: Wrong Answer

Solution code:
import copy
N,M = [int(i) for i in input().split()]
AB = []
ans = 1
for i in range(M):
  AB.append([int(i) for i in input().split()])
#print(AB)
rel = [[] for i in range(N)]
#print(rel)
for x in AB:
  #print(rel[x[0]-1],x[1]-1)
  rel[x[0]-1].append(x[1]-1)
  rel[x[1]-1].append(x[0]-1)
#print(rel)
rel = [list(set(x)) for x in rel]

check = [0 for i in range(N)]
##print(check)
q = copy.deepcopy(rel[0])
check[0] = 1
checkstart = copy.deepcopy(check)
while(check != [1 for i in range(N)]):
  #print("check =",check)
  #print("rel=",rel)
  #print("q =",q)
  qlen = 0
  if(check == checkstart):
    qlen = 1
  while(q != []):
    #print("q =",q)
    ima = q.pop()
    qlen += 1
    #print("qlen =",qlen)
    #print("ima =",ima)
    #print("check[ima] =" ,check[ima])
    if check[ima] == 0:
      check[ima] = 1 
      for x in rel[ima]:
        if check[x] == 0:
          q.append(x)
          q = list(set(q))
  for j in range(N):
    if check[j] == 0:
      q.append(j)
      q = list(set(q))
      break
  ans = max(ans, qlen)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections as col

N,M=map(int, input().split())
p=[-1]*N
p[0]=1
for _ in range(M):
    i,j=map(int, input().split())
#    print(i,j)
    if p[i-1]!=-1 and p[j-1]!=-1:
#        print('a')
        temp=p[j-1]
        p=[p[i-1] if k==temp else k for k in p]       
    elif p[j-1]==-1 and p[i-1]!=-1:
#        print('b')
        p[j-1]=p[i-1]
    elif p[j-1]!=-1 and p[i-1]==-1:
#        print('c')
        p[i-1]=p[j-1]
    else:
#        print('d')
        p[j-1]=i

    

#print(p)
ans=col.Counter(p)

if ans.most_common()[0][0]==-1:
    print(ans.most_common()[1][1])
else:
    print(ans.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
def dfs(i):
  stk = [i]
  check[i] = 1
  m = 1
  while stk != []:
    f = stk[0]
    nxt = None
    for val in mat[f]:
      if check[val] == 0:
        nxt = val
        break
    if nxt is not None:
      stk.append(nxt)
      check[nxt] = 1
      m += 1
    else:
      stk.pop()
  return m
      
N, M = list(map(int, input().split(" ")))
check = [0 for _ in range(N+1)]
mat = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = list(map(int, input().split()))
  mat[a].append(b)
  mat[b].append(a)

ma = 1
for i in range(1, N+1):
  if check[i] == 0:
    ma = max(ma, dfs(i))
    
print(ma)