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

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
  N, M = map(int, input().split(" "))
  checked = [False] * (N + 1)
  # frend_labels = [0] * (N + 1)
  # frend_labels_counter = [0] * (N + 1)
  num_of_friend = [0] * (N + 1)
  friends = [None] * (N + 1)

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

    if friends[A] == None and friends[B] == None:
      friends[A] = set([A, B])
      friends[B] = friends[A]
    elif friends[A] == None:
      friends[B].add(A)
      friends[A] = friends[B]
    elif friends[B] == None:
      friends[A].add(B)
      friends[B] = friends[A]
    else:
      union = friends[A] | friends[B]
      friends[A] = union
      friends[B] = union

    if len(friends[A]) > maximam_group:
      maximam_group = len(friends[A])

  # for friend in friends:
  #   print(friend)
  print(maximam_group)

if __name__ == "__main__":
  resolve()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
edges = [[] for _ in range(n)]
for a, b in AB:
    edges[a - 1].append(b)
    edges[b - 1].append(a)

ans = 0
for edge in edges:
    ans = max(ans, len(set(edge))+1)

if m == 0:ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
n,m = map(int,input().split())
if m==0:
  print(1)
  exit()
g = [-1]*n
gc = []
for i in range(m):
  a,b = map(int,input().split())
  if g[a-1]==-1 and g[b-1]==-1:
    g[a-1] = i
    g[b-1] = i
  elif g[a-1]!=-1 and g[b-1]==-1:
    g[b-1] = g[a-1]
  elif g[a-1]==-1 and g[b-1]!=-1:
    g[a-1] = g[b-1]
  elif g[a-1]!=g[b-1]:
    gc.append((g[a-1],g[b-1]))
lgc = len(gc)
if gc!=[]:
  for i in range(lgc):
    for j in range(n):
      if g[j]==gc[i][1]:
        g[j]=gc[i][0]
c = collections.Counter(g)
cnt = c.most_common()
if cnt[0][0]==-1:
  print (cnt[1][1])
else:
  print (cnt[0][1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
n,m = map(int,input().split())

d = defaultdict(list)

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

visited = [-1] + [False]*n
for i in range(m):
    a,b = map(int,input().split())
    d[a].append(b)
    d[b].append(a)
maxi = 1
for i in range(n):
    if visited[i]:
        continue
    cnt = 0
    que = deque([i])
    while que:
        v = que.pop()
        visited[v] = True
        cnt += 1
        for j in d[v]:
            if not visited[j]:
                que.append(j)
    maxi = max(maxi,cnt)
print(maxi)

Submission status: Wrong Answer

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

for i in range(m):
    a, b = map(int, input().split())
    
    if ls[a-1]== n or ls[b-1]==n:
        continue
    
    else:
      ls[a-1] += 1
      ls[b-1] += 1

print(n-max(ls))

Submission status: Wrong Answer

Solution code:
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)

group, lst = {}, {}
cnt = 1
for i in range(m):
    group_a, group_b = None, None
    if a[i] in lst:
        group_a = lst[a[i]]
    if b[i] in lst:
        group_b = lst[b[i]]
    if group_a is not None and group_b is not None and group_a != group_b:
        for _b in group[group_b]:
            lst[_b] = group_a
        group[group_a] += group[group_b]
        del group[group_b]
    elif group_a is not None and group_b is not None and group_a == group_b:
        continue
    elif group_a is not None and group_b is None:
        lst[b[i]] = group_a
        group[group_a].append(b[i])
    elif group_a is None and group_b is not None:
        lst[a[i]] = group_b
        group[group_b].append(a[i])
    else:
        group_name = f'g_{cnt}' 
        lst[a[i]], lst[b[i]] = group_name, group_name
        group[group_name] = [a[i], b[i]]
        cnt += 1
if m != 0:
    print(max([len(s[1]) for s in group.items()]))
else:
    print(n)

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))
n = a[0]
m = a[1]

if m != 0:
  ab = [map(int, input().split()) for _ in range(m)]
  a, b = [list(i) for i in zip(*ab)]
  
  edge = [[0 for j in range(n)] for i in range(n)]
  for i in range(m):
    edge[a[i]-1][b[i]-1] = 1
    edge[b[i]-1][a[i]-1] = 1

  #print(set_list)

  ans = 1
  for i in range(n):
    aa = max(edge[i])
    ans = max(aa,ans)

  print(ans)
else:
  print(1)

Submission status: Wrong Answer

Solution code:
from collections import deque
class Node:
    def __init__(self):
        self.friends = {}
        self.checked = False
    def add(self, b):
        self.friends[b] = True
N, M = [int(i) for i in input().split()]
P = [Node() for i in range(N)]
for i in range(M):
    A, B = [int(i)-1 for i in input().split()]
    P[A].add(B)
    P[B].add(A)

counter = 0
for i in range(N):
    if P[i].checked == False:
        d = deque([i])
        counter += 1
    else:
        continue
    while d:
        q = d.popleft()
        P[q].checked = True
        for key in P[q].friends.keys():
            if P[key].checked == False:
                d.append(key)
            for j in P[key].friends.keys():
                if P[key].checked == False:
                    d.append(j)
print(counter)

Submission status: Wrong Answer

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

s=[]
for i in range(m):
  a,b=map(int,input().split())
  if (a,b) not in s and (b,a) not in s:
    s.append((a,b))
s.sort()
#print(s)
d=[[0]*n for i in range(n)]
for i in s:
  d[i[0]-1][i[1]-1]+=1
  d[i[0]-1][i[0]-1]+=1
  d[i[1]-1][i[0]-1]+=1
  d[i[1]-1][i[0]-1]+=1
ans=0
for i in range(n):
  f=sum(d[i])
  ans=max(ans,f)
print(ans-1)

Submission status: Wrong Answer

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

mx=0
friends={}

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

for i in range(m):
    ab=input('').split()
    a = int(ab[0])
    b = int(ab[1])
    friends[a].add(b)
    friends[b].add(a)
    for f in friends[a]:
        friends[f].add(b)
        friends[b].add(f)
    for f in friends[b]:
        friends[f].add(a)
        friends[a].add(f)

for f in friends.values():
    len_f=len(f)
    if len_f > mx:
        mx=len_f
#print(friends)
print(mx)

Submission status: Wrong Answer

Solution code:
N , M = map(int,input().split())
g = [[] for i in range(N)]
for i in range(M):
  a , b = map(int,input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)
m = 0
for i in range(N):
  tg = list(g[i])
  for j in tg:
    g[i].extend(g[j])
for i in range(N):
  tg = list(g[i])
  for j in tg:
    g[i].extend(g[j])
for i in range(N):    
  l = len(set(g[i]))
  if m < l:
    m = l
print(m+1)

Submission status: Wrong Answer

Solution code:
import sys

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

if M==0:
    print(1)
    sys.exit()
    
friends = [[0]*N]*N

for _ in range(M):

    A_i, B_i = map(int, input().split())
    friends[A_i-1][B_i-1] = 1

    friends[B_i-1][A_i-1] = 1

ans_list = []

for rows in friends:
    ans_list.append(sum(rows))

ans = max(ans_list)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N,M= map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    aw, we = map(int, input().split())
    A[i]=min(aw,we)
    B[i]=max(aw,we) 
a=[]
for i in range(N):
    a.append(i+1)
    
for i in range(M):
    #print(a[B[i]-1],A[i])
    a[B[i]-1]=min(a[B[i]-1],A[i])
for i in range(N):
    a[i]=a[a[i]-1]
c = collections.Counter(a)
print(c.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

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


group_dict = defaultdict(lambda : None)
group_counter = 0
group_member = [0]*(n+1)

update_dict = defaultdict(lambda : None)

group = []
for i in range(m):
    a,b = friend_list[i]

    a_group = group_dict[a]
    b_group = group_dict[b]
    target_group = -1
    if a_group != None:
        target_group = a_group
    if b_group != None:
        target_group = b_group

    if target_group == -1:
        target_group = group_counter
        group_counter+=1

    if a_group != None and b_group != None:
        target_group = min(a_group,b_group)
        update_dict[max(a_group,b_group)] = min(a_group,b_group)
        update_dict[min(a_group,b_group)] = max(a_group,b_group)
    
    group_dict[a] = target_group
    group_dict[b] = target_group

for k in group_dict:

    new_k = update_dict[group_dict[k]]
    prev = None
    test = set()
    while (not new_k in test) and prev != new_k and new_k != None:
        test.add(new_k)
        prev = new_k
        new_k = update_dict[new_k]
    if prev != None:
        change = min(test)
    else:
        change = group_dict[k]
    group_member[change] += 1

print(max(group_member))

Submission status: Wrong Answer

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

n,m=map(int,input().split())
p = [tuple(sorted(list(map(int,input().split())))) for ii in range(m)]
p=set(p)

m=len(p)

g=[-1]*(n+1)
r=0

p2=list()

rr=[2]

import numpy as np
for pii in p:
  if g[pii[0]]<0 and g[pii[1]]<0:
    g[pii[0]]=r
    g[pii[1]]=r
    if r>0:
      rr.append(2)
    r+=1
  elif g[pii[0]]>=0 and g[pii[1]]>=0:
    g0=g[pii[0]]
    g1=g[pii[1]]
    if g0!=g1:
      p2.append((g[pii[0]],g[pii[1]]))
  elif g[pii[0]]>=0:
    g[pii[1]]=g[pii[0]]
    rr[g[pii[0]]]+=1
  elif g[pii[1]]>=0:
    g[pii[0]]=g[pii[1]]
    rr[g[pii[1]]]+=1

for p2ii in p2:
  g0=g[p2ii[0]]
  g1=g[p2ii[1]]
  rr[g1]+=rr[g0]
  rr[g0]=0

#print(rr)
print(max(rr))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
F = {}
for _ in range(M):
    A, B = map(int, input().split())
    if not A in F.keys():
        F[A] = []
    if not B in F.keys():
        F[B] = []
    if A in F.keys():
        F[A].append(B)
    if B in F.keys():
        F[B].append(A)
if F.keys() == 0:
    print(1)
else:
    ans = 1
    for f in F.values():
        ans = max(ans, len(list(set(f)))+1)
    print(ans)

Submission status: Wrong Answer

Solution code:

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

line = []
graph = [[] for _ in range(n)]

for i in range(m):
    ai, bi = list(map(int, input().split(" ")))
    ai -= 1
    bi -= 1
    graph[ai].append(bi)
    graph[bi].append(ai)


class DFS:

    def __init__(self):
        pass

    @staticmethod
    def dfs(start):
        max_size = 0
        size = 1
        stack = [start]
        startkouho = [i for i in range(n)]
        tansaku_zumi = set([start])
        while stack:
            ai = stack[-1]
            if ai in startkouho:
                startkouho.remove(ai)
            if graph[ai]:
                bi = graph[ai].pop()
                if bi not in tansaku_zumi:
                    stack.append(bi)
                    size += 1
                    tansaku_zumi.add(bi)
            else:
                stack.pop()
            if not stack:
                max_size = max(max_size, size)
                size = 1
                if startkouho:
                    stack.append(list(startkouho)[0])
        return max_size

ans = 0
print(DFS.dfs(0))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
par=[i for i in range(N+1)]
size=[1 for i in range(N+1)]
def find(x):
    if x!=par[x]:
        par[x]=find(par[x])
    return par[x]
def union(x,y):
    if find(x)!=find(y):
        par[y] = par[x]
        size[x] += size[y]
res=N
for i in range(M):
    s,e=map(int,input().split())
    union(s,e)
c=0
for i in range(len(par)):
    if par[i]==i and size[i]!=1:

        c+=size[i]
print(c-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
relationship = []
reldict = {}
counter = [0]*(N+1)
refer = [0]*(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    if str(a) not in reldict:
        if str(b) not in reldict:
            reldict[str(a)] = 1
            reldict[str(b)] = 2
            refer[a] = a
            refer[b] = a
            counter[a] = 2

        elif str(b) in reldict:
            counter[refer[b]] += 1
            reldict[a] = counter[refer[b]]
            refer[a] = refer[b]

    elif str(a) in reldict:
        if str(b) not in reldict:
            counter[refer[a]] += 1
            reldict[b] = counter[refer[a]]
            refer[b] = refer[a]


        elif b in reldict:
            pass

#print(reldict)
print(max(counter))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
friends_set=set()
for i in range(M):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    friends_set.add((a,b)) 
    
friends_list=[[] for _ in range(N+1)]

for f in friends_set:
    friends_list[f[0]].append(f[1])
    friends_list[f[1]].append(f[0])

max_len=0
for i in friends_list:
    max_len=max(max_len,len(i)+1)
    
print(max_len)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m = map(int,input().split())
l = [set([]) for i in range(n+1)]
for i in range(m):
  a,b = map(int,input().split())
  l[a].add(b)
  l[b].add(a)
Q = deque()
for i in range(n):
  Q.append(i+1)
vis = [-1]*(n+1)
vis[1] = 1
while Q:
  temp = Q.popleft()
  if vis[temp]==-1:
    vis[temp] = 1
  for v in l[temp]:
    if vis[v]!=-1:
      continue
    vis[temp] += 1
    vis[v] = vis[temp]
    Q.appendleft(v)
print(max(vis))

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
n,m = map(int, input().split())

q = [0]*(n+1)

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)

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

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

d = deque()
a = 0
for l,j in enumerate(q):
    b = set()
    if j == 0:
        d.append(l)
        while d:
            v = d.popleft()
            b.add(v)
            for i in graph[v]:
                b.add(i)
                if dist[i] != -1:
                    continue
                dist[i] = dist[v] + 1
                d.append(i)
                q[i] = -1
        a = max(a,len(b))
print(a)

Submission status: Wrong Answer

Solution code:
N,M=input().split()
N,M=int(N),int(M)
A,B=[0]*M,[0]*M
for i in range(M):
  t,s=input().split()
  #print(t,s)
  A[i]=int(t)-1
  B[i]=int(s)-1
group=[0]*N
R=0
grcnt=0
index=[]
for i in range(M):
  if group[A[i]]==0 and group[B[i]]==0:
    group[A[i]],group[B[i]]=grcnt,grcnt
    index.append([A[i],B[i]])
    grcnt+=1
  elif group[A[i]]==0:
    group[A[i]]=group[B[i]]
    index[group[B[i]]].append(A[i])
  elif group[B[i]]==0:
    group[B[i]]=group[A[i]]
    index[group[A[i]]].append(B[i])
  else:
    for j in index[group[B[i]]]:
      group[j]=group[A[i]]
      index[group[A[i]]].append(j)
      
r=[0]*(grcnt+1)
for i in range(len(group)):
  r[group[i]]+=1
print(max(r))
#print(group)

Submission status: Wrong Answer

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

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

A_set = set()
A = []
B = []
for i in range(M):
    a, b = map(int, input().split())
    if (a == b):
        exit
    if (a < b):
        A_set.add(a)
        A.append(a)
        B.append(b)
    else:
        A_set.add(b)
        A.append(b)
        B.append(a)


count = 0
member = []
for a in A_set:
    group = set()
    group.add(a)
    for i in range(len(A)):
        if (A[i] == a):
            group.add(B[i])    
    member.append(len(group))
    count = count + 1

print(max(member))

Submission status: Wrong Answer

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

for i in range(m):
    a, b = ab[i]
    fl = True
    for j in range(len(li)):
        if a in li[j]:
            li[j].append(b)
            fl = False
        elif b in li[j]:
            li[j].append(a)
            fl = False
    if fl:
        li.append(ab[i])

ans = 0

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

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

not_friend_graph = defaultdict(set)
for a, b in R:
    not_friend_graph[a].add(b)
    not_friend_graph[b].add(a)

max_n = 0
max_i = 0
for i in range(N):
    if len(not_friend_graph) > max_n:
        max_n = len(not_friend_graph[i])
        max_i = i

def dfs_stack(start, visited=None):
    stack = [start]
    visited = set()

    while stack:
        current_vertex = stack.pop()
        if current_vertex not in visited:
            visited.add(current_vertex)
            for v in not_friend_graph[current_vertex]:
                if v not in visited:
                    stack.append(v)
    return visited

visited = dfs_stack(max_i)
print(len(visited))

Submission status: Wrong Answer

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

friends = [0]*n
group = [-1]*n

for a, b in ab:
    if a > b:
        a, b = b, a
    a -= 1
    b -= 1
    if group[a] == -1 and group[b] == -1:
        group[a] = a
        group[b] = a
        friends[a] += 2
    elif group[a] != -1 and group[b] != -1:
        group[b] = group[a]
        friends[group[a]] += friends[group[b]]
    elif group[a] == -1:
        group[a] = group[b]
        friends[group[b]] += 1
    elif group[b] == -1:
        group[b] = group[a]
        friends[group[a]] += 1

print(max(friends))

Submission status: Wrong Answer

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

l = [[] for i in range(N)]
for _ in range(M):
    AB = list(map(int,input().split()))
    if AB[0] < AB[1]:
        A = AB[0]
        B = AB[1]
    else:
        A = AB[1]
        B = AB[0]
    if B-1 not in l[A-1]:
        l[A-1].append(B-1)

mi = float('inf')
ma = 0
for i in l:
    if len(i) != 0:
        mi = min(mi,len(i))
print(mi + 2)

Submission status: Wrong Answer

Solution code:
#abc177_D_2_特定のnが特定のlistに含まれることを確認するまで、iter
int_n, int_m = map(int, input().split())
list_agg = list()
for i in range(int_m):
  list_tmp = list(map(int, input().split()))
  list_agg.append(list_tmp)

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

flag = 100
list_agg_tmp = list_agg
while flag <= 1:
  list_set_agg = list()
  flag = 0
  for iter_n in range(1, int_n+1):
    list_tmp_add = list()
    n_flag = 0
    for i_list in list_agg_tmp:
      if iter_n in i_list:
        list_tmp_add = list_tmp_add + i_list
        n_flag = n_flag + 1
    if n_flag > flag:
      flag = n_flag
    list_set_agg.append(list(set(list_tmp_add)))
  list_agg_tmp = get_unique_list(list_set_agg)
    
int_max_len = 0
for i in list_agg_tmp:
  if len(i) > int_max_len:
    int_max_len = len(i)
    
print(int_max_len)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
if M == 0:
    print(1)
else:
    D = {}
    count = 0
    friends = []
    while count < M:
        A, B = map(int,input().split())
        if A not in D and B not in D:
            friends += [[A,B]]
            D[A] = len(friends) - 1
            D[B] = len(friends) - 1
        elif A in D and B not in D:
            friends[D[A]] += [B]
            D[B] = D[A]
        elif B in D and A not in D:
            friends[D[B]] += [A]
            D[A] = D[B]
        count += 1
    print(max(len(f) for f in friends))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
connect = []
ls = [0 for _ in range(N)]
flg = 1
count = [0 for _ in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    if ls[a-1] == 0 and ls[b-1] == 0:
        ls[a-1]=flg
        ls[b-1]=flg
        count[flg] +=2
        flg+=1
    elif ls[a-1] == 0:
        ls[a-1] = ls[b-1]
        count[ls[b-1]] +=1
    elif ls[b-1] == 0:
        ls[b-1] = ls[a-1]
        count[ls[a-1]] +=1
    else:
        check = [ls[a-1],ls[b-1]]
        connect.append(check)
connect.sort()
for j in connect:
    count[min(j)] += count[max(j)]
    count[max(j)] = 0
print(max(count))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
 
fri = []
chain = []
 
for i in range(M):
  fri.append( list(map(int, input().split())) )
 
 
for fr in fri:
  frag = False
  for i,ch in enumerate(chain):
    if fr[0] in ch and fr[1] not in ch:
      chain[i].append(fr[1])
      frag = True
      break
    elif fr[1] in ch and fr[0] not in ch:
      chain[i].append(fr[0])
      frag = True
      break
      
  if not(frag):
    chain.append(fr)

max = 0
for ch in chain:
  if len(ch)>max:
    max = len(ch)

print(max)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
have = [{i} for i in range(N)]

for m in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    have[a] |= have[b]
    have[b] = have[a]

ans = 0
for h in have:
    ans = max(ans, len(h))

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
abm = [list(map(int, input().split())) for _ in range(m)]
abm = set(tuple(sorted(item)) for item in abm)
edges = {}
for a, b in abm:
    if a not in edges:
        edges[a] = [b]
    else:
        edges[a].append(b)
    if b not in edges:
        edges[b] = [a]
    else:
        edges[b].append(a)

import collections
vis = [False for _ in range(n + 1)]
gr = {}
def create_group(s):
    if vis[s]:
        return None
    
    deq = collections.deque()
    deq.append(s)
    group = []
    while len(deq):
        node = deq.popleft()
        if vis[node]:
            continue
        group.append(node)
        vis[node] = True
        for e in edges.get(node, []):
            deq.append(e)

    for g in group:
        gr[g] = s
    return group


groups = [create_group(i) for i in range(1, n + 1)]
#print(groups)
groups = list(filter(lambda x:x, groups))
#print(groups)
groupmap = {g[0]:g for g in groups}
#print(gr)
#print(groupmap)

class Cluster:
    def __init__(self, s):
        self.node_list = [s]
        self.group_set = set([gr[s]])
    def __str__(self):
        return 'Cluster(node_list={}, group_set={})'.format(self.node_list, self.group_set)

clusters = [Cluster(i) for i in range(1, n + 1)]
    
nc = len(clusters)
while True:
    merged = set()
    new_clusters = []
    for i in range(len(clusters)):
        if i in merged:
            continue
        c1 = clusters[i]
        for j in range(i + 1, len(clusters)):
            c2 = clusters[j]
            if c1 == c2:
                continue
            # マージ可能か = グループが重なっていない
            intersect = c1.group_set.intersection(c2.group_set)
            if len(intersect) == 0:
                #print(i, j, "をマージ")
                # マージ可能
                union = c1.group_set.union(c2.group_set)
                
                new_cluster = Cluster(1)
                new_cluster.node_list = c1.node_list + c2.node_list
                new_cluster.group_set = union

                new_clusters.append(new_cluster)

                merged.add(j)
                break
        else:
            new_clusters.append(c1)
    

    nc_new = len(new_clusters)
    if nc == nc_new:
        break
    nc = nc_new
    clusters = new_clusters
print(nc)

Submission status: Wrong Answer

Solution code:
def main():
    N,M = map(int,input().split())
    A = [[0,0] for i in range(M)]
    for i in range(M):
        A[i] = list(map(int,input().split()))
        list.sort(A[i])
    
    list.sort(A)
    
    List = [-1 for i in range(N)]
    List2 = [[] for i in range(N)]
    host = 0
    guest = 0
    for i in range(M):
        a = A[i][0]-1
        b = A[i][1]-1
        if List[a] == -1 and List[b] == -1:
            host = a
            guest = b
            List[host] = host
            List2[host].append(host)
            List[guest] = host
            List2[host].append(guest)
        elif List[a] != -1 and List[b] != -1 and List[a] != List[b]:
            host = List[a]
            guest = b
            for l in List2[List[b]]:
                List[l] = host
            List[guest] = host
            List2[List[a]].extend(List2[List[b]])
            List2[host].append(guest)
            List2[List[b]] = []
        elif List[a] != -1:
            host = List[a]
            guest = b
            List[guest] = host
            List2[host].append(guest)
        elif List[b] != -1:
            host = List[b]
            guest = a
            List[guest] = host
            List2[host].append(guest)
        
    ans = [0 for i in range(N)]
    for i in range(N):
        L = List[i]
        if L != -1:
            ans[L] += 1
            
    print(max(ans))
        
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import copy
N,M=map(int,input().split())
A=[0]*M
tomo=[ [] for i in range(N)]
for i in range(M):
    A[i]=list(map(int,input().split()))
    if(A[i][1]<A[i][0]):
        temp=A[i][1]
        A[i][1]=A[i][0]
        A[i][0]=temp
A=list(map(list,set(map(tuple,A))))

for i in range(len(A)):
    #print(tomo)
    #print(A[i][0]-1)
    tomo[A[i][0]-1].append(A[i][1])

    tomo[A[i][1]-1].append(A[i][0])
    #print(tomo)


for i in range(N):

    #print(i)
    for j in tomo[i]:

        tem=copy.deepcopy(tomo[j-1])
        #print(tem)
        tem.extend(tomo[i])

        tem=list(set(tem))

        tomo[i]=tem

ans=0

for i in range(len(tomo)):
    ans=max(ans,len(tomo[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy

N, M = map(int, input().split())
R = numpy.array([[int(r) for r in input().split()] for _ in range(M)]) - 1

size = [1] * N

groups = numpy.array([-1] * N)
gnum = 1
sameinfo = []

for p1, p2 in R:

    g1 = groups[p1]
    g2 = groups[p2]

    if g1 == -1 and g2 == -1:
        groups[p1] = gnum
        groups[p2] = gnum
        gnum += 1

    elif g1 != -1 and g2 == -1:
        groups[p2] = g1

    elif g1 == -1 and g2 != -1:
        groups[p1] = g2

    elif g1 != -1 and g2 != -1:
        sameinfo.append([min(g1, g2), max(g1, g2)])
    
    elif g1 == g2:
        continue

for s1, s2 in sameinfo:
    groups[groups == s2] = s1

groups = groups[groups != -1]
a = numpy.bincount(groups)
if len(a) == 0:
    print(N)
else:
    maxgroup = numpy.argmax(a)
    print(numpy.count_nonzero(groups == maxgroup))

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)

d = deque()
vis = [True]*(n+1)

def bfs(num):
    for i in range(m):
        if a[i] == num:
            if vis[b[i]]:
                d.append(b[i])
                vis[b[i]] = False
        if b[i] == num:
            if vis[a[i]]:
                d.append(a[i])
                vis[a[i]] = False

ans = 0
for i in range(m):
    if vis[a[i]]:
        d.append(a[i])
        vis[a[i]] = False
        val = 0
        while len(d) != 0:
            val += 1
            num = d[0]
            bfs(num)
            d.popleft()
        ans = max(ans, val)
    if vis[b[i]]:
        d.append(b[i])
        vis[b[i]] = False
        val = 0
        while len(d) != 0:
            val += 1
            num = d[0]
            bfs(num)
            d.popleft()
        ans = max(ans, val)
print(ans)

Submission status: Wrong Answer

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

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

# print(AB)

class UnionFind: # with rank
    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
        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

uf = UnionFind(n)
for a, b in AB:
    uf.union(a, b)
# for v in range(1,n+1):
#     print('find(v) {}'.format(uf.find(v)))

m = {}
for g in uf.par:
    if not g in m:
        m[g] = 0
    m[g] += 1

# print('uf {}'.format(uf.par))
# print(*m.items(),sep='\n')

ans = max(m.values())
print(ans)

Submission status: Wrong Answer

Solution code:
N , M = map(int,input().split())
g = [[] for i in range(N)]
for i in range(M):
  a , b = map(int,input().split())
  a -= 1
  b -= 1
  g[a].append(b)
  g[b].append(a)
m = 0
for i in range(N):
  tg = list(g[i])
  for j in tg:
    g[i].append(j)
for i in range(N):
  tg = list(g[i])
  for j in tg:
    g[i].append(j)
for i in range(N):    
  l = len(set(g[i]))
  if m < l:
    m = l
print(m+1)

Submission status: Wrong Answer

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

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

for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    friends[a].add(b)
    friends[b].add(a)

friend_groups = set()
checked = []

for i, f in friends.items():
    group = set(f)
    for n in f:
        for friend in friends[n]:
            group.add(friend)
    friend_groups.add(tuple(group))

counts = []
for group in friend_groups:
    counts.append(len(group))

print(max(counts))

Submission status: Wrong Answer

Solution code:
N, M = [ int(v) for v in input().split(" ") ]
r = [0]*N

cache = []
for i in range(M):
  A, B = [ int(v) for v in input().split(" ") ]
  if set([A,B]) in cache:
    continue
  r[A-1] += 1
  r[B-1] += 1
  cache.append(set([A,B]))

#print(cache)
#print(r)
print(max(set(r))+1)