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:
import collections
n,m = map(int, input().split())

friends = [0] * n
query = []

tmp = 1
for i in range(m):
  a,b = map(int, input().split())
  if friends[a - 1] == 0 and  friends[b - 1] == 0:
    friends[a - 1] = tmp
    friends[b - 1] = tmp
    tmp += 1
  elif friends[a - 1] == 0:
    friends[a - 1] = friends[b - 1]
  elif friends[b - 1] == 0:
    friends[b - 1] = friends[a - 1]
  else:
    index_num = [n for n, v in enumerate(friends) if v == friends[a - 1]]
    duplicated = friends[b - 1]
    for j in index_num:
      friends[j] = duplicated
      
counted = collections.Counter(friends)
if counted.most_common()[0][1] != 0:
  print(counted.most_common()[0][1])
else:
  print(counted.most_common()[0][2])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
if m == 0:
    print(1)
    exit()

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

g = [set([i]) for i in range(n + 1)]
for a, b in fs:
    g[a] |= g[b]
    g[b] |= g[a]

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
from collections import deque
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
MOD2 = 998244353
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, Q = NMI()
    PAB = [NLI() for _ in range(Q)]
    
    #各頂点の遡った親が同じなら、同じグループ
    parents = [i for i in range(N+1)] # 最初は自分自身が親。

    
    def find_parent(x):#ある子の親を探す
        if parents[x] == x:#自分自身が親ならそれでいい
            return x
        else:
            parents[x] = find_parent(parents[x])#親の値を親の親の…親に書き換える
            return parents[x]
    
    
    def unite_children(x,y):#親を同じにする
        parent_x = find_parent(x)
        parent_y = find_parent(y)
        if parent_x == parent_y:#すでに親が同じなら何もしない
            return
        parents[x] = parents[y]


        
    for q in range(Q):
        a = PAB[q][0]
        b = PAB[q][1]
        
        unite_children(a,b)

    del parents[0]
    pa = collections.Counter(parents)
    print(pa.most_common()[0][1])





if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
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)
print(collections.Counter(par).most_common()[0][1])

Submission status: Wrong Answer

Solution code:
n,m=list(map(int, input().split()))
a=[]
b=[]
for j in range(m):
    a1,b1=[int(j) for j in input().split()]
    a.append(a1)
    b.append(b1)
d=[0]*n
e=[0]*n
f=[0]*n
for q in range(n):
    d[q]=q


for i in range(m):
    x=min(a[i],b[i])-1
    y=max(a[i],b[i])-1
    z=x
    while z!=d[z]:
        z=d[z]
    d[y]=z
    f[z]+=f[y]+1
for j in range(n):
    p=d[j]
    e[p]+=1
print(max(e))

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)
        unite(b,a)
    ##print(p[:n])
    tmp = Counter(p[:n])
    print(max(tmp.values()))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N,M=map(int,input().split())
# rinsetu=[set() for _ in range(N+1)]
dic={}
for i in range(M):
    a,b=map(int,(input().split()))
    if a not in dic:
        c=set()
        c.add(a)
        c.add(b)
        dic[a]=c
    else:dic[a].add(b)
    if b not in dic:
        dic[b] = dic[a]
    else:dic[b].add(a)

    # rinsetu[a].add(b)
    # rinsetu[b].add(a)
ans=0
for v in dic.values():
    ans=max(ans,len(v))
print(ans)
# grp=0
# color=["white"]*(N+1)
# color[0]="black"
# for i in range(1,N+1):
#     if color[i]=="white":
#         d = deque()
#         d.append(i)
#         a = set()
#         a.add(i)
#         while(d):
#             k=d.popleft()
#             color[k]="black"
#             for j in rinsetu[k]:
#                 if color[j]=="white":
#                     d.append(j)
#                     a.add(j)
#         grp=max(grp,len(a))
# print(grp)

Submission status: Wrong Answer

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

mx=0
friends=[]

for i in range(m):
    ab=input('').split()
    a = int(ab[0])
    b = int(ab[1])
    ingroup=False
    for f in friends:
        if a in f:
            f.add(b)
            ingroup=True
        if b in f:
            f.add(a)
            ingroup=True
    if ingroup == False:
        friends.append(set([a,b]))
    
for f in friends:
    len_f=len(f)
    if len_f > mx:
        mx=len_f
#print(friends)
print(mx)

Submission status: Wrong Answer

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"

n, m=I()
people = [[] for i in range(n)]

for i in range(m):
    A,B=I()
    people[A-1].append(B-1)
    people[A-1] = list(set(people[A-1]))
    cnt = max(len(people[A-1]),cnt)

people.sort()

for i in range(len(people)-1):
    if people[i] != people[i+1]:
        ans += 1

print(max(ans,cnt+1))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = 0
def dfs(node):
    todo = set()
    for nextnode in graph[node]:
        if nextnode not in seen:
            seen.add(nextnode)
            todo.add(nextnode)
    for nextnode in todo:
        dfs(nextnode)
done = set()
while len(done) < n:
    seen = set()
    for i in range(1,n+1):
        if i not in done:
            break
    done.add(i)
    dfs(i)
    ans = max(ans,len(seen))
    done |= seen
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
graph = [[n] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    if b-1 not in graph[a-1]:
        graph[a-1].append(b-1)
    if a-1 not in graph[b-1]:
        graph[b-1].append(a-1)  # 有向グラフなら消す
max_g = 0
for g in graph:
    if len(g)>max_g:
        max_g = len(g)
print(max_g)

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    G[a - 1].add(b - 1)
    G[b - 1].add(a - 1)
d = [0] * N
Q = deque()
for i in range(N):
    if d[i] != 0:
        continue
    Q.append(i)
    d[i] = 1
    while len(Q) > 0:
        q = Q.popleft()
        for g in G[q]:
            if d[g] != 0:
                continue
            d[q] += 1
            d[g] = -1
            Q.append(g)
print(max(d))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

node = [i for i in range(n)]
r = []
for _ in range(m):
   a, b = map(int, input().split())
   a, b = a-1, b-1
   if a > b:
      a, b = b, a
   r.extend([(a, b)])
r = set(r)
r = sorted(r, key=lambda x:(x[0], x[1]))

for a, b in r:
   y = min(node[a], a)
   node[a] = y
   node[b] = y

cnt = Counter(node)
print(cnt.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
class Gr:
    def __init__(self, id):
        self.id = id

    def get_id(self):
        return self.id

    def set_id(self, id):
        self.id = id


def main():
    n, m = [int(e) for e in input().split()]
    AB = [[int(e) for e in input().split()] for i in range(m)]

    Gn = [None] * (n + 1)
    gid = 1
    for a, b in AB:
        if Gn[a] is None and Gn[b] is None:
            Gn[a] = Gr(gid)
            Gn[b] = Gn[a]
            gid += 1
        elif Gn[a] is not None and Gn[b] is None:
            Gn[b] = Gn[a]
        elif Gn[a] is None and Gn[b] is not None:
            Gn[a] = Gn[b]
        else:
            Gn[b].set_id(Gn[a].get_id())

    C = [0] * (m + 1)
    for gn in Gn:
        if gn is not None:
            C[gn.get_id()] += 1

    print(max(C))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M=map(int,input().split())
groupnumber=[0 for i in range(N)]
grouplist=[]
counter=0
maxmembers=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
    
    grouplist+=[[a,b]]
  elif groupnumber[a]==0 and groupnumber[b]!=0:
    groupnumber[a]=groupnumber[b]
    tmp=groupnumber[a]-1
    grouplist[tmp]+=[b]
    
  elif groupnumber[a]!=0 and groupnumber[b]==0:
    groupnumber[b]=groupnumber[a]
    tmp=groupnumber[b]-1
    grouplist[tmp]+=[a]
  else:
    if groupnumber[a]!=groupnumber[b]:
      tmp1=groupnumber[a]-1
      tmp2=groupnumber[b]-1
      for i in grouplist[tmp2]:
        groupnumber[i]=tmp1
      if grouplist[tmp2]!=[] and grouplist[tmp2]!=[]:
        grouplist[tmp1]+=grouplist[tmp2]
        grouplist[tmp2]=[]
for i in grouplist:
  tmp=len(i)
  if tmp>maxmembers:
    maxmembers=tmp
print(maxmembers)

Submission status: Wrong Answer

Solution code:
import itertools
n, m = map(int, input().split())
f = []
if m == 0:
  ans = 1
else:
    d = {}
    for i in range(m):
      a, b = map(int, input().split())
      if a in d:
        f[d[a]].append(b)
      elif b in d:
        f[d[b]].append(a)
      else:
        f.append([a, b])
        d[a] = len(f) - 1
        d[b] = len(f) - 1
    arr = []
    for i in range(len(f)):
      arr.append(len(list(set(f[i]))))
    ans = max(arr)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = [[] for i in range(n)]
for i in range(m):
    a,b = input().split()
    s[int(a)-1] += b
    s[int(b)-1] += a

ans = []
for i in s:
    i = set(i)
    ans.append(int(len(i)) + 1)

print(max(ans))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, m = map(int, input().split())
li = [0]*n
flag = 1
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if li[a] and li[b]:
        continue
    elif li[a] or li[b]:
        s = max(li[a], li[b])
        li[a] = s
        li[b] = s
    else:
        li[a] = flag
        li[b] = flag
        flag += 1
for i in range(len(li)):
    if li[i] == 0:
        li[i] = -i
result = Counter(li)
print(result.most_common()[0][1])

Submission status: Wrong Answer

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

members = [-1] * N

group_count = 0
groups = [0] * N
group_dict = {}
for m in range(M):
    A, B = map(int, input().split())
    A = A - 1
    B = B - 1
    if members[A]==-1 and members[B]==-1:
        members[A] = members[B] = group_count
        groups[group_count] = 2
        group_dict[group_count] = [A, B]
        group_count += 1
    
    elif members[A]!=-1 and members[B]==-1:
        members[B] = members[A]
        groups[members[A]] += 1
        group_dict[members[A]].append(B)
    
    elif members[B]!=-1 and members[A]==-1:
        members[A] = members[B]
        groups[members[B]] += 1
        group_dict[members[B]].append(A)
    
    else:
        if members[A] != members[B]:
            if len(group_dict[members[A]]) > len(group_dict[members[B]]):
                old = members[B]
                groups[members[A]] += groups[members[B]]
                groups[members[B]] = 0
                group_dict[members[A]] = group_dict[members[A]] +  group_dict[members[B]]
                for aaaaaa in group_dict[members[B]]:
                    members[aaaaaa] = members[A]
                group_dict[old] = []
            else:
                old = members[A]
                groups[members[B]] += groups[members[B]]
                groups[members[A]] = 0
                group_dict[members[B]] = group_dict[members[B]] + group_dict[members[A]]
                for bbbbbb in group_dict[members[A]]:
                    members[bbbbbb] = members[B]
                group_dict[old] = []

ans = max(groups)
if ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int, input().split()))
d = {}
newd = {}
for i in range(N):
  d[i+1] = []
  newd[i+1] = []
for i in range(M):
  A,B = list(map(int, input().split()))
  d[A].append(B)
  d[B].append(A)
#print(d)

for i in range(N):
  d[i+1] = list(set(d[i+1]))
  d[i+1] = sorted(d[i+1])

#print(d)

for i in range(N):
  if(len(d[i+1])>=2):
    for j in range(len(d[i+1])):
      for k in range(j+1,len(d[i+1])):
        newd[ d[i+1][j] ].append(d[i+1][k])
        newd[ d[i+1][k] ].append(d[i+1][j])
#print(newd)

for i in range(N):
  if(len(newd[i+1])>0):
    for j in range(len(newd[i+1])):
      if(newd[i+1][j] not in d[i+1]):
        d[i+1].append(newd[i+1][j])
#print(d)

anslist = []
for i in range(N):
  anslist.append(len(d[i+1]))
print(max(anslist)+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 = -1
print(graph)
for g in graph:
  ans = max(ans, len(set(g)))
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
readline = sys.stdin.readline

# f = [set() for _ in range(n)]

# for _ in range(m):
#     a, b = [int(i) for i in readline().split()]
#     a -= 1
#     b -= 1
#     f[a].add(b)
#     f[a] = f[a] | f[b]
#     f[b].add(a)
#     f[b] = f[b] | f[a]

# ans = 0
# for i in range(n):
#     ans = max(ans, len(f[i]))
# print(ans)

f = [set() for _ in range(n)]
ans = [1]*n
seen = [False]*n

for _ in range(m):
    a, b = [int(i) for i in readline().split()]
    a -= 1
    b -= 1
    f[a].add(b)
    f[b].add(a)


# def dfs(v, p=-1):
#     global ans
#     if seen[v]:
#         return
#     seen[v] = True
#     for u in f[v]:
#         if u == p:
#             continue
#         ans[u] += ans[v]
#         dfs(u, v)


# for i in range(n):
#     dfs(i)


q = queue.Queue()

for i in range(n):
    if not seen[i]:
        q.put(i)
        while not q.empty():
            v = q.get()
            seen[v] = True
            for u in f[v]:
                if seen[u]:
                    continue
                ans[v] += 1
                # ans[u] = ans[v]
                seen[u] = True
                q.put(u)

# print(f)
# print(*ans)
print(max(ans))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
if m == 0:
    print(2)
    import sys
    sys.exit()

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

dist = [-1]*n
from collections import deque
q = deque([])

def bfs(vert,num):
    q.append(vert)
    while q:
        v = q.popleft()
        for i in graph[v]:
            if dist[i]!=-1:
                continue
            dist[i]=num
            q.append(i)

for j in range(n):
    if dist[j]==-1:
        bfs(j,j)

dist = list(dist)
from collections import Counter
e = Counter(dist)
print(e.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

x = [[] for _ in range(N+1)]
for a, b in AB:
    x[a].append(b)
    x[b].append(a)

for row in x:
    if len(row) >= 2:
        for v in combinations(row, 2):
            x[v[0]].append(v[1])
            x[v[1]].append(v[0])

l1 = []
l2 = [0] * (N+1)
for i in range(1, N+1):
    if l2[i] == 1:
        continue
    l1.append([i])
    l2[i] = 1
    for j in range(1, N+1):
        if j == i or j in x[i] or l2[j] == 1:
            continue
        else:
            l1[-1].append(j)
            l2[j] = 1
print(len(l1))

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, m = map(int, input().split())
li = [0]*n
flag = 1
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if li[a] and li[b]:
        continue
    elif li[a] or li[b]:
        s = max(li[a], li[b])
        li[a] = s
        li[b] = s
    else:
        li[a] = flag
        li[b] = flag
        flag += 1
for i in range(len(li)):
    if li[i] == 0:
        li[i] = -i
result = Counter(li)
print(li)
print(result.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
A = np.zeros((M,2), dtype=int)

for i in range(M):
    Ai = input().split()
    
    A[i,0] = min(int(Ai[0]), int(Ai[1]))
    A[i,1] = max(int(Ai[0]), int(Ai[1]))

Asort = np.sort(A, axis=0)

Grp_lst = np.arange(1, N+1)
for i in range(M):
    Grp_lst[Asort[i,1] - 1] = min(Grp_lst[Asort[i,0] - 1], Grp_lst[Asort[i,1] - 1])

count = np.zeros(N,dtype=int)

for i in range(N):
    count[Grp_lst[i]-1] += 1

print(max(count))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
x = [[i+1] for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    x[a-1].append(a)
    x[a-1].append(b)
    x[b-1].append(a)
    x[b-1].append(b)
for i in range(n):
    x[i] = len(set(x[i]))
print(max(x))

Submission status: Wrong Answer

Solution code:
N, M=map(int,input().split())
groupnumber=[0 for i in range(N)]
grouplist=[]
counter=0
maxmembers=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
    
    grouplist+=[[a,b]]
  elif groupnumber[a]==0 and groupnumber[b]!=0:
    groupnumber[a]=groupnumber[b]
    tmp=groupnumber[a]-1
    grouplist[tmp]+=[b]
    
  elif groupnumber[a]!=0 and groupnumber[b]==0:
    groupnumber[b]=groupnumber[a]
    tmp=groupnumber[b]-1
    grouplist[tmp]+=[a]
  else:
    if groupnumber[a]!=groupnumber[b]:
      tmp1=groupnumber[a]-1
      tmp2=groupnumber[b]-1
      for i in grouplist[tmp2]:
        groupnumber[i]=tmp1
      if grouplist[tmp2]!=[] and grouplist[tmp2]!=[]:
        grouplist[tmp1]+=grouplist[tmp2]
        grouplist[tmp2]=[]
for i in grouplist:
  tmp=len(i)
  if tmp>maxmembers:
    maxmembers=tmp
print(maxmembers)
print(grouplist)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N ,M = map(int, input().split())

groups = [i for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a = a-1
    b = b-1
    if a > b:
        a, b = b, a
    groups[b] = groups[a]

group_count = Counter(groups)

max_num= 0
for group, num in group_count.items():
    if max_num < num:
        max_num = num

print(max_num)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

relations = []
for i in range(M):
    relations.append(set([int(i) for i in input().split()]))
    

def search(node,stock):
    
    n_member = 0
    
    while(len(node)>0):
        n_member += len(node)
        go_list = []
        ng_list = []
        
        for s in stock:
            if len(s & node)>0:
                go_list = np.append(go_list,list(s))
            else:
                ng_list.append(s)
        node = set(np.unique(go_list)) - node
        stock = ng_list
            
    return n_member,stock
    
    
MaxMember = 1    
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 deque

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

graph = [[] for _ in range(n+1)]

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

for i in range(n+1):
  graph[i] = list(set(graph[i]))

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

d = deque()
ans = 0

for v in range(n):
  if dist[v] != -1:
    continue
  dist[v] = 1
  d.append(v)
  #print(str(d))
  while d:
    v = d.popleft()
    #print("v:" + str(v))
    for i in graph[v]:
      #print("i:" + str(i))
      if dist[i] != -1:
        continue
      dist[v] += 1
      d.append(i)
      #print(str(d))
      
print(max(dist))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)

def li():
    return [int(x) for x in input().split()]

N, M = li()
L = []
for i in range(M):
    a, b = sorted(li())
    L.append((a, b))

L = set(L)

cnts = [0] * (N+1)

for l in L:
    a, b = l
    cnts[a] += 1
    cnts[b] += 1

ans = max(cnts) + 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n,m=map(int,input().split())
ab=[]
if m==0:
  print(1)
  sys.exit()
ab=[map(int, sorted(input().split())) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]
ans=[set(str(i)) for i in range(1,n+1)]
for i in range(m):
  ans[a[i]-1].add(str(b[i]))
print(max([len(x) for x in ans]))

Submission status: Wrong Answer

Solution code:
def solve():
    n, m = map(int, input().split())
    group = []
    done = [-1]*n
    num = 0
    for i in range(m):
        a, b = map(lambda x:int(x)-1, input().split())
        if done[a] != -1:
            if done[b] == -1:
                group[done[a]].append(b)
                done[b] = done[a]
        else:
            if done[b] == -1:
                group.append([a,b])
                done[a], done[b] = num, num
                num += 1
            else:
                group[done[b]].append(a)
                done[a] = done[b]
    people = [0]+[len(i) for i in group]
    ans = 0
    for i in range(1,len(people)):
        ans += people[i]-people[i-1]
    print(max(ans, done.count(-1)))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from collections import deque
n, m = map(int, input().split())
a = []
b = []
for i in range(m):
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)

vis = [True]*(n+1)
ans = 0
d = deque()
for i in range(m):
    if vis[a[i]]:
        d.append(a[i])
        vis[a[i]] = False
        val = 1
        while len(d) != 0:
            now = d[0]
            for j in range(m):
                if a[j] == now:
                    if vis[b[j]]:
                        d.append(b[j])
                        val += 1
                        vis[b[j]] = False
                if b[j] == now:
                    if vis[a[j]]:
                        d.append(a[j])
                        val += 1
                        vis[a[j]] = False
            d.popleft()
        ans = max(ans, val)
for i in range(m):
    if vis[b[i]]:
        d.append(b[i])
        vis[b[i]] = False
        val = 1
        while len(d) != 0:
            now = d[0]
            for j in range(m):
                if a[j] == now:
                    if vis[b[j]]:
                        d.append(b[j])
                        val += 1
                        vis[b[j]] = False
                if b[j] == now:
                    if vis[a[j]]:
                        d.append(a[j])
                        val += 1
                        vis[a[j]] = False
            d.popleft()
        ans = max(ans, val)

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
T=[set([i]) for i in range(N+1)]
AB=[list(map(int,input().split())) for _ in range(M)]
for i in range(M):
  a,b=AB[i]
  T[a].add(b)
  T[b].add(a)

unions=[[] for _ in range(N+1)]
for i in range(M):
  a,b=AB[i]
  unions[a]=(T[a].union(T[b]))
  unions[b]=(T[b].union(T[a]))

ans=0
for j in range(1,len(unions)):
  ans=max(ans,len(unions[j]))
print(ans)

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

for i in range(N):
    friends[i] = set(friends[i])

for i in range(N):
    for f in friends[i]:
        friends[i] = friends[i] | friends[f-1]

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

print(ans)

Submission status: Wrong Answer

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

par = [i for i in range(N)]

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

def unite(x, y):
  a = find(x)
  b = find(y)
  if a > b:
    par[x] = par[y]
  else:
    par[y] = par[x]
if M > 0:  
  for i in range(M):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
  
  ans = [0] * N
  Max = 0
  for i in par:
    ans[i] += 1
  for i in ans:
    if i > Max:
      Max = i
  
  print(Max)
else:
  print(1)

Submission status: Wrong Answer

Solution code:
import sys
import os

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

N,M = LI()
AB = [LI() for _ in range(M)]

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

# 無向グラフ
G = []
for _ in [0]*N:
    G.append([False]*N)

for r in AB:
    f = r[0]-1
    t = r[1]-1
    G[f][t] = True
    G[t][f] = True

used = [False] * N

ss = []
for i in range(N):
    if used[i]==True:
        continue
    used[i]=True
    
    s = set([i])
    l = [i for i, x in enumerate(G[i]) if x == True and used[i]==False]
    for j in l:
        used[j]=True
        s.add(j)
        for i,x in enumerate(G[i]):
            if x == True and used[i]==False:
                s.add(i)
    ss.append(len(s))

print(max(ss))

Submission status: Wrong Answer

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

def main():
    n, m = map(int, input().split())
    ab_arr = []
    for _ in range(m):
        ab = list(map(int, input().split()))
        ab.sort()
        ab_arr.append(ab)

    # ab_arr.sort(key=lambda ab: (ab[0], ab[1]))
    # print(ab_arr)
    f_set = [{i} for i in range(n+1)]

    for ab in ab_arr:
        a, b = ab
        f_set[a] = f_set[a] | f_set[b]
        f_set[b] = f_set[a]

    ans = 0
    for f in f_set:
        ans = max(ans, len(f))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M = (int(x) for x in input().split())

minOfGroup = list(range(N+1))

friends = []
for i in range(M):
    A,B = (int(x) for x in input().split())
    if A>B:
        A=A+B
        B = A-B
        A=A-B
    friends.append([A,B])

friends.sort()

for A,B in friends:
    minOfGroup[B] = minOfGroup[A]

cnt = [0] * (N+1)
for i in minOfGroup:
    cnt[i] = cnt[i] + 1

maxCnt = 0
for i in cnt:
    if maxCnt < i :
        maxCnt  = i

print(maxCnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
lst = list(range(1, n+1))
dic = {x:set() for x in lst}
for i in range(m):
  a,b = map(int, input().split())
  dic[a].add(b)
  for x in dic[a]:
      dic[x].add(b)
  dic[b].add(a)
  for x in dic[b]:
      dic[x].add(a)

res = len(dic[1])
for i in dic.values():
    if len(i) > res:
        res = len(i)
print(res)

Submission status: Wrong Answer

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

for i in range(M):
  A,B=map(int,input().split())
  for j in range(len(L)):
    cnt=0
    if A in L[j] or B in L[j]:
      L[j].add(A)
      L[j].add(B)
      cnt+=1
  else:
    if cnt==0:
      L.append(set())
      L[-1].add(A)
      L[-1].add(B)
      
print(len(max(L)))

Submission status: Wrong Answer

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

for _ in range(m):
    friend = tuple(map(int, input().split()))

    if len(groups) == 0:
        groups.append(set(friend))
    else:
        exist = 0
        for i, group in enumerate(groups):
            if friend[0] in group or friend[1] in group:
                if not exist:
                    groups[i] = set.union(group, set(friend))
                    exist = i
                else:
                    groups[i] = set.union(groups[i], groups[exist])
                    groups.pop(exist)
            else:
                groups.append(set(friend))

max_len = 0
for group in groups:
    max_len = max(max_len, len(group))
print(max_len)