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: Accepted

Solution code:
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

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

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))


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

uf = DSU(n)

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

ans = 0

for i in range(n):
    ans = max(ans, uf.size(i))

print(ans)

Submission status: Accepted

Solution code:
l=lambda:map(int, input().split())
n,m=l()
p=[-1]*n
def root(x):
  if p[x]<0:return x
  p[x]=root(p[x]);return p[x]
def union(x,y):
  x,y=root(x),root(y)
  if x==y: return
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[r(x)]
for _ in range(m):
  a,b=l()
  union(a-1,b-1)
print(-min(p))

Submission status: Accepted

Solution code:
from sys import stdin
import collections
def ip(): return [int(i) for i in stdin.readline().split()]
def sp(): return [str(i) for i in stdin.readline().split()]

# 4 6
# 1 2
# 1 3
# 1 4
# 2 3
# 2 4
# 3 4

def find(d,x):
    root = x
    while root != d[root]:
        root = d[root]

    while x != root:
        nxt = d[x]
        d[x] = root
        x = nxt
    return d,root


def merge(d,s,x,y):
    d,x = find(d,x)
    d,y = find(d,y)
    if x == y: return d,s
    if s[x] > s[y]:
        s[x] += s[y]
        d[y] = d[x]
    else:
        s[y] += s[x]
        d[x] = d[y]
    return d,s


n,m = ip()
d = {i+1: i+1 for i in range(n)}
s = {i+1: 1 for i in range(n)}
seen = set()
for _ in range(m):
    # print(d,s)
    x,y = ip()
    if (x,y) in seen or (y,x) in seen: continue
    seen.add((x,y))
    seen.add((y,x))
    d,s = merge(d,s,x,y)
ans = 0
for i in s:
    ans = max(ans, s[i])
print(ans)

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
import zlib
import base64
import subprocess


exe_bin = "c%1E9eRLDol^=Z=8w`>lCNW<@p(ceSR;(bvB4)8{3C2V?Ua*OiKqg`&V>Plwq!HNJmT)jm859v8&Th-eZduap>85mhmQA;Na_H`2aDa5TJta*~!ZvBvrwy$XH^E&Jz5;0Pee<3?GuAZeZvW)@*!SJvyZ65P?!5PA=FRo9f#7Ph$;7c@;r@(6Zp5MRjTEnU6-5B6=O)A7JGpt>B;c(oIX%5%($b1zKZ;(xncCOUxtx}oRJ4pUE+aFwl;fO5J@mD1o`TlRb82Xg_S;sb)iYB)p6c;bo>2$YW0Z~0N`KoauBU!ZORbc)otMH`AG%H9^)$$7DbxFN(3`}4{z5M=x1RQA6qmEqUq;z=xIY%%vdnXTEL<Cl#?!sEz4gm#mw8;NgzEv~lY`2xY3(5Lc)iUkpQ|W_?QdS#zhiXmUdzC|j?srczAMmo?_YhzOl8=0!w8!|vx?fNIykjC^|f+laze?#?~D@oca3o9Xh8|Q!$5w}R2n~IfPc%tPMv}Lvj+ID4D2j3kpGE+{F4Uwe2&e0ZRs+wf6M@P7}$Bx08bhC(+c*dbF;Wcr=sPc6Yxu%f<Jkef>*PN3G*@~g~faC#kshQ6NIfjiMWuGLP<#wIH9F|oe+*BBU_^>DUxho*Bnd4BkiFrv53-Ey5+If4bfyOus%wviC8LtwGGk|F&Zb3R3A;Gge{>|#M2UwN`7}>I}va%7X+z0nb-ksVIdTYB}8lp$J(~*^xR8ReQ{CP5tX{Z+i)}y*n-aY_6pk~$y6d9ibbV9VSAloc9|d~Qc^M!>Jg&xR3s_2h=97q?od*YlA)-SY7qm0^?)q_<57`Gx3mlGbwXgnGNJ9E4NHU=Sc~uIDK&&<HUy8DNJ|*jt)eKTFsg1&=!ox##>2w;NGjbE!A6mV8zL<}C5YWm30<Km*cU=6^pA03Z%7D9k>038nXV`f?HLHNfM)2G>Ip$$*EBZ^OI&r_nqW&)v+#h+Q>;DUTFNzdcKVuH1h;F60(W+Tu*c<9b2uT)@M9sr7E-su{lg4<3T_?cWDingl&!=BKb@xW`P+7PUnR=@n9eT~$fap}9sE{BqtkFl`#HtZv!j!7XM3+GZy|da+i&0e$EV70NBe-v%g-)0;~ni2%1et6RG>c=y0fu;nB7-KrYp2whaYA4YaM==%2znGIOEUGS19hW7S*~tr^0P2d_;viRCrE>Pgmh%DqOw3uc+|bRJeosg)y6|!rA)A+jEr)XX_vFnJRo6wO`JS-?Omvs&MtqW0wlIs_?xkT>acJsKV9v-GeH;T!kN2;T0<UWfeYIg&$SnQ&jk?D!fvK52^5JD*Sa7Zdc)a|L-dJOxgLFPL3ZKlFWs(eE(||!(3tMT7U`*gYefrzY%K4ccV&vqyS}M6Y?0+{8_@UKpsPxA0qq%$m3MXA0_-f$YV(JhY7y`c?@NKknppS#}MXs5q<{p=x%-+;in*vA<I8Wcr)@Cs(c&auT=q$A<8!r{(q3i(B$g~{{iq_gKXTsM|>OI1z(4+y<-E!pf}8CtP2-mKxBVSw|giz2Xy$XR8z-iSFXApqI0Hf?j1@Db9UP1;pH<qGcw{P5Ip0r;Ym!P(#9&Cq%!c1ys4(qKJY^bP{v>5$+i^+hUE4dkA2U2h+!}ruBi`ZYu|z~1;KDbF#F}2#!<1$WuL!?^cfUSwVW6+ug!YQnMngfcKK5Py}y)dd2yJ}PTkFmr}%8u?u<KQ_MYB3T|Og^$)oa3UVfXG|AUvWn#N?4JX_cG+h|z+O;Em&Yq(h`1m#OOAU9M&us+*~q=C3zpY1Nlv6=?^-g3C4nP5$$oV$GXL~g$KKka{Wa?eToo(nKC?@#R6-vZ?`?KON*9M*We*9(F2p4d4*D8Am5nY(Y`9lP8CW0!~JJJBF0KYu$3?6eCo4fyQR7$GZrfE@b*#{KVa6bknFyD%Q!*T3=>FXl20M+ORZIR}V5Nj{bT;3i7=Ns#LXhIXdW^1zSm`%f{q+#d$q?+3Fn2=7AseD3l&pZ7JtJvfpLn7p8~b2V!4{ijUc6ZZWtpjLM7_sBKOdS>H5dVh>98^P0{IJP$1@QOcE9>6Q|55$Q~`RI3{2k<*T!^!#O-{e9!l-bgN&qy%8&YXs*PRZSaaOTT3JU>v7%5tOE3kCNO0^MPLNduXS_JNPkf&SNeAK&cT<lF3f!Y2%SuiE#Y!>c9!v?*iVhduuqdu}*_p_Z@YFG8dDzwG<JPlVnCp#v!N5(qWPbN8WCUWPV5j$=PmTEwA@XLm5$Fo5G6xMY`)lJPd|UM*W+!EyWLq5NHVZC))XWfkuowtw|$5}y0MLBa!*X!&&<>C{E;pADX|l2y(3pEU8_H`8OvNabKn8!j+X>x6;Z_k098xsN_A6!Pz1$N6F3|0xDWJeTpjIB==2t4X#Vkcab41*P%58#t)5O&QMtXsw0Tee#)n0f+p1`~D%)db%mouzR4;=jWj+dsei7_pX8>afnE~2SIspV5n~sG#`-1MqkCIeofQkvgbu;*@fYb-cW_RPiT@GcFQ+MUxJw$v67j3(n4nH+dz)t(?IUVHO1Zg$yi>`c=my}B6$0ve0p>rw#-zu*yZQR#UZU<#n#K$)vZ5JT4AK4{m|)A(%aH?N~f*ZDLzi;_Fls^T)@~a3c{jw24R_32Z412A?Ovka<&Ng42on>B!eOu6oDmE0iEQ@)c!+ehD@KwOf4~U0nMnD`_;-im1<DQnXj>RArC7{<Lp&H<p0hsf|k+ub58?12m?Pk-AQg=xiM_dtaRIf&(2&y$kK0-*4HZXyP>sf(EVYH{KgZ!{42iy{js+8V7BZUI+C46{K>BT9Y_^szGZWAACvt9AQKqs;Im~{0pz_`c=^0E3vQK1Y|5>2+UCN@`2M_k81ItfJm{aW5l4>M(9B}kiqG>WZd!PGj6acE#hXs^Z`_os!Qj)>;8ZkdWN+8XHym*HN#D=+ubdAGU=sY93d3FtTy7q?pW|T&r^~(rawb$K`{c#pE;1ez-<<CP356fHgm=E)&Afagv&wsUXFH!+SHX+#@h5(5h8xMOj2UM7l*i>U*m%Ge=RLF29TZ1k-Ms`edAfXBHp^qUD^dHn{9ncepXsQ8srpUc^o!A7KzM6Nc$dDUgyfqX+sfa)44xE6*ENXu;}-dCydej(3lB{pp|AZm&<#HMMvHtYxcEGIRylFQl3N4H{J@8j)BR5I{wQCA+m~Oy;44(U%l8k%uJg<E2RH##Tj$_-j~9pOvk!UNQJ&}VWy2+kT%EIFrL)(0_ucTP!5J4&UXNjoV0~EYE6N#_Xk2o3#G{G$YIt8-u_6U;I*R~XY|x%eBqUAy_Cz$S7D&UZ8L@DmlZct-SRTZ)Abdb-yHqF~1nPt^4WaKq@qA$nHkCa<ov`)blUyC_n&*HH0X+;jJ}2eqLo$1|Ha)YRGxa)5bEcM844TRvh~rt@QLuHdYJ8>TIj)Aue^Mx%MFE>*wXJ%sy>dszE^gKA2k%)@vw-R28CWOyu6{1YSGP?#Ch(bDIls;EyxC`~e$L{vIs2`lDYoino1@8A;ji2Xbswp(sVtrsKGPN?9+m%fZKac&!~DYMGxY5W_;nnfLaoPvX|g$9FgMw%_gnlnXV%(eTl9RH&sO)`B%iImzua#-YO?&Td5WzbFrRHvlg$aTO{7B~K4?~B{K0k@?q=ke^dXz$37aw+92>5MY8Xd^)ASW6_QhjgJodHD)|f2S4|&&$ft^OMqkeBG6ijoS(CG{2%jQFs+|MVKy;{kAzY<1vtP-oY%B^y%+$y)qt#YgU{|h^RW#_Hzd{zB@QcXKeT0TuH>}>N2J@jK|b|2G2(pi*e=f86(&(2(DQ_9YJ*>ewjhWg}YA%XNDeOO>;muKnWCOfknqV4RA(N1~x<WNni`fL>oJ1g#_=Zox_#Ho9ZWM`mvP<pOHiyto6`dv@;*;y#-|4vRT2aj50d?pIrq`ZULD^Q;KIY#*rI`FHMSD*F%DGU2PtS@)dKrf?oHKiLV?V@x$rO#3NHA=rt>Az5Vn$ow_hs6Jf!oCNvvZlFtg>zBImULW7JD0nby6S3|qzUKV>8^Lxc@`_^=dq1nK<Z0;sm1Rx?Im#wCzZsl#rdqo%Zl?@i%%-fcP(CCoCjLGqBwuF_~ha|)#6i%^I3~m7T2{FpUOE(Tqg^x{*jWnjT<Y8+l%{z7I$brrWEn%#ry#+K7(^qmBMf1hV%=b;8n%_NQ=)b?n7Gq_LA$s0=og*H?%mcc4sMk{QIvKpFIJ??Ze9bzM#h^lQsvpi^hTNuS+R@nBuG#k>XG4<X_-$ud@~Rf0h>WcSL>`*SEk~^aIN)2LAjTwd0ts#g9|GO^5%C;)iv3j`rKD>-RFLPrNR7niM-DIy?86P=4a|HS)iO$j{*ZwZuFrCI1L<Y~nop60tLJo}`F;)dc_dP+afl*NL5p^Xhx#yJ|I8t(!jy3tsDq^X;EWzQOo9V%x{CL7qe20IxQe&L=s<q5Sx|K2C4U9+01IuAZ<D`^=^7KWc#EzIhkeVc${N_T;vr{KS1@(7?_S13YC>{Ac-L>@4Wt4dmZ2z<)sOOx!0wq;b$+ud4=jHd;#OhxAyK>#o1P&yx8ti`%t8i$7ygaDBheSq$=pXdHIY#t6lKXdwTt0e;a^Iv>VvEiL~=E1f^Ik=^!|TTAD|tTV6^vzG4nFRVCk!9Lv|_E3D#K>mn<{o<jj@YrLm-r@nK2M;&{(SX}42yN>F?d^{Wt2<ho+gl!P#q1o7>{4>p8Hj#9X%8N)8e3iye7MOM6ogcIi_oH^mtb;BuwD?Ni70f$iAgCXrMtRZA~&8OBuG7ih>1WcP7uNgVQVb0B@`3FQX-iWLg`*kO!RDvMWjgBwS1YkzO)eLxI~3eG8yU<B5^6%$8{w`JrN<C?&;|R6%{9-D;iNjSiRo2E+7P2{WuO`O>2h`;3>%a*K>mZ(N^EOmS$+vD2KHG$*U>G;o;S*Hw4;+c3)F409GU6kQCyCmWN5|QCvu;B4NY)rN%~ehRtVYG3mrLNk6oWX7oVtQVF3u6c1~1uJi^}2}N3c|0Awsq{~%0Yf6=Qr0bPrW9bJK-_fJ*SDV>1ZUo!f*EO>%^ruYE(zxLAj^|_PeZ%X=F0rsBm16bMd0l#Kl6WPi(qz7r%sOjqRHa)LbKrD#{!nh6CSeTpXlj?LZ(JnBq`HzGj;Ds{=Z!YUuf&G)8OePm()Y9;aIREej}+PhR7xteo7JLmFu9F$#S>D*1u?3XLR%@fHJ)~DNk?Ph+Gv;~Tz4qd&AGyTaj>UQDXFw<hk%3A8b*M&WF!_sL0a1uldwy;PFQtqO+W=^HT)$3bR`pHExRJ!bYJNXC&xLkE{Z~=SBz|v1c{8_HNHtGHdr0{4E01ss1SoNt2h^IcRjE#mD=$CxPs>yc#C59FQfc#R!lk`KPIYkxb*qePMy5|HPEfoXYZSg)_jIOe%HBFC?uFZdoN{l5yjcLi~cpSl~c}Gm_B=dWt8QU<7=u(rO(boHgejWYWAMXs9pCytdHLloN`9O#Mt{Vqxb3jH|ywAoO0&Ec=q1RC`-6vd4>A%Kf@_8W%}&>no)KRq>mpP{~oH}M0xfe&ZtwRe@6-Z{hT_teEb}aQFdO%ivIe`I(_zD&*)j5yhBI-Qm4<}{~6WCt3pS=q0?vY6O5X51{_+JzORn!v-bi<^~V?b@qdTYuHWLh1N(mkoxD@W|C3JN=>Hsy`aiDIXXhA<9@R~FeLR1p?|-J2>iyNPpLaMVFP5Dzj{n~T^+PAGzka{vlzdF4&)#zz=au$XuYZx#=IoCDUkdGCwSTDfm|q9!nDpnko%0p`<<IE<x=z3No<#{;XL@~B%=F;4IDV>MP4ydf`&Xk*zuctsuRnlf`ipgVsq^_#|2)D|eFt?I??Y~G;{GvN<-59c(vAP8x(TbFKhq8LzgSEA*D2`r{}*)uI*$"

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Submission status: Accepted

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$|e)+isjN5PkPoj1*-9SuS1WrHVp+Bt^(JW@FVDWSfWd>pKQYutPVz80K>3oEbBB&`RqjCzX8$MfG)}S5fivncVF?Qgb!6qG_eERrx;jqU3{i!aAy5S*U?iRVvBK@x#3j`l<L?TIobSQvMqOZK<bz{J<O|$`y-rX6ONPcwt?OCve%1gK^MPg@74!MhHT9D>~qcS_`e6o(bSH+oX2T=<xe-q(*4h45qR24`zF>cQy@|TDqo55Cp7HT{b7^bU}<zpn{kA?R907Xm|t<Idlm+(saw}1_Kh)z+m@8vIq3f_$F&a%P*VN7cUx(MjhHh?&u%){97>-*(umn@~uh^KvEL+M+w>r6ZL@ZfMj>X<&D<x0zX1!M!3mnptnT$#A<P@rH_L?+qt41hec{E?M19*Ie_gn?IBkdG=(bU#o|`^k~bQ)g62m=!%8vhUYP5DXtVe>y6uxjeWaf)WAH`FZk*IBW#5br;|`U~b3gR3I)rpcf(91Pm<1M3)O~kd&efrZ)i)Da9n{|hhFeAs+mf-IYHa>!u<sq&hNCm+Gd~W76Ul&+IWBp)Z|~cO3{L1j_30AtM>t_wJn^?D(IV*ASw;W|eOd=J70Xqi`339cmoE_ic8Q<P6f4HH@(O%+U;LIih$4$b&)}Cv20SHy0fYF)@&")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N, M = map(int, input().split())
f_uf = UnionFind(N)
for _ in range(M):
  a, b = map(int, input().split())
  f_uf.union(a-1, b-1)
answer = 1
for i in range(N):
  answer = max(answer, f_uf.size(i))
print(answer)

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

ans=0
u=UnionFind(n)
for a,b in ab:
    u.union(a-1,b-1)

for i in range(n):
    ans=max(ans,u.size(i))
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self, x):#親となる要素を探索
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#再帰
            return self.root[x]

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

        elif self.rank[x] > self.rank[y]:#深い木に連結
            self.root[x] += self.root[y]
            self.root[y] = x#yの親をxとする

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def issame(self, x, y):#x, yが同じ集合か判定
            return self.find(x) == self.find(y)


    def count(self, x):#要素の個数
        return (-1)*self.root[self.find(x)]

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

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

ans = 0

for i in range(n):
    ans = max(ans, uf.count(i))

print(ans)