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


class UnionFindByRank():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [0] * n

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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
    def main(self):
      return max([len(self.members(r)) for r in self.roots()])
    
uf = UnionFindByRank(N)


for _ in range(M):
  A, B  = map(int, input().split())
  
  uf.union(A-1,B-1)

  
#print(uf.parents)
c = collections.Counter(uf.parents)
print(c.most_common()[0][1])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
#import numpy as np
import re
import math
from collections import defaultdict,deque,Counter
from fractions import Fraction
import bisect
import itertools
from itertools import accumulate
from copy import deepcopy

import heapq
import random
import time
import os
import sys
from functools import lru_cache,reduce
readline=sys.stdin.readline
sys.setrecursionlimit(100000)
alp="abcdefghijklmnopqrstuvwxyz"
numbers="0123456789"
mod=int(10**9+7)
inf=int(10**19)
class Set():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(bool)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        if not self.find(x):
            heapq.heappush(self.heap,x)
            self.dic[x]=True
            self.size+=1

    def remove(self,x):
        if self.find(x):
            self.dic[x]=False
            self.size-=1

    def find(self,x):
        return self.dic[x]
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==False:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class multiset():
    def __init__(self,A=[]):
        self.heap=[]
        self.dic=defaultdict(int)
        self.size=0
        for a in A:self.add(a)
    
    def __str__(self):
        return str(self.heap)
    
    def add(self,x):
        heapq.heappush(self.heap,x)
        self.dic[x]+=1
        self.size+=1

    def remove(self,x):
        if self.dic[x]>0:
            self.dic[x]-=1
            self.size-=1
    
    def count(self,x):
        return self.dic[x]

    def find(self,x):
        return self.dic[x]>0
    
    def top(self):
        while self.heap and self.dic[self.heap[0]]==0:
            heapq.heappop(self.heap)
        if self.heap:return self.heap[0]
        else:return None

    def pop(self):
        ret=None
        if self.heap:
            ret=self.top()
            self.remove(ret)
        return ret
class Edge():
    def __init__(self,x,y,val=1):
        self.x=x
        self.y=y
        self.val=val
class Point():
    def __init__(self,y,x):
        self.x=x
        self.y=y
class unionfind():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(n)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):
            self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def yn(b):print("yes" if b else "no")
def Yn(b):print("Yes" if b else "No")
def YN(b):print("YES" if b else "NO")
def ispow(a,b):
    now=b
    while now<a:
        now*=b
    return now==a
def getbin(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def getfacs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def nextcomb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def getprimes(n):
    if n==0:return []
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    ret=[]
    for a in range(n+1):
        if(A[a]):ret.append(a)
    return ret
def isprime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(b,t,f):return t if b else f
def factorize(n):
    b = 2
    ret=defaultdict(int)
    while b * b <= n:
        while n % b == 0:
            n //= b
            ret[b]+=1
        b+=1
    if n > 1:ret[n]+=1
    return ret
def inputintlist(row=1): 
    if row==1:
        ret=list(map(int,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=int(input())
    return ret
def inputfloatlist(row=1): 
    if row==1:
        ret=list(map(float,input().split()))
    else:
        ret=[None]*row
        for a in range(row):
            ret[a]=float(input())
    return ret
def istanchouzouka(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>=a:
            f=False
        prev=a
    return f
def istanchouhigensyou(A):
    f=True
    prev=min(A)-1
    for a in A:
        if prev>a:
            f=False
        prev=a
    return f
def getallsum(A):
    s=sum(A)
    dp=defaultdict(int)
    dp[0]=1
    for a in range(0,len(A)):
        for b in range(s,-1,-1):
            if b-A[a]>=0:
                dp[b]+=dp[b-A[a]]
    return dp
def yuukoutomukou(edges):
    ret=deepcopy(edges)
    for edge in edges:
        if not edge.x==edge.y:
            ret.append(Edge(edge.y,edge.x,edge.val))
    return ret
def dijkstra(edges,V,start):
    from queue import PriorityQueue
    mincost=[inf]*V
    G=[[] for a in range(V)]
    for edge in edges:
        G[edge.x].append([edge.val,edge.y])
    Q=PriorityQueue()
    Q.put([0,start])#[cost,x]
    while not Q.empty():
        nowcost,nowx=Q.get()
        if mincost[nowx]==inf:
            mincost[nowx]=nowcost
            for cost,y in G[nowx]:
                newcost=nowcost+cost
                Q.put([newcost,y])
    return mincost
def warshallfloyd(edges,V):
    mincost=[[inf for b in range(V)] for a in range(V)]
    for a in range(V):mincost[a][a]=0
    for edge in edges:
        mincost[edge.x][edge.y]=min(mincost[edge.x][edge.y],edge.val)#x→yが複数ある場合のためにmin()する
    for k in range(V):
        for s in range(V):
            for t in range(V):
                if mincost[s][k]==inf or mincost[k][t]==inf:continue
                mincost[s][t]=min(mincost[s][t],mincost[s][k]+mincost[k][t])
    return mincost
def bellemanford(edges,V,start):
    mincost=[inf]*V
    mincost[start]=0
    for _ in range(V):
        for edge in edges:
            if mincost[edge.x]==inf:continue
            mincost[edge.y]=min(mincost[edge.y],mincost[edge.x]+edge.val)
    return mincost
def getmd(x1,y1,x2,y2):return abs(x1-x2)+abs(y1-y2)
def geted(x1,y1,x2,y2):return math.sqrt((x1-x2)**2+(y1-y2)**2)
class fordfulkerson():
    def __init__(self,edges,V,s,t):
        self.V=V
        self.used=[False]*V
        self.G=[[] for a in range(V)]
        self.s=s
        self.t=t
        for edge in edges:
            self.G[edge.x].append({"x":edge.x,"y":edge.y,"cap":edge.val,"rev":len(self.G[edge.y])})
            self.G[edge.y].append({"x":edge.y,"y":edge.x,"cap":0,"rev":len(self.G[edge.x])-1})
    def dfs(self,v,t,f=inf):
        if v==t:return f
        self.used[v]=True
        for a in range(len(self.G[v])):
            x=self.G[v][a]["x"]
            y=self.G[v][a]["y"]
            cap=self.G[v][a]["cap"]
            rev=self.G[y][self.G[x][a]["rev"]]
            if self.used[y] or cap==0:continue
            f2=self.dfs(y,t,min(f,cap))
            if f2>0:
                self.G[v][a]["cap"]-=f2
                rev["cap"]+=f2
                return f2
        return 0
    def maxflow(self):
        flow=0
        while True:
            self.used=[False]*V
            zouka=self.dfs(self.s,self.t)
            if zouka==0:break
            flow+=zouka
        return flow
def zipsort(*args):
    ziplist=sorted(zip(*args))
    for a in range(len(args)):
        for b in range(len(ziplist)):
            args[a][b]=ziplist[b][a]
def zipreverse(*args):
    ziplist=list(zip(*args))
    rev=[]
    for a in range(len(ziplist)-1,-1,-1):
        rev.append(ziplist[a])
    for a in range(len(args)):
        for b in range(len(rev)):
            args[a][b]=rev[b][a]

def to10(A):
    ret=0
    for a in range(len(A)-1,-1,-1):
        ret+=X[a]*2**(N-1-a)
    return ret
######################################################################################################
N,M=inputintlist()
U=unionfind(N)
for a in range(M):
    x,y=inputintlist()
    x-=1
    y-=1
    U.unite(x,y)
count=defaultdict(int)
for a in range(N):
    count[U.P[a]]+=1
ans=max(count.values())
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
numbers=[set() for _ in range(N)]
for _ in range(M):
    a,b=map(int,input().split())
    A=sorted([a,b])
    numbers[A[0]-1].add(A[1]-1)
for n in range(N):
    for num in numbers[n]:
        numbers[n]=numbers[n]|numbers[num]
suuji=0
for number in numbers:
    suuji=max(suuji,len(number))
print(1+suuji)

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)

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
    
    group_dict[a] = target_group
    group_dict[b] = target_group


for k in group_dict:
    group_member[group_dict[k]] += 1

print(max(group_member))

Submission status: Wrong Answer

Solution code:
from collections import Counter


class UnionFind:
    def __init__(self, n):
        super().__init__()
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

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

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            elif self.rank[x] > self.rank[y]:
                self.par[y] = x
            else:
                self.par[x] = y
                self.rank[y] += 1


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

print(max(Counter(union.par).values()))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
t = [0]*n
q = []
r = 0
for i in range(n):
    q.append([])
for i in range(m):
    a,b = map(int,input().split())
    q[a-1].append(b-1)
    q[b-1].append(a-1)
num = 0
for i in range(n):
    if(t[i] == 0):
        num += 1
        cnt = 0
        stc = [i]
        while(len(stc) > cnt):
            x = stc[cnt]
            for j in range(len(q[x])):
                if(t[q[x][j]] == 0):
                    t[q[x][j]] = num
                    stc.append(q[x][j])
            cnt += 1
        r = max(cnt-1,r)
print(r)

Submission status: Wrong Answer

Solution code:
import collections

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

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

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

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

for i in range(M):
    A, B = map(int, input().split())
    tree.unite(A-1, B-1)

count = collections.Counter(tree.parent).most_common(1)[0][1]
print(count)

Submission status: Wrong Answer

Solution code:
import networkx as nx

N, M = map(int, input().split())
#A = [0 for _ in range(M)]
#B = [0 for _ in range(M)]
C = [0 for _ in range(M)]
for i in range(M):
    #A[i], B[i] = map(int, input().split())
    C[i] = tuple(map(int, input().split()))
G = nx.Graph()
G.add_edges_from(C)
ans = 0
for comp in nx.connected_components(G):
    ans = max(ans, len(comp))

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
count = [0] * n
for idx in range(m):
    a, b = map(int, input().split())
    if count[a - 1] != 0 and count[b - 1] != 0:
        pass
    else:
        count[a - 1] += 1
        count[b - 1] += 1

print(max(count) + 1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, m = [int(i) for i in input().split()]
people = [-1] * n
num = 1
ab = [0] * m

for i in range(m):
    ab[i] = [int(i) for i in input().split()]

ab.sort()

for a, b in ab:
    a -= 1
    b -= 1
    if people[a] == -1 and people[b] == -1:
        people[a] = num
        people[b] = num
        num += 1
    elif people[a] == -1 or people[b] == -1:
        if people[a] == -1: people[a] = people[b]
        else: people[b] = people[a]

print(max(Counter(people).values()))

Submission status: Wrong Answer

Solution code:
import collections # deque, Counter
# import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
# import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# --------------------------------------------------------------

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

road = [[] for i in range(n)] # 頂点vと隣接する頂点のリスト

for i in lis:
    i[0]-=1
    i[1]-=1
    road[i[0]].append(i[1])
    road[i[1]].append(i[0])

cmax = 0

for i in road:
    cmax = max(cmax, len(collections.Counter(i)) + 1)

print(cmax)

Submission status: Wrong Answer

Solution code:
n,m = [int(i) for i in input().split()]
d = []
for i in range(m):
  d.append(sorted([int(i) for i in input().split()]))
#print(sorted(d))

groups = list(range(n))
for t1,t2 in d:
  groups[t2-1] = groups[t1-1]
groups.sort()

pre = groups[0]
c = 0
t = 1
for i in range(1,len(groups)):
  if groups[i] == pre:
    t += 1
  else:
    t = 1
  pre = groups[i]
  c = max(c, t)
print(c)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,M = (int(T) for T in input().split())
Parent = [I for I in range(N+1)]
Rank = [0]*(N+1)
def FindParent(X):
    if Parent[X]==X:
        return X
    else:
        Parent[X] = FindParent(Parent[X])
        return Parent[X]

def IsSameParent(X,Y):
    return FindParent(X)==FindParent(Y)

def UniteParent(X,Y):
    X = FindParent(X)
    Y = FindParent(Y)
    if X==Y:
        return 0
    if Rank[X]<Rank[Y]:
        Parent[X] = Y
    else:
        Parent[Y] = X
        if Rank[X]==Rank[Y]:
            Rank[X] += 1

for TM in range(0,M):
    A,B = (int(T) for T in input().split())
    UniteParent(A,B)
for TN in range(0,N):
    FindParent(N)
print(Counter(Parent[1:]).most_common()[0][1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N, M = map(int, input().split())
    Edge_lsit = []
    for i in range(M):
        A, B = map(int, input().split())
        Edge_lsit.append((min(A, B), max(A, B)))
    Edge_lsit.sort()

    counter = 0
    group_list = [0]*N
    for Edge in Edge_lsit:
        if group_list[Edge[0] - 1] == 0:
            counter += 1
            group_list[Edge[0] - 1] = counter
        group_list[Edge[1] - 1] = group_list[Edge[0] - 1]
    
    group_len_list = [0]*(N+1)
    for group in group_list:
        if group >= 1:
            group_len_list[group] += 1
    print(max(group_len_list[1:]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

members = [-1] * N

group_count = 0
groups = [0] * N
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_count += 1
    
    elif members[A]!=-1 and members[B]==-1:
        members[B] = members[A]
        groups[members[A]] += 1
    
    elif members[B]!=-1 and members[A]==-1:
        members[A] = members[B]
        groups[members[B]] += 1


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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline

N,M=map(int,input().split())
P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]

def find(a):
    if a==P[a]:
        return a
    else:
        return find(P[a])
        
def union(b,c):
    B=find(b)
    C=find(c)
    if size[B]<size[C]:
        P[b]=P[C]
        size[C]+=size[B]
    else:
        P[c]=P[B]
        size[B]+=size[C]

for i in range(M):
    a,b=map(int,input().split())
    if find(a)==find(b):
        P[a]=find(a)
        P[b]=find(b)
        continue
    else:
        union(a,b)
for i in range(N+1):
    P[i]=find(P[i])
#print(P)
D={}
for i in range(1,N+1):
    if P[i] not in D:
        D[P[i]]=1
    else:
        D[P[i]]+=1
ans=0
for k,v in D.items():
    if ans<v:
        ans=v
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
#for _ in range(n):
#  x, y, z = map(int, stdin.readline().split())

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

uf=[i for i in range(n+1)]
"""
def uff(x):
    while x!=uf[x]:
        uf[x]=uff(x)
        x=uf[x]
    return x
"""
def uff(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = uff(uf[x]) #経路圧縮
        return uf[x]

T=[]

for i in range(m):
    a,b= map(int, sys.stdin.readline().split())
    ua=uff(a)
    ub=uff(b)
    T.append((a,b))

T.sort()
for i in range(m):
    now=T[i]
    ua,ub=now[0],now[1]
    if ua<ub:
        uf[ub]=ua
    else:
        uf[ua]=ub

cnt=[0 for i in range(n+1)]
for i in range(1,n+1):
    cnt[uff(i)]+=1
print(max(cnt))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict

input = sys.stdin.readline


def ST():
    return input().rstrip()


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


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


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


N, M = MI()

d = defaultdict(set)
for _ in range(M):
    a, b = MI()
    d[a].add(b)
    d[b].add(a)
    d[a] |= d[b]
    d[b] |= d[a]

ans = 0
for v in d.values():
    ans = max(ans, len(v))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N, M = map(int, input().split())
group, gnum, dnum = [0], 1, 0
mate = [0]*(N+1)

for _ in range(M):
    A, B = map(int, input().split())
    if mate[A] == 0 and mate[B] == 0:
        group.append(set([A, B]))
        mate[A], mate[B] = gnum, gnum
        gnum += 1
    elif mate[B] == 0:
        group[mate[A]].add(B)
        mate[B] = mate[A]
    elif mate[A] == 0:
        group[mate[B]].add(A)
        mate[A] = mate[B]
    elif len(group[mate[A]]) >= len(group[mate[B]]):
        for x in group[mate[B]]:
            mate[x] = mate[A]
        group[mate[A]] |= group[mate[B]]
        dnum += 1


mate = sorted(mate[1:], reverse=True)
if mate[0] == 0:
    print(1)
else:
    i = N-1
    while mate[i] == 0:
        i -= 1
    c = Counter(mate[:i+1])
    print(sorted(c.values())[-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ad_list = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in ad_list:
    ad_list[a].add(b)
  else:
    ad_list[a] = {b}
  if b in ad_list:
    ad_list[b].add(a)
  else:
    ad_list[b] = {a}

#BFS
ans = 0
done = [True for i in range(N+1)]

def dfs(x):
  global done
  global tmp
  for y in ad_list[x]:
    if done[y]:
      done[y] = False
      tmp += 1

for i in range(1, N+1):
  if done[i]:
    done[i] = False
    tmp = 1
    if i in ad_list:
        dfs(i)
    ans = max(ans, tmp)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class Graph:
    def __init__(self,v):
        from collections import defaultdict
        self.v = v
        self.graph = defaultdict(list) 
        self.count = 0
        self.mx = 0

    def addEdge(self,a,b):
        self.graph[a].append(b)
        self.graph[b].append(a)

    def dfs(self,node,visited):
        if visited[node]:
            return self.count
        else:
            visited[node] = True
            self.count += 1
        
        for nbr in self.graph[node]:
            if not visited[nbr]:
                visited[nbr] = True
                self.count += 1
                self.dfs(node,visited)

    def solve(self):
        visited = [False]*(self.v+1)

        for i in range(1,self.v+1):
            if not visited[i]:
                self.dfs(i,visited)

            self.mx = max(self.mx, self.count)
            self.count = 0
        return self.mx

if __name__ == "__main__":
    n,m = map(int, input().split())
    g = Graph(n)
    for i in range(m):
        a,b = map(int, input().split())
        g.addEdge(a,b)
    
    print( g.solve() )

Submission status: Wrong Answer

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


def root(a):
    if a == tree[a]:
        return a
    b = root(tree[a])
    tree[a] = b
    return tree[a]


def same(a, b):
    return root(a) == root(b)


def unite(a, b):
    if same(a, b):
        pass
    if a > b:
        a, b = b, a
    ra, rb = root(a), root(b)
    tree[rb] = ra


for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    unite(a, b)

d = {}
for t in tree:
    if t not in d:
        d[t] = 1
    else:
        d[t] += 1

print(max(d.values()))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    N, M = map(int, input().split())
    Edge_lsit = []
    for i in range(M):
        A, B = map(int, input().split())
        Edge_lsit.append((min(A, B), max(A, B)))
    Edge_lsit.sort()

    counter = 0
    group_list = [0]*N
    for Edge in Edge_lsit:
        if group_list[Edge[0] - 1] == 0:
            counter += 1
            group_list[Edge[0] - 1] = counter
        group_list[Edge[1] - 1] = group_list[Edge[0] - 1]
    
    group_len_list = [0]*(N+1)
    for group in group_list:
        if group >= 1:
            group_len_list[group] += 1
    print(max(group_len_list))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[set() for _ in range(n+1)] 

mn=0
for i in range(m):
  a,b=map(int,input().split())
  l[a].add(b)
  l[b].add(a)
  

for i in range(n):
  aa=l[i]
  for k in l[i]:
    aa=aa|l[k]
  mn=max(mn,len(aa))
print(mn)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
li = []
for _ in range(m):
    a, b = map(int, input().split())
    if li:
        for i in li:
            if a in i:
                if not b in i:
                    i.append(b)
                    break
            elif b in i:
                if not a in i:
                    i.append(a)
                    break
            else:
                li.append([a,b])
    else:
        li.append([a,b])
ans = 0
for i in li:
    if len(i) > ans:
        ans = len(i)
print(ans)

Submission status: Wrong Answer

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

ab = [[int(_)-1 for _ in input().split()]for i in range(m)]

for i in range(m):
    if ab[i][0] > ab[i][1]:
        ab[i][0], ab[i][1] = ab[i][1], ab[i][0]

ab.sort(key=lambda x: (-x[1], x[0]))

t = [-1 for i in range(n)]
ans = [0 for i in range(n)]
for i in range(m):
    a, b = ab[i]
    if t[b] == -1:
        if t[a] == -1:
            t[b] = a
        else:
            t[b] = t[a]
        ans[t[b]] += 1


print(max(ans)+1)
# print(t)

Submission status: Wrong Answer

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


import collections
 
 
class UnitDict(dict):
 
    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)
 
    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]
 
 
class DisjointSetDataStructure(object):
 
    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]
         
    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r
     
    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)
     
    def elements_of_group(self, node):
        return self.groups[self.root(node)]
  
    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1



def compute(n, edges):
    dds = DisjointSetDataStructure(range(n))
    for a, b in edges:
        dds.unite(a, b)
    roots = (i == dds.root(i) for i in range(n))
    res = max(len(dds.elements_of_group(i)) for i in roots)
    return res


def main():
    n, m = (int(z) for z in input().split())
    edges = []
    for _ in range(m):
        a, b = (int(z) - 1 for z in input().split())
        edges.append((a, b))
    res = compute(n, edges)
    print(res)


if __name__ == '__main__':
    main()