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 ).

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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():
    N, M = [int(x) for x in input().split()]
    AB = [[int(x) for x in input().split()] for _ in range(M)]

    uf = UnionFind(N)

    for a, b in AB:
        uf.union(a - 1, b - 1)

    print(uf.group_count() - 1)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())
class UnionFind:
    def __init__(self, n):
        self.parents = [-1] * (n + 1)
        self.rank = [0] * (n + 1)

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

    def unite(self, x, y) -> bool:
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
        return True

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

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

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

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

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

def main():
    N, M = i_map()
    u = UnionFind(N)
    for _ in range(M):
        A, B = i_map()
        u.unite(A, B)
    ans = len(u.roots()) - 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(int(1e9))

class uft:
  def __init__(self, N):
    self.__N = N
    self.__arr = [-1] * (N + 1)
  def fp(self, x):
    if self.__arr[x] < 0:
      return x
    else:
      self.__arr[x] = self.fp(self.__arr[x])
      return self.__arr[x]
  def add(self, x, y):
    px = self.fp(x)
    py = self.fp(y)
    if px > py:
      px, py = py, px
    if px == py:
      return 1
    self.__arr[px] += self.__arr[py]
    self.__arr[py] = px
  def groups(self):
    ret = -1
    for i in self.__arr:
      if i < 0:
        ret += 1
    return ret
  def show_arr(self):
    print(self.__arr)
  
N, M = map(int, input().split()) 
UFT = uft(N)

for i in range(M):
  A, B = map(int, input().split())
  UFT.add(A,B)
print(UFT.groups() -1)

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

arr=[[] for i in range(n+1)]

gro=[0]*(n+1)

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

from collections import deque
deque=deque()

gro_no=0

for i in range(1,n+1):
    if gro[i]==0:
        gro_no+=1
        gro[i]=gro_no
        deque.append(i)

    while deque:
        j=deque.popleft()
        for k in arr[j]:
            if gro[k]==0:
                gro[k]=gro_no
                deque.append(k)

print(gro_no-1)

Solution (Python):
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 solve():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for i in range(M):
        a,b = map(lambda x: int(x)-1, input().split())
        uf.union(a,b)
    print(uf.group_count() - 1)

if __name__ == '__main__':
    solve()

Solution (Python):
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)
cnt = 0
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)
for i in uf.parents:
    if i < 0:
        cnt += 1
    
print(cnt - 1)

Solution (Python):

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 groups(self):
        groups = dict()
        for i in range(self.n):
            p = self.find(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.union(a,b)
    print(len(uf.groups())-1)

if __name__ == '__main__':
    main()

Solution (Python):
(N,M),*AB=[list(map(int, x.split())) for x in open(0).readlines() if len(x)>1]

class UnionFind:
    def __init__(self, n):
        self.n=n
        self.parents=[-1 for i in range(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):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.parents[rx] > self.parents[ry]:
            rx,ry=ry,rx
        self.parents[rx] = self.parents[ry]
        self.parents[ry] = rx

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


d=UnionFind(N)
for a,b in AB:
    d.union(a-1,b-1)
print(d.group_count() - 1)

Solution (Python):

import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


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


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


def main():
    N, M = MI()

    routes = []

    cities = [[] for i in range(N)]

    for i in range(M):
        a, b = MI()
        cities[a-1].append(b-1)
        cities[b-1].append(a-1)

    groups = [-1] * N

    group = 0

    for i in range(N):
        if groups[i] != -1:
            continue
        deque = cl.deque([i])
        groups[i] = group
        while len(deque) > 0:
            city = deque.popleft()
            next_cities = cities[city]
            for next_city in next_cities:
                if groups[next_city] != -1:
                    continue
                groups[next_city] = group
                deque.append(next_city)

        group += 1

    print(group - 1)


main()

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)

class UnionFind:
    """素集合を木構造として管理する。"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.n = n
        self.cnt = n
 
    def root(self, x):
        """要素xの代表元を求める。O(α(N))"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
 
    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を併合する。O(α(N))"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1
        return True
 
    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める。O(α(N))"""
        return self.root(x) == self.root(y)
 
    def size(self, x):
        """要素xを含む集合の要素数を求める。O(α(N))"""
        return -self.parent[self.root(x)]
 
    def count(self):
        """集合の個数を求める。O(1)"""
        return self.cnt
 
    def groups(self):
        """集合を列挙する。list[list[int]]で返す。O(N)"""
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            res[self.root(i)].append(i)
        return [group for group in res if group]

N,Q = map(int,readline().split())
uf = UnionFind(N)

for _ in range(Q):
    x,y = map(int,readline().split())
    x-=1; y-=1
    uf.merge(x,y)

print(uf.count()-1)

Solution (Python):

import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y] 
        par[y] = x 
        return 


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


def size(x):
    return -par[find(x)]

N,Q = map(int,readline().split())

par = [-1]*N
for _ in range(Q):
    x,y = map(int,readline().split())
    x-=1; y-=1
    union(x,y)

ans = set()
for i in range(N):
    ans.add(find(i))
print(len(ans)-1)

Solution (Python):
def dfs(node):
  visited[node]=True
  stack=[node]
  while stack:
    node=stack.pop()
    for child in g[node]:
      if visited[child]==False:
        visited[child]=True
        stack.append(child)
n,m=map(int,input().split())
g={i:[] for i in range(1,n+1)}
for i in range(m):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
visited=[False for i in range(n+1)]
c=0
for i in range(1,n+1):
  if visited[i]==False:
    c=c+1
    dfs(i)
print(c-1)

Solution (Python):
from sys  import stdin,stdout

from collections import Counter

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:map(int,stdin.readline().split())
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

from bisect import bisect_left,bisect_right

mod=1000000007
INF=float('inf')
def DFS(n,d,v):
    v[n]=False
    stack=[n]
    while stack:
        a=stack.pop()
        for i in d[a]:
            if not v[i]:
                stack.append(i)
                v[i]=True
                
def solve():
    n,m=mp()
    d={i:[] for i in range(n+1)}
    for i in range(m):
        a,b=mp()
        d[a].append(b)
        d[b].append(a)
    ans=0
    v=[False for  i in range(n+1)]
    for i in range(1,n+1):
        if not v[i]:
            ans+=1
            DFS(i,d,v)
    pr(ans-1)
    
    
for _ in range(1):

    solve()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

def find(Data, x):
    if Data[x] < 0:
        return x
    else:
        Data[x] = find(Data, Data[x])
        return Data[x] 

def unite(Data, a, b):
    a, b = find(Data, a), find(Data, b)
    if a == b:
        pass
    elif Data[a] < Data[b]:
        Data[a] = Data[a] + Data[b]
        Data[b] = a
    else:
        Data[b] = Data[b] + Data[a]
        Data[a] = b 

n, m = map(int, input().split())
UF = [-1 for i in range(n)]
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1, bi - 1
    unite(UF, ai, bi)

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

Solution (Python):
class UnionFind():
    def __init__(self, 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

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

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

cnt = 0
for item in uf.parents:
    if item < 0:
        cnt += 1

print(cnt-1)

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

roads=[]

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

group2=[]

while group2!=group:
  group2=list(group)
  for road in roads:
    if group[road[1]-1]>group[road[0]-1]:
      group[road[1]-1]=group[road[0]-1]
    else:
      group[road[0]-1]=group[road[1]-1]
  
counter=1
group.sort()

for i in range(n-1):
  if group[i]!=group[i+1]:
    counter+=1

print(counter-1)

Solution (Python):

import sys;input = sys.stdin.readline

inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

class DisjSet: 
    def __init__(self,n): 
        self.rank = [1]*n 
        self.parent = [i for i in range(n)] 

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

    def Union(self,x,y):
        xset = self.find(x) 
        yset = self.find(y)
        if xset == yset: return

        if self.rank[xset] < self.rank[yset]: 
            self.parent[xset] = yset 
        elif self.rank[xset] > self.rank[yset]: 
            self.parent[yset] = xset 
        else: 
            self.parent[yset] = xset 
            self.rank[xset] += 1

n,m = ip()
obj = DisjSet(n)
for i in range(m):
    a,b = ip()
    obj.Union(a-1,b-1)
dt = {}
for i in range(n):
    p = obj.find(i)
    dt[p] = dt.get(p,0)+1
print(len(dt.keys())-1)

Solution (Python):
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()

Solution (Python):
import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 

import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'




def solve():
    n, m = map(int, input().split())

    adj_list = {x: [] for x in range(1, n + 1)}

    uf = [x for x in range(n + 1)]
    sz = [1]  * (n + 1)

    def find(i):
        while uf[i] != i:
            uf[i] = uf[uf[i]]
            i = uf[i]
        return i

    def check(i, j):
        return find(i) == find(j)

    def union(i, j):
        a = find(i)
        b = find(j)
        if sz[a] < sz[b]:
            uf[a] = uf[b]
            sz[b] += sz[a]
        else:
            uf[b] = uf[a]
            sz[a] += sz[b]

    for _ in range(m):
        a, b = map(int, input().split())
        if not check(a, b):
            union(a, b)

    sets = 0

    for i in range(1, n + 1):
        if uf[i] == i:
            sets += 1

    cout<<sets - 1<<endl




def main():
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
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())
    a -= 1
    b -= 1
    
    uf.union(a, b)
    

print(uf.group_count() - 1)

Solution (Python):
from collections import Counter
N, M = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]

    def unite(self, x, y):
        if not self.same(x, y):
            self.root[self.find(y)] = self.find(x)

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
UF = UnionFind(N)
ans = N-1
for _ in range(M):
  x, y = map(int, input().split())
  if not UF.same(x-1, y-1):
    UF.unite(x-1, y-1)
    ans -= 1
print(ans)

Solution (Python):
import types

_atcoder_code = """


__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_dsu_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))
"""

atcoder.dsu = types.ModuleType('atcoder.dsu')
exec(_atcoder_dsu_code, atcoder.dsu.__dict__)
DSU = atcoder.dsu.DSU


def solve():
    N,M = map(int,input().split())
    uf = DSU(N)

    for _ in range(M):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        uf.merge(a,b)
    
    print(len(uf.groups())-1)
    
if __name__ == '__main__':
    solve()

Solution (Python):
f = lambda x: x if p[x]<0 else f(p[x])
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)-1),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-1)

Solution (Python):
def f(x):
  while p[x]>0: x = p[x]
  return x
N,M = map(int,input().split())
p = [-1]*N
for _ in range(M):
  A,B = map(lambda x:f(int(x)-1),input().split())
  if A==B: continue
  elif A<B: A,B=B,A
  p[A] += p[B]
  p[B] = A
print(sum(i<0 for i in p)-1)

Solution (Python):
import sys
input = sys.stdin.readline

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

def main():
    mod=10**9+7
    class UnionFind:
        def __init__(self, N: int):
            """
            N:要素数
            root:各要素の親要素の番号を格納するリスト.
                 ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
            rank:ランク
            """
            self.N = N
            self.root = [-1] * N
            self.rank = [0] * N

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

        def find(self, x: int):
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                while self.root[x] >= 0:
                    x = self.root[x]
                return x

        def union(self, x: int, y: int):
            """x,yが属する木をunion"""
            
            
            
            
            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
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rank[x] == self.rank[y]:
                    self.rank[y] += 1

        def same(self, x: int, y: int):
            """xとyが同じグループに属するかどうか"""
            return self.find(x) == self.find(y)

        def count(self, x):
            """頂点xが属する木のサイズを返す"""
            return - self.root[self.find(x)]

        def members(self, x):
            """xが属する木の要素を列挙"""
            _root = self.find(x)
            return [i for i in range(self.N) if self.find == _root]

        def roots(self):
            """森の根を列挙"""
            return [i for i, x in enumerate(self.root) 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()}
        
    N,M=MI()
    uf=UnionFind(N)
    for _ in range(M):
        a,b=MI()
        a-=1
        b-=1
        uf.union(a,b)
        
    cnt=uf.group_count()
    print(cnt-1)

main()

Solution (Python):
N,M = map(int,input().split())
par = [0]+[-1 for i in range(N)]

def find(x):
    if par[x] == -1:
        return x
    else:
        par[x] = find(par[x]) 
        return par[x]

def same(x,y):
    return find(x) == find(y)
  
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(len([i for i in par if i == -1])-1)

Solution (Python):
from collections import Counter
import sys
input = sys.stdin.readline


class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)

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

UF = UnionFind(N)

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

UF.updatePars()

cnt = Counter(UF.pars)

ans = len(cnt.keys()) - 1
print(ans)