Problem:


Score : 300 points

Problem Statement

There are N cities numbered 1 through N, and M bidirectional roads numbered 1 through M.
Road i connects City A_i and City B_i.

Snuke can perform the following operation zero or more times:

Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.

After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).

What is the minimum number of roads he must build to achieve the goal?

Constraints

2 \leq N \leq 100,000

1 \leq M \leq 100,000

1 \leq A_i < B_i \leq N

No two roads connect the same pair of cities.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

Print the answer.

Sample Input 1

3 1
1 2

Sample Output 1

1

Initially, there are three cities, and there is a road between City 1 and City 2.

Snuke can achieve the goal by building one new road, for example, between City 1 and City 3.
After that,

We can travel between 1 and 2 directly.

We can travel between 1 and 3 directly.

We can travel between 2 and 3 by following both roads (2 - 1 - 3).



Sample input:
3 1
1 2


Sample output:
1

Submission status: Accepted

Solution code:
# This code is generated by [Atcoder_base64](https://github.com/kyomukyomupurin/AtCoder_base64)
# Original source code : 

"""
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

#define all($) begin($), end($)
#define rall($) rbegin($), rend($)

class UnionFind {
 public:
  UnionFind(int n) : n_(n) { init(); }

  int root(int x) {
    assert(0 <= x && x < n_);
    if (par_[x] == -1)
      return x;
    else
      return par_[x] = root(par_[x]);
  }

  bool same(int x, int y) {
    assert(0 <= x && x < n_ && 0 <= y && y < n_);
    return root(x) == root(y);
  }

  void unite(int x, int y) {
    assert(0 <= x && x < n_ && 0 <= y && y < n_);
    x = root(x);
    y = root(y);
    if (x == y) return;
    if (rank_[x] < rank_[y]) std::swap(x, y);
    if (rank_[x] == rank_[y]) ++rank_[x];
    par_[y] = x;
    return;
  }

 private:
  const int n_;
  std::vector<int> par_;
  std::vector<int> rank_;

  void init() {
    par_.assign(n_, -1);
    rank_.assign(n_, 0);
  }
};


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  UnionFind uf(n);
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b;
    --a;
    --b;
    uf.unite(a, b);
  } 

  set<int> st;
  for (int i = 0; i < n; ++i) {
    st.emplace(uf.root(i));
  }

  cout << (int)st.size() - 1 << endl;

  return 0;
}

"""

import base64
import subprocess
import zlib


exe_bin = "c%0>1eRxw<n!oud4YVXd3l;^5ZeR;YY@lERGB#}kH=05hiZTjb(j=vkG^xoA6xNT<wngrQKp%HTSyxAPbf0Br$7h&b_YvKFlv2K&QKx=9E<276vomTUepFE8OS12K?m5Z5w~6!d%zt}%()Yf<`+l7FJ?}a9-g6HRdVI_DIvvLj1NSWsxsz2g-$3zwH|9kEtLMhU-)p()+&JKk3OOx3r&Ci?-jA$Tua|i(oyMuDPC?7K(uZl9nsS^iuZL~5O{eH|n~I*Jem9h<_4HJ)p6b<8c}A^Nk5Lw%k^b5!uBFYKni?r>eP0Zcd`^{lEe&#N%JlvQ^u}?2{9&bZ74=stFDGex8D;%&V<g<ZsP4u{a9$)FP4>*|sb4g2QJo_ZbId1gvQpXQE7lNs>~FoI%~ce`>-EOWSI?Z1HqU$MrR~<?OLrVd%)B3Er*MUS!wl;{a|*RlwWqQv@klu{Ip+9h_+3#1H|dJwH6`!~;Nkir_&p`;uPK3lR>J<*CGhJ?;6e%fp%VCeCGb!Q{MHiq2Cg_hgJUB_eH<xaXR5w9ZY^PFNeO(kM0@TBzmvGBT!T&4veJV6kdyHZ*U5M_D`cqSgcuCWor|@*h!cd3U9qT;5dCpc5IDix)*=K$@zBO_LJY;*TACuUXsFHK9tp|UieI^N#p-Z8;aL?Xr?E)FgJ-M7x==J2@dj3lPG_Lg9~Z>9KP)D^0gq=DU<=y)iEu!OCB%5h-{ox++G+*Q>O}%ko$nG>wSz(^B!r`h5VX!84TAf2f5aaRgxXudKz&{$8ViO5Fc(@~E38^ATUZbXM@f6c`fw~kuGV>@VX@ii*-QkSHwl8+8INs&YeB&uiNpeUAsA`htkH8WOl*w?ge_sQ6H*ln$2{$rxt<=OI}}gEqW(x&+$wCY1-0mwu3}D`nA5sIEGf$F3(XIP0`X8+C@PkS3VUs1ARr{L)0~{JCb}gI*;o}yB)iDP0P9WY$iOBc(78$I@P{J+_!A^~lneCu1-}^T35%5J2xH^7K_3ceh89AXA5yoxsYzJisO6UXyp2u5d`DgWY`$Y5*R*!6yU{B+9SdZ5?OG77<8ao)e+K&3KzSql%IMw2KnhXDb@1;wU12=5&e~dmGIR6uubz90Uay5;RX98mXVe9H8B1Or9*;BYQiZ&ZE6n$A{&Z6r-a)-oUYz}~34OEs5}WtgeeC39nbv6V{q*^uR)g=Q@+O-aXZ*+vnX=~wcAQY)Rt0`ifh)&*MuA_cz(*B$l>$Gfz$YtkD{U9%$gIHG{DF@HQxrIxKM=o4iBtRKT;U#xN2dZ;-mJP6xIuyUC~)O-POk!2-sg8H@Nxw{sK8AMe2)SjufX>z@Cgchp8~H?;QJMLr2;>oz$Ys3g9_ZDz>h2NNeZ0r``E;%$~=>896xYS)aOR{zQd+rF1PTpDjS!Z`8fQw%xHi!<U3I%dol;d%!iT3F364${=3Ly>azz4|98k^%Cq|kzYTdT#q3_f$C1a>X9o#?5AvAuY%k&4k;mp{y9s|M@|fc62EwmG9#flbCH$?(V@k6Pgl|M1Q<<$L{9@!Wg;^Wn=Od4)%UTIP2l$RbmKXOO?%SO?_ZoNGn$`SwK0X0ZkWU$B)?m)0e*1Bt&V!jU(B#viy_HWd-HJIpR(AUoIn%!Mv-Uwk@3U{nT)Hd^w(-)j%xB01K+Btcz~qxI@W=Y?dsv6S`Ci5OKE?Td#rXln`9XRv$sUh2+ewNtH$gi1fDH2Kh<zRSv%%GML{a)EGX(@vZT7Z-H!Qp2(3j44eCeQltuH<ACy<R(T^$a~jD9(qz>s(7q<%%ZvfQ20^_|OE2Bw07>veI7FD18(4;=CZ{)Z=0RZpN&OS+PCr<_eo>h|0>$udw0)zEiT=aWXH*WHp+sx0pt*16W%+bp}jL>JNrKIyZ}8(%|mq)#zV$KW*8Y+svhMY3+-4XF(nJ}3F?>nuA~LNTS};H2YUjkr!XSROw%l$p`cf6UT9A1=B+x1{F)<x~Gf((4Nxl4GcX81xuJ|4c}e>*xbD0|$HTzQFOuRMqaj3lQ5AP{`6Dw{!({0H$`HCtWykeg!6T;V&__>80-idEu`>A~OdXTgVp}eA6|0|1bH#@n$gUCRQhdRkx&*hO&pjmSqOKlt5gqE$NLW=#@^nJDcs@tY3G~e)UN~dyh|g+TKenTXucQ<wGAhYuVKSQ8+&#_VTf&Z+M23#Hm};RX57f4%`Ag_7YZb=9x>moG%rzck|LwX|1hg;FILF*|l()wcnfaSf9tyjkCfOuXMznT4Qs)dEbX{q1yQ}pvjN=U$zV!#^n6!zFJ=TD#L@(v`6QHkRDh`o5%MZ(YcOVb_bz}*%wLFy`(e-J`sP>;(Grj^kErzl|=blAJpW-7a`4ka_~B8?!lj>WB@XL+G^v{-MP%1OIRnzWcie6@AgT#Ovr?GzRFB2$KlDR9w!4e$S;^iMy_SxL#&7I9LDi{*LwFl_j>o;Zeh4%(6=OF@3HjX1I>gY<R#H=%Iu+*O{rE}_NpAVor73*eFZ%Yy|Cjmtkl4XROOR>=OMcfW4iUyaP}V{Oqe^CthZrBX6>Lk=yO3Awn*<M|A|DLwGc-z5VBuF9B$WXOL{Mu^T0^l@hF_M1b*I_GVUhb_HUrjELH8s!PhK}WS@uYuD30_V%QFl-w4zfcmw1g1^MLNjYPJpJbN<=ylmOA3>99p?D`gI@at60ELA><#UUNfddM)a?3zv^n@j|uax0;7F}CM1Hshnx(5au}b!;=re}a7w7->#Td(_=`F_#Q9qR^r2HncZtNxynYws!=}Eikf-$yI{fZZ`<x`11_BW7+W($-)^+`Y|~128Ma58S-v?h$P_0;C-1i?a^lG#Hk}hTm-3R*L#*-n~I1(L-Iw$vzu}#2(dR_LQjwk*CovEP@^oJoZBo_?rw%0Oea(M#6&q6-lOA4u}uc<1$_R?+;(0L<-$cd^wSqHq~j3MZW2-#g!GUb67*A)dh4Q`fLDmr37@piZUxaNiD-lrm0KE?jL(tkKzl#DDBFLmn8v+Ijq6y>Vi#!=Ixb>JZ?Xc|2D#de!H1co=OWGS%@_0Os%GiJy9W>RkQH+F5UQ<bYG&r3tcaRHr%_v*lOs5BL5^tT0*RzCRrh4y<($|G;}WB)^}#G&<AXWe=0kftoLPCmOqpYP#RQf@(G-fNP&9?2DHH|F1j&99YYkG8HPd3-a6$IJR_%8M^~<B*2J~BxE^E<w4M4U`tHv#lZX3{TJ$kG~-!%Z)&@1*tHSLL`m*q%5ptbSd`Qn~=*>jt{-dFGpL1o_7X*~0?XOt{>_Ko%2ceya>@zQXn%OKBtc!%Mo-(;qL1-JjqS)3t<Pkn$c$Q@c5<_B_OS>^|Lh5AM0mCQ~+P8})Szo7OHO|+56!_0mnz0_F&e0uU?LKZ$vt{ygJ8{ullpz{;2^!nYr^uK)H??+qPeCe|98qmtbD+yWp6OhVHetUwA`$E1?rI+f!&>B8nb{;_9b&i+b7pKCb=#MAJkD?RT=S~*dvwj$#LRIY>nm`)z!UQxk`!eYBLzfM_G|CTUZsB!D`PVOtP%>rrQiGLfu#~;trLR}Qb6fI8zHjLaPymzAo=OP&R^T%4ehK;HA%vr4KLR-&s+0TJnc)r+4~nnP;*D752hQS?W6%1Og_pi|ef~fjpL)>52j1g{ey8WtRWryPIXV6=X%y~4aQ}hl1*dE1fqA~bNhqIxf&NWa!mU{^jpA);c#wxDqkT9-rPg5a|B%=H>eO!_y-(}Obmb;w=}J9&8hQK+<<m&V;A&pF2u-lj{{I3k{jCYPiFajpf04g0-^Jn~3Vk0#0&n3{O;&#PIezGzo`-UOsFzf0lPRV5NkjbX^Zd|xxbWJRx%|LcaSAV;=cUt<j_(^X@_iral3(!Yo1fz)@YZ*@`Yy~I*!Q`PiB`CuO67dtF{9UYF8O6j&(D4hElQ_529^5Wv~fQ#HL3K`)h7NxPCjmdc5Mmp=^Oq-ezJubf|u&-n6%+D7%Bp(I=e4ztVvDar9*?#1itSO*#8vUms$de;3b0(oWRd2eqVN#-F$}ir}Lo4dGOSUjPVSns)6`l;BNCumoQUj_*A0WCw-WCpLEeCD~>@IdLH<Mmrf;5l1@ZDRxkK|;g$XyUod>>nU{@ZD9jsIX5&`7rLVoxS>NpU$-CLm*M`g;r->!e=6omrJT6`ENoSj-&)m7HU-R%B&AZ-BeuM*3@mMohsDLxW^j(j<-HknP{h~=|ibbQLfG9MD#c(L$2y}OIwYHm=+InoWX2GAEZBc>BYhgSi*j7B-suU$hI4auKM8mP@vT!uGcyT-y6KepQ&8}~bg@a0gWHc;>P~rv~5z}2`Sb}Tu_(IqHc`k?3*#<}pKFD<g{WZ*_-Efzxg%Pk9DAwqHxYOhMWdl6T;JR}+KGgsngvoO!&=H(OK_1^12kD{#Tg%XGTgB;mth#F|%T0s2ax3EasiPWf&sD@#T%P0XRQ|xI+y>5UU1qMn)l#v=)XUv+^^!RY?AJ4W{5H`GF)7y%a77DW(++??(u2)r>rTDfT)o}kHrx7)?Gwz^O=fGO+0;~V7o5Avd1D3o{2u(Q5c?d|gA09nkTCfw+-4K`Ui2*dY;b*=PQJb!?e-a#n``weWm6!ztfEJ8t`Fpy+bV7VwR7;h1U43<kLB35=6u_NtT~?Hqpxs^Z%f-+eI!fe|EPmPzlP<im6P+e6LNJHl3@H#U>eQV-TFpz^)5rR*_Jjonrn8Jxy`lP$GOe*edWu|gL=b=VS>3HFt@p;(QE_RMw$?s*T=zjJ=~HV==?Ub^=^nCbNwvfz0md$r}E>;`{B_KkA7Or4e??=$lBQ@u(J>BDA${EIo-5bOE~VZZq}=lxbu4J@k!i!Wh1($CUGxL`lb(R|IZJ${>j!m+4`pPd!&*+r&IH9(G#{twudgRv9+=OYMIi{d-?U(YbejwLa(Njt+%q;Wn=Tp%efe_Pdh!|rSycY86Kq9*&5#l%CogS+8osyDIRQ%lBer+thQQdd~Cj9YmjVhlpn9gttNH5>#06li)8+<<<xR8-H`Zn6uM0LL25WhdDhNR%5R|8&r@Ex=KPmD*!N)Vag-+dZAw3&^em<0XyT_(I*ZaplrE$6c1k-a-Aw6rN*_@!&i)w(Tc2mg@}{Q6wwg8V$*7pL-Q-y4sGYYUNjT>N&U!~}-E0~CV{99s*XoOWsWm9RJE(C3Cl<wx`TADlW%;^R<Kv2M7BE0HZYVE?oAULf#>eODR*g@{*S8w4$d7Y1Udin*icjSB7U@3&XXf@7#Vz@HLycRxy+!d!`TYZG{0eSgQT$3Sb4@Y4DnCD|@yYplNsUh_IxY+_JFs~~jYH#Y#qh%STs4067!0QqBlmeui_3cntoezSh22PT8wHpbT<g?h{^`W#pm;x#pUQ2$-j?@=$KRLm`vYpns+mytQoL1z|2xI^YVen--yV(M6Xbks{&UpMNsXNf9m<dG$5QQ|L*%dEeqW>>ipk6K`Ph29jo2Am4{b!gYE1h>6xX)1hu9fgKf6loH+WZv`!~#7Fa3x&hvJ`+Z>ZH=wWh9S8?gq)*5O&Qub?o#*nOm|#D0dkCGa~->?e7UL;1pZKTGGE%_Z!-2>2v@^_Y447bWC>R|3Bb_;p~1eFtUJ+~hKpA3M)nZIJUhLT~VkDSnTkxc&YT_&lQ=FWYCv-d*;TkpI^bc%}p%BlgG6!$zZ=H*LRLjm7tk{IyZ86Ky?gAoVkq>%Cr$*BND8Yrnx*Vjm98gO%nvMDb(^`A16N&lrpElX<y>{BMnNKkldFVj7LNqD*d2FKrLItzJ`BeE*EIthoKwvf|^ey{vdU@1^pibiV4R`1TU=drSB&zE~jKdFKjO{w=-^-|{_SkJBXxt*bn3ZQmA_ty$63=3Ti0xBRGN7m^o#Pq?J?a^K2Ew@(lf$#%gjZxq4JEWUa{2*<*p%mw0NLQHmaI09T@Cy^j_2?5+Ol;8v*7!x)|V(tEj5ENtagy2v1aDiA?cO)c+f{vROx$27x;ck_%;E%`sTZK?mjBn*S;{L9X5KMM;Z3PttCty=lqJpq&mAl0wcvduH9K!MyYXlEZLB4qvCp3S1g}cSu1lLr`K{Y^j$mH{|a@n%go;IP)-RSfD1vV}<G$=RI2+E#mo{u|-LP5Xi=LGLcvJWXLBom=v$<0h-tbOyACXKjie-OP!H~;+kd%Ltgf{B>W2?<i|BGU>f_Asg2(R_y^9_nzE*ouYWvP65s;nku`@CKn6K)@UJKm?IcB7tXq_~WS;T7*y>GULG>TA=D7xUSkfrOgIz8Pg^^x}{4C{YiViv`J9!>?*VXueG%_vASkk%*G@d>W0;>(4I)J^Wt08wAy5ESRj!k1EJ{Fw}uAAj<EbLK#iSm+FhvH(*}BU_Zey6qRlYD#p2$u+*Qsx=&O!!B!ZO@-Wc_Ct-39&Y$eVU`8|L|V=3%&)Apru$dOHZnjMlwX4XHjHL}S5Lv@=tM`CN2=x+xq#%0>c&cabJ+08kkF)`$T{LT~o8!5Ljnsl@$!;#>;aF8Qhr$5ojIf7fGU{9uET)wgyItv=DVg$Gr4@LYaNYA<>BD#b=##6_}7@R=G!(Wn8M?6O6A4jN@PPU!Fc!2}!fq)R|352>uK_u}z3Nxo{gPns<e^)pFC&VCBB<Fy801k*^x4A#{z{hvIWwZNvsr~ls&}n%5c%$6IrrpnO)5vSrS)3Yu_I}T({SWBl`smqQF2?lPIsl_J6lbsd+Sm0JoV>=x^x1j=qYaeeI+;$P&mMno=hS=H^NuLppjm&==I?G!UZY}SZ2f^zwvfWi>NRu|C$D)io~=_b+RGK%Z{Wtpzm1b~%JkWK2BT~pPMbd#e?Qf4q&!>qV6;`Ce^n9vU7T_+e_<VzQRQArjvL$ml187cqcA$Ek+*8-_cZ!!y@gS2zDyeWgw}tBn!cgj1j(uQu;THQMxVV`F{)ig(#HQIPCb6vduX0&<ZT-MXBz!d|F5K!|CcoSY~6^_22K5I^ZBwypRF%3s%@`!{Jg`-`*Yd)ZsGr_$h<b++Wy1+{}zQlTW_eHUc9|p{WDx)Y~fM(e?Zi~V*XI-v3BjDF=^M)`57|LwoR7ue@UaCe;=hpyX>cpM^6{dnLc~Zt)}|g{%g?am+NHz+67;xKU;$r`#w_aKkM*Re+O;wH0nb;e~eeOU3rYqiT{XZomX2wlS=4+pDyfKH40k&{{yGp2ZR"

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:
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.co = n

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

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.r[x] > self.r[y]:
      x, y = y, x
    self.n[y] += self.n[x]
    self.n[x] = y
    if self.r[x] == self.r[y]:
      self.r[y] += 1
    self.co -= 1

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

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

  def set_count(self):
    return self.co

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = map(int, input().split())
  uf.unite(a-1, b-1)
print(uf.set_count()-1)

Submission status: Accepted

Solution code:
class UnionFind:#「貼るだけ」
    from typing import List, Set

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def merge(self, x, y) -> int:
        x = self.leader(x)
        y = self.leader(y)

        if x == y:
            return 0

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

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

        return self.parent[x]

    def same(self, x, y) -> bool:
        return self.leader(x) == self.leader(y)

    def leader(self, x) -> int:
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.leader(self.parent[x])
            return self.parent[x]

    def size(self, x) -> int:
        return -self.parent[self.leader(x)]

    def groups(self) -> List[Set[int]]:
        groups = dict()

        for i in range(self.n):
            p = self.leader(i)
            if not groups.get(p):
                groups[p] = set()
            groups[p].add(i)

        return list(groups.values())

def main():
    N,M = map(int, input().split())

    uf = UnionFind(N)

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

    print(len(uf.groups()) - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

#!/usr/bin/python
# -*- coding: utf-8 -*-

# def
def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

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

def print_space(l):
    return print(" ".join([str(x) for x in l]))

# import
import numpy as np
import collections as col
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

# main
N,M =int_map()
AB = int_mtx(M)

n, _ = connected_components(csr_matrix(([1]*M, (AB[:,0]-1, AB[:,1]-1)),(N,N)))

print(n-1)

Submission status: Accepted

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

par = [0]*(N+1)

for i in range (N+1): #[0,1,2,...,N]を作成
    par[i] = i

#木の根を求める関数
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

#根が同じならTrue,別ならFalseを返す関数
def find(x,y):
    return root(x)==root(y)

#経路を圧縮して連結させる関数
def union(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    par[x] = y

for l in L:
    union(l[0],l[1])

R = [0]
R[0] = root(par[1])
for i in range(2,N+1):
    if R[0] != root(par[i]):
        R.append(root(par[i]))

print(len(set(R))-1)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(self.n))
        self.rank = [1] * n
        self.cnt = n
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.rank[p] += self.rank[q]
        self.par[q] = p
        self.cnt -= 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return self.rank[x]
    def count(self):
        return self.cnt
n, m = map(int, input().split())
UF = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    UF.unite(a - 1, b - 1)
print(UF.count() - 1)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
city=[0]*(N+10)

#都市情報を初期化
for i in range(1,N+1):
  city[i]=i
  
#都市番号の小さい方を根としてUnionFind木を作成(大きい方を書き換える)
for i in range(M):
  A,B=map(int,input().split())
#  print(A,B)

#ルートチェック
  if city[A]!=A:
    root=city[A]
    while city[root]!=root:
      root=city[root]
    city[A]=root
  
  if city[B]!=B:
    root=city[B]
    while city[root]!=root:
      root=city[root]
    city[B]=root

#結合
  if city[A]!=city[B]:
    city[city[B]]=city[A]
    
#print(city)
  
#木が何種類あるかチェック
ck=[0]*(N+10)
for i in range(1,N+1):
  if city[i]!=i:
    root=city[i]
    while city[root]!=root:
      root=city[root]
    city[i]=root
    
  if ck[city[i]]==0:
    ck[city[i]]=1
    
#print(city)
#print(ck)
Ans=sum(ck)-1 #木の数-1=必要な道路数

print(Ans)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
nodes = range(1,n+1)
edges = {v: set() for v in nodes}
for _ in range(m):
  a, b = map(int, input().split())
  edges[a].add(b)
  edges[b].add(a)

visited = {v: False for v in nodes}
cnt = -1
for v in nodes:
  if not visited[v]:
    visited[v] = True
    que = deque([v])
    while que:
      p = que.popleft()
      for q in edges[p]:
        if not visited[q]:
          visited[q] = True
          que.append(q)
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

import sys
input = sys.stdin.readline

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

par = [-1]* n
rank = [0]*n

for i in range(m):
    a,b = map(int, input().split())
    a, b =a-1, b-1
    Unite(a,b,par,rank)

cnt = 0
for i in range(n):
    if par[i] < 0:
        cnt += 1
print(cnt-1)

Submission status: Accepted

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

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

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.co -= 1

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

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

  def set_count(self):
    return self.co

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = map(int, input().split())
  uf.unite(a-1, b-1)
print(uf.set_count()-1)

Submission status: Accepted

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

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

  def unite(self, x, y):
    x = self.find_root(x)
    y = self.find_root(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.co -= 1

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

  def size(self, x):
    return -self.n[self.find_root(x)]

  def set_count(self):
    return self.co

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = map(int, input().split())
  uf.unite(a-1, b-1)
print(uf.set_count()-1)

Submission status: Accepted

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

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

  def unite(self, x, y):
    x = self.find_root(x)
    y = self.find_root(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.co -= 1

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

  def size(self, x):
    return -self.n[self.find_root(x)]

  def set_count(self):
    return self.co

import sys
input = lambda:sys.stdin.readline().rstrip()

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
  a, b = map(int, input().split())
  uf.unite(a-1, b-1)
print(uf.set_count()-1)

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())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
print(len(uf.roots())-1)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
#import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def dfs(c, to, seen, g = None):
    if g == None:g = set()
    g.add(c)
    seen.add(c)
    for n in to[c]:
        if not n in seen:
            dfs(n, to, seen, g)
    return g, seen


def run():
    N, M = mapline()
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = mapline()
        to[a].append(b)
        to[b].append(a)

    seen = set()
    G = []
    for i in range(1, N+1):
        if not i in seen:
            g, seen = dfs(i, to, seen)
            #print(i, seen)
            G.append(g)
    #print(G)
    print(len(G) -1)



if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
N, Q = map(int,input().split())
#N,Q=map(int,input().split())
#親のノードを格納　2の親が4のとき par[2]=4
par=[0]
#木の深さを格納　根が2の深さが3の時 rank[2]=3
rank=[0]

#初期化
for i in range(1,N+1):
    par.append(i)
    rank.append(0)

#xの根を探す、同時に通過したノードすべてを根に直接つける
def find(x):
    #xの親がxならば根なのでxを返す
    if par[x]==x:
        return x
    else:
        #違う場合は親の親を捜し自分の親にする
        par[x] = find(par[x])
        #再帰的に行うと根が見つかる
        return par[x]

#xが属する木とyが属する木を併合する
def unite(x,y):
    #根を探す
    root_x=find(x)
    root_y=find(y)

    #根が同じなら元からつながっているので終わり
    if root_x == root_y:
        return

    #ランクが大きい木の根の直下にランクが小さい木を結合
    if rank[root_x] < rank[root_y]:
        par[root_x] = root_y

    else:
        par[root_y] = root_x

    #ランクが等しいときのみランクが増える#なぜ#yにxが結合？
    if rank[root_x]==rank[root_y]:
        rank[root_x]+=1

#xとyが同じ木に存在するかを調べる
def same(x,y):
    return find(x)==find(y)

#main
for i in range(Q):
    a,b=map(int,input().split())
    unite(a, b)
res = []
for i in range(1, N+1):
    res.append(find(i))
ans = len(set(res))-1
print(ans)

Submission status: Accepted

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

n,m=map(int,input().split())
g=[[] for i in range(10**5+10)]
for i in range(m):
  a,b=map(lambda x:int(x)-1, input().split())
  g[a].append(b)
  g[b].append(a)
chk=[-1]*n

def dfs(s,cnt):
  for u in g[s]:
    if chk[u]>-1: continue;
    chk[u]=cnt
    dfs(u,cnt)

cnt=0
for i in range(n):
  if chk[i]==-1:
    chk[i]=cnt
    dfs(i,cnt)
    cnt+=1
    
print(max(chk))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
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())
      
uf=UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)

print(len(uf.roots())-1)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-
# https://atcoder.jp/contests/atc001/tasks/unionfind_a

import sys
sys.setrecursionlimit(10001000)

class UnionFind:
    def __init__(self, n):                      #初期化
        self.n = n                              # 要素数
        self.parents = [i for i in range(n)]    # 親
        self.ranks = [0] * n                    # 木の深さ
        self.sizes = [1] * n                    # グループの要素数

    def find(self, x):              # 親を出力
        if self.parents[x] == x:
            return x
        else:
            p = self.find(self.parents[x])
            self.parents[x] = p
            return p

    def unite(self, x, y):          # ユニオン
        x = self.find(x)
        y = self.find(y)
        if x == y: return
        if self.ranks[x] > self.ranks[y]:
            x , y = y, x    #yを親にする
        if self.ranks[x] == self.ranks[y]:
                self.ranks[y] += 1
        self.parents[x] = y
        self.sizes[y] += self.sizes[x]

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def size(self, x):          #グループの要素数
        return self.sizes[self.find(x)]

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if i == x}

    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())
uf = UnionFind(n)
for _ in range(m):
    a,b = map(int,input().split())
    uf.unite(a-1, b-1)

print(uf.group_count()-1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
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())
    
    
def main():
    V, M = MI()
    uni = UnionFind(V)
    for i in range(M):
        a,b = MI()
        a-=1
        b-=1
        uni.union(a,b)
    
    print(uni.group_count()-1)

if __name__ == "__main__":
    main()