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):
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 unite(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())

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=u.roots()
print(len(ans)-1)

Solution (Python):
def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)

def print_gen(gen):
    print(len([list(x) for x in gen]) - 1)

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)  
graphA = {}
for i in range(n):
    graphA[i] = graph[i]

print_gen(connected_components(graphA))

Solution (Python):
def nxto(u):
  for val in m[u]:
    if c[val] == 0:
      return val
    
  return None

def dfs(ix):
  stk = [ix]
  c[ix] = 1
  while stk != []:
    l = stk[-1]
    nxt = nxto(l)
    if nxt is not None:
      c[nxt] = 1
      stk.append(nxt)
    else:
      stk.pop()

N, M = list(map(int, input().split(" ")))
c = [0 for _ in range(N+1)]
m = [[] for _ in range(N+1)]
for _ in range(M):
  a, b = list(map(int, input().split(" ")))
  m[a].append(b)
  m[b].append(a)

cnt = -1
for i in range(1, N+1):
  if c[i] == 0:
    dfs(i)
    cnt += 1
print(cnt)

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

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=u.roots()
print(len(ans)-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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(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(uf.group_count()-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())

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)


print(uf.group_count()-1)

Solution (Python):

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



cities = {}
 
for a in range(N):
    cities[a+1] = []

 
for i in range(M):
    i1, i2 = map(int, input().split())
    cities[i1].append(i2)
    cities[i2].append(i1)

def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)
print(len([list(x) for x in connected_components(cities)])-1)

Solution (Python):





pl = list()

def root(in_root):
    if pl[in_root] == in_root:
        return in_root
    else:
        pl[in_root] = root(pl[in_root])
        return pl[in_root]

def isSame(in_a, in_b):
    if root(pl[in_a]) == root(pl[in_b]):
        return True
    else:
        return False

def unite(in_a, in_b):
    wk_a = root(in_a)
    wk_b = root(in_b)
    if wk_a == wk_b:
        return False
    else:
        if wk_a < wk_b:
            pl[wk_b] = wk_a
        else:
            pl[wk_a] = wk_b


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


for i in range(n+1):
    pl.append(i)


for i in range(m):
    a, b = map(int,input().split())
    wa = min(a, b)
    wb = max(a, b)
    unite(wa, wb)


ans = 0
for i in range(1, n+1):
    if pl[i] == i:
        ans = ans + 1


print(ans-1)

Solution (Python):
class DSU:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), 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, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        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):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]

    def groups(self):
        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 [r for r in result if r != []]


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

dsu = DSU(N)

for _ in range(M):
    A_M, B_M = tuple(map(int, input().split()))
    
    A_M -= 1
    B_M -= 1
    leader_A_M = dsu.leader(A_M)
    leader_B_M = dsu.leader(B_M)
    dsu.merge(leader_A_M, leader_B_M)



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

Solution (Python):
'''
Created on 2020/09/26

@author: harurun
'''

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():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N,M=map(int,pin().split())
  ans=0
  uf=UnionFind(N)
  for i in range(M):
    A,B=map(int,pin().split())
    uf.union(A-1, B-1)
  print(uf.group_count()-1)
  return 
main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7+1)

N,M = map(int,input().split())
V = [i for i in range(N)]
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        if visited[e]:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

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


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)


print(uf.group_count() - 1)

Solution (Python):
import sys

sys.setrecursionlimit(100000)

import numpy as np


def main():
    n_num, m_num = map(int, input().split())
    
    c_map = []
    for _ in range(n_num):
        c_map.append([])
    

    for _ in range(m_num):
        a, b = map(int, input().split())
        if a > b:
            a, b = b, a
        
        c_map[a-1].append(b-1)
        c_map[b-1].append(a-1)
    

    city_info = np.zeros(n_num, dtype='int32')
    land_city = 0

    def move(a, b):
        if a in c_map[b]:
            return 1
        else:
            return 0

    def recr(c):
        city_info[c] = 1
        for n in c_map[c]:
            if city_info[n] == 0:
                if move(c, n) == 1:
                    recr(n)

    for n in range(n_num):
        if city_info[n] == 0:
            land_city += 1
            recr(n)
    
    
    print(land_city - 1)


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

    
from sys import stdin
imput = stdin.readline
n,m = map(int, input().split())  
uf = UnionFind(n)


num_list = []
for i in range(m):
    num_list.append(list(map(int,input().split())))

for i in range(m):
    
    
    uf.union(num_list[i][0]-1, num_list[i][1]-1)
    
print(uf.group_count()-1)

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

    def root(self,x):
        stack = []
        tbl = self.table
        while tbl[x]>=0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self,x,y):
        return self.root(x)==self.root(y)
    def union(self,x,y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -=1
        else:
            self.table[r1] = r2
N,M = map(int,input().split())
AB = []
for i in range(M):
    AB.append(list(map(int,input().split())))
uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0]-1,AB[i][1]-1)
r = [0]*N
for i in range(N):
    r[i]=uf.root(i)
print(len(set(r))-1)

Solution (Python):
import sys
 
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
 
 
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 = map(int, readline().split())
    uf = UnionFind(N)
 
    for _ in range(M):
        a, b = map(int, readline().split())
        uf.union(a - 1, b - 1)
    print(uf.group_count() - 1)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
from networkx import *

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

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

m3 = list(connected_components(G))

count = 0

if len(max(connected_components(G), key=len)) == n:
    print(0)
    exit()
else:
    for i in m3:
        count += len(i)

sub = n - count

if sub != 0:
    print((len(m3)-1)+sub)

else:
    print(len(m3)+sub-1)

Solution (Python):
N,M=map(int,input().split())
road=[[] for _ in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)
ischecked=[0]*(N)
ans=0
for i in range(N):
    if ischecked[i]==1:
        continue
    ischecked[i]=1
    q=[i]
    while q:
        now=q.pop()
        nex=road[now]
        for j in nex:
            if ischecked[j]!=0:
                continue
            q.append(j)
            ischecked[j]=1
    ans+=1
print(ans-1)

Solution (Python):
from sys import setrecursionlimit
from collections import Counter
import networkx as nx
setrecursionlimit(1000000)
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]

def find_components(n, connectors):
    g = nx.Graph()
    for i in range(n): g.add_node(i+1)
    g.add_edges_from(connectors)
    return len(list(nx.connected_components(g)))


n, m = m_in(int)
ab = [list(m_in(int)) for _ in range(m)]

ans = find_components(n, ab) - 1

print(ans)

Solution (Python):


def resolve(T,v):
    lv = v
    while lv != T[lv]:
        lv = T[lv]
    T[v] = lv
    return lv

def solve():
    N, M = map(int, input().split())
    T = list(range(N+1))
    for i in range(M):
        u, v = map(int, input().split())
        lu = resolve(T,u)
        lv = resolve(T,v)
        if lv == lu:
            continue
        T[lv] = lu
        
        
        
    return len(set(resolve(T,v) for v in range(1,N+1)))-1

if __name__ == '__main__':
    print(solve())

Solution (Python):
n,m=map(int,input().split())
g=[[] for i in range(n)]
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a-1].append(b)
    g[b-1].append(a)
from collections import deque
x=[0]*n
s=1
for i in range(1,n+1):
    if x[i-1]==0:
        x[i-1]=s
        q=deque([i])
        while q:
            v = q.popleft()
            for j in g[v-1]:
                if x[j-1]==0:
                    q.append(j)
                    x[j-1]=s
        s+=1
print(s-2)

Solution (Python):




n,m, = map(int,input().split())
par = [i for i in range(n+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) 
        return par[x]
def 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

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




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

li = [0]*(n+1)
for i in range(1,n+1):
    li[(-size(par[i]))] = 1

print(li.count(1)-1)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0]*(n+1)

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, M = map(int, input().split())
A = [0]*M
B = [0]*M
uf = UnionFind(N)
for i in range(M):
    A[i], B[i] = map(int, input().split())
    uf.union(A[i], B[i])

cnt = 0 

for j in range(1,N):
    if uf.same_check(j, j+1) == False:
        uf.union(j,j+1)
        cnt+=1

print(cnt)

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

print(uf.group_count() -1 )

Solution (Python):
def find(x):
    if par[x] == x:
        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
    size[y] = size[x] + size[y]
    size[x] = 0

N,M = map(int,input().split())
par = [ i for i in range(N+1)]
size = [1 for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    unite(a,b)
A = size.count(0)
print(N-A-1)

Solution (Python):
import math

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



parents = [-1] * n

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

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

    if x == y:
        return

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

    parents[x] += parents[y]
    parents[y] = x

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

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

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

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

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

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

def __str__():
    return '\n'.join('{}: {}'.format(r, members(r)) for r in roots())
 
C = []
for i in range(M):
    A, B = map(int,input().split())
    union(A-1,B-1)
    '''
    c = 0
    for p in C:
        if A in p:
            c = 1
            p.add(B)
        elif B in p:
            c = 1
            p.add(A)
    if c != 1:
        C.append(set([A,B]))
    '''
print(group_count()-1)

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

N,M = map(int,input().split())
table = [[] for i in range(N)]
Q = deque()
visited = [0]*N
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    table[A].append(B)
    table[B].append(A)

for x in range(N):
    if visited[x] == 0:
        ans += 1
        Q.append(x)
        while Q:
            x = Q.popleft()
            for y in table[x]:
                if visited[y]==0:
                    Q.append(y)
                    visited[y] = 1

print(ans-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())
N, M = map(int, input().split())
uf = UnionFind(N)
import sys
input = sys.stdin.readline
import collections
for i in range(M):
  A, B = map(int, input().rstrip().split())
  uf.union(A-1, B-1)
doku = uf.parents.count(-1)
all = uf.group_count() - doku
ans = all + doku -1
print(ans)

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	
	n , m = tin()
	
	
	path = [[] for _ in range(n)]
	for _ in range(m):
		a, b = tin()
		path[a-1].append(b-1)
		path[b-1].append(a-1)
		
	nn = [-1]*n
	st=1
	for i, p in enumerate(nn):
		if nn[i] != -1:
			continue
		nn[i]=st
		cc = st
		st += 1
		q = collections.deque()
		q.append(i)
		while q:
			pos = q.popleft()
			for np in path[pos]:
				if nn[np] == -1:
					q.append(np)
					nn[np]=cc
	return cc-1
			
		
		
	
	
	

isTest=False

def pa(*vl):
	if not isTest:
		return
	for v in vl:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):








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

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):
    uf.union(req[i][0]-1, req[i][1]-1)

print(uf.group_count() - 1)

Solution (Python):
import sys
import math,bisect
sys.setrecursionlimit(10 ** 5)
from itertools import groupby,accumulate
from heapq import heapify,heappop,heappush
from collections import deque,Counter,defaultdict
def I(): return int(sys.stdin.readline())
def neo(): return map(int, sys.stdin.readline().split())
def Neo(): return list(map(int, sys.stdin.readline().split()))
def dfs(t):
    vis[t] = 1
    for i in G[t]:
        if not vis[i]:
            dfs(i)
N,M = neo()
G = defaultdict(list)
vis = [0]*(N+1)
for i in range(M):
    x,y = neo()
    G[x] += [y]
    G[y] += [x]
c = 0
for i in range(1,N+1):
    if not vis[i]:
        dfs(i)
        c += 1
print(c-1)

Solution (Python):
def solve(n, m, a, b):
    E = {i: [] for i in range(n)}
    for u, v in zip(a, b):
        u, v = u-1, v-1
        E[u].append(v)
        E[v].append(u)
    L = list(range(n))
    for s in range(n):
        if L[s] == s:
            L[s] = s
            que = [s]
            while que:
                u = que.pop(0)
                for v in E[u]:
                    if L[v] != s:
                        L[v] = s
                        que.append(v)
    return len(set(L)) - 1
 
n, m = map(int, input().split())
if m == 0:
    a, b = [], []
else:
    a, b = zip(*[map(int, input().split()) for i in range(m)])
print(solve(n,m,a,b))