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:
from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]

for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
ans = 0

for i in range(1,N+1):
  st = deque([i])
  cnt = 0
  check = [0]*(N+1)
  mark = [0]*(N+1)
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        mark[t] = s
        check[t] = 1
        st.append(t)
        cnt += 1
  ans = max(ans,cnt)
print(ans)

Submission status: Wrong Answer

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

graph = [[] for _ in range(n + 1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

for i in range(len(graph)):
    graph[i] = list(set(graph[i]))

ans = 0
for i in range(1, n + 1):
    count = 0
    for j in graph[i]:
        for k in graph[j]:
            if i == k:
                count += 1

    ans = max(ans, count)

print(ans + 1)

Submission status: Wrong Answer

Solution code:
##https://tjkendev.github.io/procon-library/python/union_find/union_find.html
from collections import Counter

N = 3*10**5

p = [i for i in range(N)]
rank = [1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1

def main():

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

    for _ in range(M):
        a,b = map(int,input().split())
        a,b = a-1,b-1
        unite(a,b)
    ##print(p[:n])
    tmp = Counter(p[:n])
    print(max(tmp.values()))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
import time
A,B=[],[]

l=[-1]*N

def getID(l,idx):
  if idx==-1:
    print("error")
    time.sleep(2000)
    return -1
  while True:
    if idx==l[idx]:break
    idx=l[idx]
  return idx

for i in range(M):
  s=list(map(int,input().split()))
  s[0]-=1
  s[1]-=1
  if l[s[0]]==-1 and l[s[1]]==-1:
    l[s[0]]=s[0]
    l[s[1]]=s[0]
  elif l[s[0]]==-1 or l[s[1]]==-1:
    for j in range(2):
      if l[s[j]]==-1:
        l[s[j]]=l[s[(j+1)%2]]
  else:
    r1=getID(l,s[0])
    r2=getID(l,s[1])
    if getID(l,s[0])==getID(l,s[1]):continue
    l[r1]=r2

d={}
for i in range(N):
  x=getID(l,i)
  d.setdefault(x,0)
  d[x]+=1
ans=0
for i in d:
  ans=max(ans,d[i])
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=[[i,i] for i in range(n+1)]
g=[[i,0] for i in range(n+1)]
x[0][1]=0
for i in range(m):
    a,b=map(int,input().split())
    p=[]
    if x[a][1]!=x[b][1]:
        x[a][1]=min(x[a][1],x[b][1])
        x[b][1]=min(x[a][1],x[b][1])
ans=0
for i in range(n):
    g[x[i+1][1]][1]+=1
for i in range(n):
    ans=max(ans,g[i+1][1])

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
e = list(set([tuple(sorted(map(int, input().split()))) for _ in range(m)]))
e.sort()
g = {k: 1 for k in range(1, n+1)}

for a, b in e[::-1]:
  g[a] += g[b]
  g[b] = 0

print(max(g.values()))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M = LI()
    par = [i for i in range(N + 1)]
    par_size = [1 for _ 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):
        if same(x, y):
            return 0
        par[find(x)] = find(y)
        par_size[find(x)] += 1
    for _ in range(M):
        A, B = LI()
        unite(A, B)
    ans = 0
    for p in par_size:
        ans = max(ans, p)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[0]*(n+1) 

mn=0
c=1
for i in range(m):
  a,b=map(int,input().split())
  if l[a]!=0:
    l[b]=l[a]
  elif l[b]!=0:
    l[a]=l[b]
  else:
    l[b]=c
    l[a]=c
  c+=1

for i in range(1,c+1):
  mn=max(mn,l.count(i))
print(mn)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
set_dict = {}
for i in range(m):
    a, b = map(int, input().split())
    if a in set_dict:
        set_dict[a].add(b)
    else:
        set_dict[a] = {a, b}
    if b in set_dict:
        set_dict[b].add(a)
    else:
        set_dict[b] = {a, b}
    if len(set_dict[a]) > 3:
        set_dict[b] = set_dict[b] | set_dict[a]
    if len(set_dict[b]) > 3:
        set_dict[a] = set_dict[a] | set_dict[b]
ans = 1
for i in range(n):
    if i in set_dict:
        ans = max(len(set_dict[i]), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map( int, input().split() )
a = []
b = []
friend = [ [] for _ in range( n ) ]
for _ in range( m ):
    a_i, b_i = map( int, input().split() )
    a.append( a_i - 1 )
    b.append( b_i - 1 )
    if a_i < b_i:
        friend[ a_i - 1 ].append( b_i - 1 )
    else:
        friend[ b_i - 1 ].append( a_i - 1 )

group = [ -1 for _ in range( n ) ]
group_id = 0
for i in range( n ):
    if group[ i ] == -1:
        group[ i ] = group_id
        group_id += 1
    for j in friend[ i ]:
        group[ j ] = group[ i ]

num_v = [ 0 for _ in range( n ) ]
for i in range( n ):
    num_v[ group[ i ] ] += 1

# print( group )
# print( num_v )
print( max( num_v ) )

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().split()]

relations = []
for i in range(M):
    relations.append([int(i) for i in input().split()])
    
def search(node,stock):
    ng_list = []
    for s in stock:
        go = False
        for n in node:
            if n in s:
                go = True
                break
        if go:
            node = list(set(node)|set(s))
        else:
            ng_list.append(s)
    return len(node),ng_list
    
MaxMember = 0    
while(len(relations)>1):
    l_member,relations = search(relations[0],relations[1:])
    MaxMember = max(MaxMember,l_member)

print(MaxMember)

Submission status: Wrong Answer

Solution code:
from collections import Counter


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


def same(par, x, y):
    return root(par, x) == root(par, y)


def unite(rank, par, x, y):
    x = root(par, x)
    y = root(par, y)

    if x == y:
        return

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


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

    par = list(range(N))
    rank = [0 for _ in range(N)]

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

    C = Counter(par)
    ans = C.most_common()[0][1]
    print(ans)



main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
n = [i+1 for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    n[b-1] = a if n[b-1] == b else n[b-1]
import collections
g = 0
for k, v in collections.Counter(n).items():
    g = max(v, g)
print(g)

Submission status: Wrong Answer

Solution code:
nm = input('').split()
n = int(nm[0])
m = int(nm[1])

friends={}
for i in range(m):
    ab=input('').split()
    a = int(ab[0])
    b = int(ab[1])
    if a not in friends.keys():
        friends[a]=[]
    if b not in friends.keys():
        friends[b]=[]
    if b not in friends[a]:
        friends[a].append(b)
    if a not in friends[b]:
        friends[b].append(a)

mx=0
for k,v in friends.items():
#    print(v)
    len_v=len(v)
    if len_v>mx:
        mx=len_v
print(mx+1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A,B=[],[]

l=[-1]*N

def getID(l,idx):
  if idx==-1:
    print("error")
    return -1
  while True:
    if idx==l[idx]:break
    idx=l[idx]
  return idx

for i in range(M):
  s=list(map(int,input().split()))
  s[0]-=1
  s[1]-=1
  if l[s[0]]==-1 and l[s[1]]==-1:
    l[s[0]]=s[0]
    l[s[1]]=s[0]
  elif l[s[0]]==-1 or l[s[1]]==-1:
    for j in range(2):
      if l[s[j]]==-1:
        l[s[j]]=l[s[(j+1)%2]]
  else:
    r1=getID(l,s[0])
    r2=getID(l,s[1])
    if getID(l,s[0])==getID(l,s[1]):continue
    l[r1]=r2

d={}
for i in range(N):
  x=getID(l,i)
  d.setdefault(x,0)
  d[x]+=1
ans=0
for i in d:
  ans=max(ans,d[i])
print(ans)

Submission status: Wrong Answer

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

xs=[-1]*n

abs = set()
for _ in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    abs.add((a,b))
    abs.add((b,a))
abs = sorted(list(abs), key=lambda x:x[0])

for a,b in abs:
    if xs[a] == -1 and xs[b] == -1:
        min_ = min(a,b)
        xs[a] = min_
        xs[b] = min_
    else:
        new = [xs[k] for k in [a,b] if xs[k] != -1][0]
        xs[a] = new
        xs[b] = new

    # print(xs)

from collections import Counter

xs = [x for x in xs if x != -1]

if xs != []:
    print(max(Counter(xs).values()))
else:
    print(1)

Submission status: Wrong Answer

Solution code:
n,m = (int(x) for x in input().split())
friendlist = [0]*n
classes = 1
for i in range(m):
    a,b = (int(x)-1 for x in input().split())
    if friendlist[a]!=0:
        friendlist[b] = friendlist[a]
    if friendlist[b]!=0:
        friendlist[a] = friendlist[b]
    else:
        friendlist[a] = classes
        friendlist[b] = classes
        classes += 1

count = [0]*classes
maxa = 0
for i in range(n):
    count[friendlist[i]] += 1
    maxa = max([count[friendlist[i]],maxa])

print(maxa)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,m=map(int,input().split())
par=[i for i in range(n+1)]
rank=[0]*(n+1)
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 0
  if rank[x]<rank[y]:
    par[x]=y
  else:
    par[y]=x
    if rank[x]==rank[y]:
      rank[x]+=1
for i in range(m):
  a,b=map(int,input().split())
  unite(a,b)
counter=Counter(par)
print(counter.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]

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


check = [0]*(N+1)
# check[1] = 1
mark = [0]*(N+1)
ans = 0

for i in range(1,N+1):
  st = deque([i])
  cnt = 0
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        mark[t] = s
        check[t] = 1
        st.append(t)
        cnt += 1
  ans = max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


uf = UnionFind()


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

g = list(uf.grouper())

ans = 0
for i in g:
    ans = max(ans, len(i))

print(ans)

Submission status: Wrong Answer

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

friend = [1]*N
visited = [[]]*N
for i in range(M):
    A,B = list(map(int,input().split()))
    if A> B:
        A,B = [B,A]
    A -= 1
    B -= 1
    if not B in visited[A]:
        friend[A],friend[B] = [friend[A]+friend[B],friend[A]+friend[B]]
        visited[A].append(B)
print(max(friend))

Submission status: Wrong Answer

Solution code:
(n,m),*e=[[*map(int,i.split())]for i in open(0)]
d=[[]for i in range(n+1)]
for i,j in e:
    d[i]+=[j]
    d[j]+=[i]
for i in range(n+1):
    for j in set(d[i]):
        d[i]+=d[j]
print(max(len(set(d[i]))for i in range(n+1)))

Submission status: Wrong Answer

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

friends = [[0 for _ in range(0)] for _ in range(N)]

for i in range(M):
    friends[AB[i][0]-1].append(AB[i][1])
    friends[AB[i][1]-1].append(AB[i][0])

ans = 0
for i in range(N):
    ans = max(ans, len(set(friends[i])))

print(ans+1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Friend = list(range(N))
for i in range(M):
    A, B = map(int, input().split())
    a = A-1
    b = B-1
    if(B < A):
        a = B-1
        b = A-1
    Friend[b] = Friend[a]
sF = sorted(Friend)
now = 0
count = 0
cmax = 0
for i in range(N):
    if(sF[i] == now):
        count += 1
        if(count > cmax):
            cmax = count
    else:
        now = sF[i]
        if(count > cmax):
            cmax = count
        count = 1
print(cmax)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
fri_dic = {}
for _ in range(m):
  a, b = map(int, input().split())
  if a not in fri_dic:
    fri_dic[a] = set()
  if b not in fri_dic[a]:
    fri_dic[a].add(b)
  if b not in fri_dic:
    fri_dic[b] = set()
  if a not in fri_dic[b]:
    fri_dic[b].add(a)
visited = set()
count = 0
for i in range(1, n + 1):
  #print(visited)
  if i not in visited and i != 1:
    continue
  count += 1
  queue = [i]
  while queue:
    p = queue.pop(0)
    if p in visited:
      continue
    visited.add(p)
    if p not in fri_dic:
      continue
    for j in fri_dic[p]:
      queue.append(j)
print(count)

Submission status: Wrong Answer

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


friends=[]
num=0
people=[-1]*n
ans=0

for f in F:

    if people[f[0]-1]==-1 and people[f[1]-1]==-1:
        friends.append({f[0]-1,f[1]-1})
        people[f[0]-1]=num
        people[f[1]-1]=num
        num+=1

    if people[f[0]-1]!=-1:
        friends[people[f[0]-1]].add(f[1]-1)
        people[f[1]-1]=people[f[0]-1]

    if people[f[1]-1]!=-1:
        friends[people[f[1]-1]].add(f[0]-1)
        people[f[0]-1]=people[f[1]-1]

for i in friends:
    if len(i)>ans:
        ans=len(i)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
f=[[] for i in range(n)]
j=1
shozoku=[0]*n
for i in range(m):
    if shozoku[ab[i][0]-1]==0:
        if shozoku[ab[i][1]-1]==0:
            shozoku[ab[i][0]-1]+=j
            shozoku[ab[i][1]-1]+=j
            f[j-1].append(ab[i][0])
            f[j-1].append(ab[i][1])
            j+=1
        else:
            shozoku[ab[i][0]-1]+=shozoku[ab[i][1]-1]
            f[shozoku[ab[i][1]-1]-1].append(ab[i][0])
    else:
        if shozoku[ab[i][1]-1]==0:
            shozoku[ab[i][1]-1]+=shozoku[ab[i][0]-1]
            f[shozoku[ab[i][0]-1]-1].append(ab[i][0])
ans=0
for i in range(n):
    ans=max(len(f[i]),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

graph = [[] for _ in range(n+1)]
for i in range(m):
    s = li[i][0]
    t = li[i][1]
    
    graph[s].append(t)
    graph[t].append(s)

ans = 0
for i in range(n+1):
    graph[i] = set(graph[i])
    ans = max(ans, len(graph[i]))
    
print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

AB = []
pos = [i for i in range(N)]
for _ in range(M):
    tmp = list(map(int,input().split()))
    tmp.sort()
    AB.append(tmp)

AB.sort()
for i in range(M):
    a,b = AB[i]
    pos[b-1] = pos[a-1]

c = Counter(pos)
ans = c[0]
print(ans)

Submission status: Wrong Answer

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

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

for i in range(1,N+1):
    D[i]=[]

for i in range(M):
    A,B=map(int,input().split())
    if A not in D[B]: D[B].append(A)
    if B not in D[A]: D[A].append(B)

ans=0
for i in range(1,N+1):
    L=len(D[i])+1
    if L>ans: ans=L

print(ans)

Submission status: Wrong Answer

Solution code:
N, M=map(int, input().split())
fri=[0]*N
s = set([])
for _ in range(M):
  a=list(map(int, input().split()))
  a.sort()
  if tuple(a) not in s:
    s.add(tuple(a))
    fri[a[0]-1]+=1
    fri[a[1]-1]+=1
ans=max(fri)+1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M=map(int,input().split())
groupnumber=[0 for i in range(N)]
counter=0
for i in range(M):
  a,b=map(int,input().split())
  a-=1
  b-=1
  if groupnumber[a]==0 and groupnumber[b]==0:
    counter+=1
    groupnumber[a]=counter
    groupnumber[b]=counter
  elif groupnumber[a]==0 and groupnumber[b]!=0:
    groupnumber[a]=groupnumber[b]
  elif groupnumber[a]!=0 and groupnumber[b]==0:
    groupnumber[b]=groupnumber[a]
groupsuu=counter
each_groupmember=[0 for i in range(groupsuu+1)]
for i in range(N):
  tmp=groupnumber[i]
  each_groupmember[tmp]+=1
print(max(each_groupmember))

Submission status: Wrong Answer

Solution code:
from collections import deque
from random import randint

class Friend():
    def __init__(self, ID):
        self.friends = {ID}
def coFriend(A, B):
    global ans
    if not A in friends:
        friends[A] = Friend(A)
    if not B in friends:
        friends[B] = Friend(B)
    for f in friends[B].friends:
        friends[A].friends.add(f)
        ans = max(ans, len(friends[A].friends))
    for f in friends[A].friends:
        friends[B].friends.add(f),

friends = dict()
N, M = map(int, input().split())
ans = 0
for _ in range(M):
    A, B = map(int, input().split())
    coFriend(A, B)

            
    
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N, M = LI()
    par = [i for i in range(N + 1)]
    par_size = [1 for _ 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):
        if same(x, y):
            return 0
        par[x] = find(y)
        par_size[find(x)] += 1
    for _ in range(M):
        A, B = LI()
        unite(A, B)
    ans = 0
    for p in par_size:
        ans = max(ans, p)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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

direction = [-1]+[False]*n
d = defaultdict(list)

for i in range(m):
    a,b = map(int,input().split())
    if direction[a] == False and direction[b] == False:
        direction[a] = a
        direction[b] = a
        d[a] += [a,b]
    elif direction[a] == False:
        direction[a] = direction[b]
        d[direction[b]].append(a)
    elif direction[b] == False:
        direction[b] = direction[a]
        d[direction[a]].append(b)
# print(d)
maxi = 1
for alist in d.values():
    maxi = max(maxi,len(alist))
print(maxi)

Submission status: Wrong Answer

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

S = [set([i]) for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    S[a].add(b)
    S[b].add(a)
    tmp_a = S[a]
    S[a] |= S[b]
    S[b] |= tmp_a

res = 0
for s in S:
    res = max(res, len(s))

print(res)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lsa = [{i} for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    lsa[a] = lsa[a] | lsa[b]
    lsa[b] = lsa[a] | lsa[b]
ans = 0
for i in range(N):
    ans = max(ans,len(lsa[i]))
print(ans)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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


n,m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1,a[i][1]-1)
ans = 0
x = [True]*n
for i in range(n):
    if (x[i]==False):
        continue
    print(i)
    t = uf.members(i)
    ans = max(ans,len(t))
    for j in t:
        x[j] = False
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

# from typing import Optional
# from typing import List
# from typing import Dict
# from typing import Tuple
# from typing import Sequence


def main():
    args = input().split()
    N = int(args[0])
    M = int(args[1])

    groupList = list()
    # fSet = set()
    for i in range(M):
        args = list(map(lambda x: int(x), input().split()))
        # fSet.add(args)

        isHit = False
        for group in groupList:
            if args[0] in group:
                group.add(args[1])
                break
                isHit = True
            elif args[1] in group:
                group.add(args[0])
                isHit = True
                break

        if not isHit:
            groupList.append({args[0], args[1]})

    maxNum = 0
    for group in groupList:
        maxNum = max(maxNum, len(group))

    print(maxNum)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections

# https://www.ics.uci.edu/~eppstein/PADS/UnionFind.py


class UnionFind:
    """Union-find data structure.

    Each unionFind instance X maintains a family of disjoint sets of
    hashable objects, supporting the following two methods:

    - X[item] returns a name for the set containing the given item.
      Each set is named by an arbitrarily-chosen one of its members; as
      long as the set remains unchanged it will keep the same name. If
      the item is not yet part of a set in X, a new singleton set is
      created for it.

    - X.union(item1, item2, ...) merges the sets containing each item
      into a single larger set.  If any item is not yet part of a set
      in X, it is added to X as one of the members of the merged set.
    """

    def __init__(self):
        """Create a new empty union-find structure."""
        self.weights = {}
        self.parents = {}

    def __getitem__(self, object):
        """Find and return the name of the set containing the object."""

        # check for previously unknown object
        if object not in self.parents:
            self.parents[object] = object
            self.weights[object] = 1
            return object

        # find path of objects leading to the root
        path = [object]
        root = self.parents[object]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]

        # compress the path and return
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):
        """Iterate through all items ever found or unioned by this structure."""
        return iter(self.parents)

    def union(self, *objects):
        """Find the sets containing the objects and merge them all."""
        roots = [self[x] for x in objects]
        heaviest = max([(self.weights[r], r) for r in roots])[1]
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest


n, m = [int(x) for x in input().split()]
if m == 0:
    print(1)
else:
    uf = UnionFind()
    for _ in range(m):
        a, b = [int(x) for x in input().split()]
        uf.union(a, b)
    print(collections.Counter(uf.parents.values()).most_common(1)[0][1])

Submission status: Wrong Answer

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

l = []  # 同値類のリスト
d = {}  # 各人がいるlのindex
tmp = 0

for i in range(M):
    A, B = map(int, input().split())
    if (d.get(A) == None) and (d.get(B) == None):
        d[A] = tmp
        d[B] = tmp
        tmp += 1
        l.append([A, B])
    elif (d.get(A) != None) and (d.get(B) == None):
        d[B] = d[A]
        l[d[A]].append(B)
    elif (d.get(A) == None) and (d.get(B) != None):
        d[A] = d[B]
        l[d[B]].append(A)
    else:
        continue

ans = 0
for i in range(len(l)):
    ans = max(len(l[i]), ans)

print(ans)

Submission status: Wrong Answer

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

friendsetlist = [set([]) for _ in range(n)]

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

    friendsetlist[a].add(b)
    friendsetlist[b].add(a)

    friendsetlist[a].union(friendsetlist[b])


ans = 0

for i in range(n):
    if ans < len(friendsetlist[i]):
        ans = len(friendsetlist[i])

print(ans+1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
d={k:[] for k in range(1,n+1)}
for a,b in l:
    for v in d[a]:
        d[v].append(b)
    d[a].append(b)
    for v in d[b]:
        d[v].append(a)
    d[b].append(a)
ans=0
for s in d.values():
    ans=max(ans,len(set(s))+1)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, M = map(int,input().split())
par = []
rank = [0] * (N + 1)
for i in range(N + 1): par.append(i)
def find(x):
    if par[x] == x: return x
    else:
         par[x] = find(par[x])
         return par[x]
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y: return 0
    if rank[x] < rank[y]: par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]: rank[x] += 1
def same(x,y):
    return find(x) == find(y)

for i in range(M):
    A, B = map(int,input().split())
    unite(A,B)
print(Counter(par).most_common()[0][1])