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

    
    friend = set([a,b])
    a_group = group_dict[a]
    b_group = group_dict[b]
    target_group = -1
    if a_group != None:
        target_group = a_group
        group[a_group] = group[a_group].union(friend)
    if b_group != None:
        target_group = b_group
        group[b_group] = group[b_group].union(friend)

    
    if target_group == -1:
        target_group = group_counter
        group.append(friend)
        group_counter+=1
    if a_group != None and b_group != None:
        group[a_group] = group[a_group].union(group[b_group])
        group[b_group] = group[b_group].union(group[a_group])
        target_group = min(a_group,b_group)
        update_dict[max(a_group,b_group)] = min(a_group,b_group)
    
    group_dict[a] = target_group
    group_dict[b] = target_group
ans = -1
for k in group:
    ans = max(ans,len(k))
print(ans)

Submission status: Wrong Answer

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

for _ in range(m):
    a, b = map(int, input().split())
    g[a - 1].add(b - 1)
    g[b - 1].add(a - 1)


visited = [False]*n
ans = 0
for i in range(n):
    if not visited[i] and i in g:
        # cc = []
        count = 1
        q = deque([i])
        visited[i] = 1
        while q:
            node = q.popleft()
            for nbr in g[node]:
                if not visited[nbr]:
                    q.append(nbr)
                    visited[nbr] = True
                    count += 1
            
        # ans = max(ans, len(cc))
        ans = max(ans, count)

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    N, M = [int(item) for item in input().split()]

    edges = [[int(item) for item in input().split()] for _ in range(M)]
    links = [set() for _ in range(N+1)]

    res_list = [set() for i in range(N+1)]

    for a, b in edges:
        links[a].add(a) 
        links[a].add(b)
        links[b].add(a)
        links[b].add(b)

    max_num = 0
    for item in links:
        max_num = max(max_num, len(item))

    print(max_num)

        


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from sys import exit, stdin

input = stdin.readline
import copy
from collections import deque, Counter

# import numpy as np


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

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


D = [-1] * N
tmp = 0
for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    if D[a] == -1 and D[b] == -1:
        D[a] = tmp
        D[b] = tmp
        tmp += 1
    elif D[a] == -1 and D[b] != -1:
        D[a] = D[b]
    elif D[a] != -1 and D[b] == -1:
        D[b] = D[a]
    elif D[a] != D[b]:
        for k in range(N):
            if D[k] == D[b]:
                D[k] = a


R = Counter(D)
ans = R.most_common(2)
if ans[0][0] == -1:
    print(ans[1][1])
else:
    print(ans[0][1])

Submission status: Wrong Answer

Solution code:
def resolve():
  N, M = map(int, input().split(" "))
  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]
      for friend in union:
        friends[friend] = 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:
from collections import deque
N,M = map(int,input().split())
graph = []
fship = []
for i in range(M):
    x,y = map(int,input().split())
    if x>y:
        x,y = y,x
    fship.append([x-1,y-1])
fship.sort(key = lambda x: x[0])
graph = [[] for _ in range(N)]
for i in fship:
    graph[i[0]].append(i[1])

dist = [None]*N
ans = -1

for i in range(N):
    if dist[i]:
        continue
    dist[i] = True
    tmp = 0
    d = deque()
    d.append(i)
    while d:
        v = d.popleft()
        for i in graph[v]:
            if dist[i]:
                continue
            dist[i] = True
            d.append(i)
            tmp += 1
    ans = max(ans,tmp)
print(ans+1)

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:
            D[A] = len(friends)
            D[B] = len(friends)
            friends += [{A,B}]
        elif A in D and B not in D:
            friends[D[A]] = friends[D[A]].union({B})
            D[B] = D[A]
        elif B in D and A not in D:
            friends[D[B]] = friends[D[B]].union({A})
            D[A] = D[B]
        count += 1
    print(max(len(f) for f in friends))

Submission status: Wrong Answer

Solution code:
import sys,os
import math
from fractions import Fraction 
from collections import defaultdict
from random import randint

# sys.stderr=open('err.txt','w')
# sys.stdout=open('output.txt','w')
# sys.stdin=open('input.txt','r')

def linput():
    return list(minput())

def minput():
    return map(int, sys.stdin.readline().strip().split())

###############################################################

def make_set(a):
    parent[a]=a

def find_set(a):
    while a!=parent[a]:
        parent[a]=parent[parent[a]]
        a=parent[a]
    return a

def union_set(a,b):
    x=find_set(a)
    y=find_set(b)
    if x==y:
        return
    else:
        parent[y]=parent[x]

n,m=minput()
parent=[0]*n
for i in range(n):
    make_set(i)
ans=0
for i in range(m):
    x,y=minput()
    if x>y:
        x,y=y,x
    x=x-1
    y=y-1
    union_set(x,y)
# print(parent)
di = defaultdict(int)
for i in parent:
    di[i]+=1
# print(di)
for k,v in di.items():
    ans=max(ans,v)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
friends_set_list = [set() for i in range(N+1)]
# friends_subset_list = [set() for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    friends_set_list[A].add(B)
    friends_set_list[B].add(A)
    friends_set_list[A] |= friends_set_list[B]
    friends_set_list[B] |= friends_set_list[A]
ans = 0 
for i in range(N):
    # friends_set_list[i] |= friends_subset_list[i]
    num = len(friends_set_list[i])
    if num > ans:
        ans = num

print(ans)

Submission status: Wrong Answer

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

ad_sum_array = [0] * n
set_ad = set()

for ab in ab_array:
    a, b = ab
    if not (a, b) in set_ad:
        set_ad.add((a, b))
        set_ad.add((b, a))
        ad_sum_array[a - 1] += 1
        ad_sum_array[b - 1] += 1

print(max(ad_sum_array) + 1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
#import numpy as np
import math
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def solve():
    return

if __name__=='__main__':
    n,m = IL()
    grouplist = []
    for _ in range(m):
        a,b = IL()
        flag = True
        buff = set()
        for groups in grouplist[:]:
            if a in groups or b in groups:
                groups.add(a)
                groups.add(b)
                flag = False
                buff |= groups
                grouplist.remove(groups)

        if 0<len(buff):
            grouplist.append(buff)

        if flag:
            grouplist.append({a,b})

    ans = 0
    for rep in grouplist:
        ans = max(ans,len(rep))

    print(ans)

    solve()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
hint_list = [list(map(int,input().split())) for i in range(M)]
friend_list = []

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

hint_list = get_unique_list(hint_list)

if M == 0:
    print(N)
else:
    friend_list.append(hint_list[0])
    for i in range(1,len(hint_list)):
        for j in range(len(friend_list)):
            if hint_list[i][0] in friend_list[j]:
                if hint_list[i][1] in friend_list[j]:
                    pass
                else:
                    friend_list[j].append(hint_list[i][1])
            elif hint_list[i][1] in friend_list[j]:
                if hint_list[i][0] in friend_list[j]:
                    pass
                else:
                    friend_list[j].append(hint_list[i][0])
            else:
                pass

    friend_length = []

    for i in range(len(friend_list)):
        friend_length.append(len(friend_list[i]))

    print(max(friend_length))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


def LI():
    return list(map(int, input().split()))


N, M = LI()
friend = [set() for _ in range(N)]
ans = 0
miru = set()
if M == 0:
    print(0)
    sys.exit()
for i in range(M):
    a, b = map(int, input().split())
    friend[a-1].add(b-1)
    friend[b-1].add(a-1)
    miru.add(a-1)
    miru.add(b-1)
looked = [0]*N
d = deque()
count = 1
d.append(a-1)
miru.discard(a-1)
while d:
    x = d.pop()
    for i in friend[x]:
        if looked[i] != 0:
            continue
        count += 1
        looked[i] = 1
    if len(d) == 0:
        ans = max(count, ans)
        if len(miru) == 0:
            break
        y = miru.pop()
        d.append(y)
        looked[y] = 1
        count = 1
        miru.discard(y)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
par = [i for i in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
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 = map(int, input().split())

tree = [[] for i in range(n+1)]
colors = [0 for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    if not a in tree[b]:
        for j in range(len(tree[a])):
            if not tree[a][j] in tree[b]:
                tree[tree[a][j]].append(b)
                tree[b].append(tree[a][j])
        tree[a].append(b)
        for j in range(len(tree[b])):
            if not tree[b][j] in tree[a]:
                tree[tree[b][j]].append(a)
                tree[a].append(tree[b][j])
        tree[b].append(a)


for i in range(1, n+1):
    color = 1
    color_list = []
    for j in range(len(tree[i])):
        color_list.append(colors[tree[i][j]])
    while True:
        if not color in color_list:
            colors[i] = color
            break
        color += 1
        
print(max(colors))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[92]:


N,M = map(int, input().split())
AB = []
for _ in range(M):
    A,B = map(int, input().split())
    A -= 1; B -= 1
    AB += [[A,B]]


# In[93]:


def func(friends,a,b):
    if b not in friends[a]:
        friends[a] += [b]
        for x in friends[b]:
            func(friends,a,x)


# In[94]:


friends = {}
for i in range(N):
    friends[i] = []
for a,b in AB:
    func(friends,a,b)
    func(friends,b,a)
ans = 0
for i,mylist in friends.items():
    ans = max(ans,len(mylist))
print(ans)


# In[ ]:

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(1,n+1):
    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:
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, m = LI()
    friends = [[] for i in range(n)]
    for i in range(m):
        a, b = LI()
        if not b in friends[a - 1]:
            friends[a - 1].append(b)
        if not a in friends[b - 1]:
            friends[b - 1].append(a)
    lst = [int(x) for x in range(1, n + 1)]
    groups = []
    for p in lst:
        flg2 = 1
        for group in groups:
            flg = 1
            for g in group:
                for f in friends[g - 1]:
                    if p in friends[f-1]:
                        flg = 0
                        break
                    if flg:
                        break
            if flg:
                group.append(p)
                flg2 = 0
                break
        if flg2:
            groups.append([p])
    print(len(groups)+1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

teams = {}
for i in range(N):
  teams[i+1] = i+1

if M == 0:
  print(1)
else:
  for i in range(M):
    a, b = map(int, input().split())
    fa = min(a,b)
    fb = max(a,b)
    if (teams[fa] != teams[fb]):
      teams[fb] = teams[fa]
  teams_inv = {}
  for k, v in teams.items():
    if v not in teams_inv.keys():
      teams_inv[v] = 1
    else:
      teams_inv[v] += 1
  print(max(teams_inv.values()))

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(0)

Submission status: Wrong Answer

Solution code:
import copy

n,m = map(int,input().split())
f = []

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

nf = []

for i in range(len(f)):
    cf = set()
    cf.add(f[i][0])
    cf.add(f[i][1])
    for j in range(i+1,len(f)):
        if f[i][0] in f[j]:
            cf.add(f[j][0])
            cf.add(f[j][1])
        elif f[i][1] in f[j]:
            cf.add(f[j][0])
            cf.add(f[j][1])
    nf.append(cf)

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


print(ans)

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:
            D[A] = len(friends)
            D[B] = len(friends)
            friends += [[A,B]]
        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:
import math
import collections
import fractions
import itertools
import functools
import operator
import bisect

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]
    print(max(people))
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

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

for i in range(n):
    a = groups[i]
    for j in set(groups[i]):
        a += groups[j-1]
    ans = max(len(set(a)), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n,m = map(int, input().split())
g = [[0] for i in range(n+1)]
for i in range(m):
  a, b = map(int, input().split())
  g[b] = g[a]
  g[b][0] = i
  
g2 = [0 for i in range(n)]
for i in range(n)[1:]:
  g2[i-1] = g[i][0]
  
c = Counter(g2)
print(c.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
##https://tjkendev.github.io/procon-library/python/union_find/union_find.html
from collections import Counter
N = 2*10**5
 
*p, = 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)
    
    tmp = Counter(p)
    print(max(tmp.values()))
    
 
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

I = [-1] * (n+1)
x = [[]]
for _ in range(m):
    a,b = map(int, input().split())
    if (I[a]!=-1 and I[b]!=-1) or a == b: continue

    if x == [[]]:
        x[0] += [a,b]
        I[a]=I[b]=0
    else:
        if I[a]==-1 and I[b]==-1:
            x.append([a,b])
            I[a]=I[b] = len(x)-1
        elif I[a]!=-1:
            x[I[a]].append(b)
            I[b] = I[a]
        elif I[b]!=-1:
            x[I[b]].append(a)
            I[a] = I[b]

ans = []
for i in x:
    ans.append(len(i))
ans.sort()
cnt = I.count(-1)-1
if cnt > 0:
    if ans[-1] * (len(ans)-1) - sum(ans[:-1]) <= cnt:
        print(ans[-1])
    else:
        Ans = ans[-1]
        cnt -= ans[-1] * (len(ans)-1) - sum(ans[:-1])
        if cnt > len(x):
            Ans += cnt//len(x)
            if cnt%len(x) != 0: ans += 1
        else: Ans += 1
        print(Ans)
else:
    print(ans[-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

n,m=map(int,input().split())
lst=[set() for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  lst[a].add(b)
  lst[b].add(a)

chklst=[False for _ in range(n)]
mcnt=1
for i in range(n):
  cnt=0
  if chklst[i]:
    continue
  x=lst[i]
  chklst[i]=True
  cnt+=1
  q = deque([])  
  for e in x:
    if chklst[e]:
      continue
    cnt+=1
    chklst[e]=True
    q.append(e)
  
  while(len(q) >0):
    qq=q.pop()
    if chklst[e]:
      continue
    for e in lst[qq]:
      if chklst[e]:
        continue
      chklst[e]=True
      cnt+=1
      q.append(e)
  
  mcnt=max(mcnt,cnt)

print(mcnt)

Submission status: Wrong Answer

Solution code:
import copy

n,m = map(int,input().split())
f = []

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

nf = []

for i in range(len(f)):
    cf = set()
    cf.add(f[i][0])
    cf.add(f[i][1])
    for j in range(i+1,len(f)):
        if f[i][0] in f[j]:
            cf.add(f[j][0])
            cf.add(f[j][1])
        elif f[i][1] in f[j]:
            cf.add(f[j][0])
            cf.add(f[j][1])
    nf.append(cf)

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


print(ans)








print(ans)

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

grpno=[i for i in range(N)]
ngrp=[1 for i in range(N)]
members=[[i] for i in range(N)]

ngrp_max=1

for i in range(M):
    p,q = list(map(int,input().split()))

    if grpno[p-1] > grpno[q-1]:
        r = p
        p = q
        q = r
    
    if grpno[p-1] != grpno[q-1]:
        ngrp[grpno[p-1]] += ngrp[grpno[q-1]]
        ngrp[grpno[q-1]] = 0

        for j in members[q-1]:
            grpno[j] = grpno[p-1]            

        members[p-1] += members[q-1]                

        if ngrp_max < ngrp[grpno[p-1]]:
            ngrp_max = ngrp[grpno[p-1]]
   

# for i in range(N):
#     print("i=",i)
#     print(members[i])
#     print("group_no=",grpno[i])
#     print("#member=",ngrp[i])

print(ngrp_max)

Submission status: Wrong Answer

Solution code:
import collections

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

for i in range(M):
    A,B = list(map(int, input().split()))
    if (team_table[A-1] == 0)&(team_table[B-1] == 0):
        color = A
        team_table[A-1] = color 
        team_table[B-1] = color
    elif (team_table[A-1] == 0)&(team_table[B-1] != 0):
        team_table[A-1] = team_table[B-1]
    elif (team_table[A-1] != 0)&(team_table[B-1] == 0):
        team_table[B-1] = team_table[A-1]

if M != 0:
    ans_table = []
    for t in team_table:
        if t != 0:
            ans_table.append(t)

    ans = collections.Counter(ans_table).most_common()[0][1]
else:
    ans = 1
        
print(ans)

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[str(a)] = counter[refer[b]]
            refer[a] = refer[b]

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


        elif str(b) in reldict:
            pass

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

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[i]) > 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:
#!/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()
    hitDict = set()
    for i in range(M):
        args = list(map(lambda x: int(x), input().split()))

        hit0 = args[0] in hitDict
        hit1 = args[1] in hitDict
        hitDict.add(args[0])
        hitDict.add(args[1])

        if hit0 and hit1:
            continue
        elif (not hit0) and (not hit1):
            groupList.append({args[0], args[1]})
        elif hit0:
            for group in groupList:
                if args[0] in group:
                    group.add(args[1])
                    break
        elif hit1:
            for group in groupList:
                if args[1] in group:
                    group.add(args[0])
                    break

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

    print(maxNum)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
L=[]
for i in range(M):
  A,B=map(int,input().split())
  if A>B:
    A,B=B,A 
  if (A,B) not in L:
    L.append((A,B))
L.sort
P=[set()]
for l in L:
  a,b=l
  for j in range(len(P)):
    if a in P[j]:
      P[j].add(b)
      break
  else:
    P.append(set())
    P[-1].add(a)
    P[-1].add(b)

print(len(max(P)))

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[i]) > 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(visited)
print(len(visited))

Submission status: Wrong Answer

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

import networkx as nx

g = nx.Graph()
g_list = []
s_list = []
for i in range(M):
    b, c = map(int, input().split())
    
    if b in g_list and c in g_list:
        continue
    
    g_list.append(b)
    g_list.append(c)
    
    if b not in s_list and c not in s_list:
        s_list.append(b)
    
    g.add_edges_from([(b,c)])
    
g_list = list(set(g_list))
result = 1
for n in s_list:
    tmp = len(nx.single_source_shortest_path(g, n).keys())
    if result < tmp:
        result = tmp
    if result > N / n:
        break
print(result)

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))))
    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
def main():
  N, M = map(int, input().split())
  lst = [list(map(int, stdin.readline().split())) for _ in range(M)]
  
  f_lst = [[] for i in range(N)]
  count = [0] * N
  
  for A, B in lst:
    if not B in f_lst[A-1]:
      f_lst[A-1].append(B)
      f_lst[B-1].append(A)
      count[A-1] += 1
      count[B-1] += 1
  print(max(count)+1)

main()

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)//2+(c-1)%2)