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):
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):
N, M = [int(n) for n in input().split(" ")]
R = []
for _ in range(M):
    R.append([int(n) - 1 for n in input().split(" ")])


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

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.par[rx] = ry


unionfind = UnionFind(N)
for r in R:
    unionfind.unite(r[0], r[1])

ss = [unionfind.root(n) for n in range(N)]

aaa = list(set(ss))

print(len(aaa) - 1)

Solution (Python):
from collections import deque

def main():
    n, m = list(map(int, input().split(" ")))
    paired_dict = {i: [] for i in range(n)}
    for _ in range(m):
        a, b = list(map(int, input().split(" ")))
        paired_dict[a-1].append(b-1)
        paired_dict[b-1].append(a-1)

    done_set = set([])
    que = deque([a-1])
    i = 0
    ans = 0
    while que:
        x = que.popleft()
        done_set.add(x)
        if x in paired_dict.keys():
            for one in paired_dict[x]:
                if one in done_set:
                    continue
                que.append(one)
                done_set.add(one)

        while (not que) and len(done_set)!=n:
            if i not in done_set:
                que.append(i)
                ans+=1
            i+=1
            if n<i:
                i = 0

    print(ans)

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())
u = UnionFind(n)

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

a = u.roots()
print(len(a)-1)

Solution (Python):
import sys

def dfs(c):
    if seen[c]==0:
        seen[c]=1
        for nc in clis[c]:
            dfs(nc)

sys.setrecursionlimit(10**7)


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

clis=[[] for _ in range(n)]

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

seen=[0 for i in range(n)]
cnt=0

for ci in range(n):
    if seen[ci]!=0:
        continue
    dfs(ci)
    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 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)

total=uf.group_count()
print(total-1)

Solution (Python):
import sys
sys.setrecursionlimit(int(2e6))

def dfs(u, p = 0):
  vis[u] = True
  for v in g[u]:
    if not vis[v]:
      dfs(v, u)

n, m = map(int, input().split())
assert 2 <= n <= int(1e5)
assert 1 <= m <= int(1e5)
g = [list() for i in range(n + 1)]
for i in range(m):
  u, v = map(int, input().split())
  assert 1 <= u <= int(1e5)
  assert 1 <= v <= int(1e5)
  assert u < v
  g[u].append(v)
  g[v].append(u)
c = 0
vis = [False] * (n + 1)
for i in range(1, n + 1):
  if not vis[i]:
    c += 1
    dfs(i)
print(c - 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
        
        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 same(self, x, y):
        
        return self.find(x) == self.find(y)

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

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


def resolve():
    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(len(uf.roots()) - 1)

resolve()

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)

edge = []
for i in range(m):
    a,b = map(int,input().split())
    edge.append((a-1,b-1))
    
for a,b in edge:
    uf.union(a, b)
    
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 _ in range(M):
    a,b=map(int, input().split())
    uf.union(a-1,b-1)
cnt = 0
for i in range(N-1):
    if(not uf.same(i,i+1)):
        cnt += 1
        uf.union(i+1,i)
print(cnt)

Solution (Python):
import math
import sys
import os

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

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 = LI()
AB = [LI() for _ in range(M)]
ans = 0

road = UnionFind(N)
for r in AB:
    f = r[0]-1
    t = r[1]-1
    road.union(f,t)


ans = road.group_count() - 1

print(ans)

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): uf.union(*map(lambda x: int(x)-1, input().split())) 
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 = list(map(int, input().split()))
root = []
for i in range(M):
    x = list(map(int, input().split()))
    root.append(x)
uf = UnionFind(N)
for i in range(M):
    a, b = root[i]
    a, b = a - 1, b - 1
    uf.union(a, b)
gc = uf.group_count()
print(gc - 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 _ in range(m):
  a,b = map(int,input().split())
  uf.union(a-1,b-1)
  
ans = uf.group_count() - 1
print(ans)

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 resolve():
  N, M = map(int, input().split(" "))
  connections = UnionFind(N)
  for _ in range(M):
    A, B = map(int, input().split(" "))
    A -= 1
    B -= 1
    connections.union(A, B)
  print(len(connections.roots()) - 1)

if __name__ == "__main__":
  resolve()

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

uf = UnionFind(N + 1)
for i in range(M):
    uf.union(*list(map(int, input().split())))

print(uf.group_count()-2)

Solution (Python):
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")



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

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

    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]



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

    T = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        T.Unite(a, b)
    
    ans = 0
    used = [False] * N
    for i in range(1,N+1):
        r = T.Find_Root(i) - 1
        if used[r] == False:
            used[r] = True
            ans += 1
    
    print(ans - 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())

def main():
    N,M = list(map(int,input().split()))
    uf = UnionFind(N+1)
    ab = [list(map(int,input().split())) for i in range(M)]

    uf = UnionFind(N+1)
    for i in range(M):
        uf.union(ab[i][0],ab[i][1])
    print(uf.group_count()-2)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict








def solve(grid, n):  
    console("----- solving ------")
    grid = [(x-1, y-1) for x,y in grid]
    
    grid = sorted(grid)
    console(grid, n)

    g = defaultdict(list)

    for x,y in grid:
        g[x].append(y)
        g[y].append(x)

    console(g)

    res = [0 for _ in range(n)]
    visited_1 = [0 for _ in range(n)]

    result = 0  

    for i in range(n):
        if visited_1[i]:  
            continue
        visited_1[i] = 1
        stack = [i]
        cnt = 1
        result += 1
        while stack:
            cur = stack.pop()
            for nex in g[cur]:
                if not visited_1[nex]:
                    cnt += 1
                    visited_1[nex] = 1
                    stack.append(nex)
                

    
    console(result)
    console(visited_1)
    
    
    

    return result - 1




def console(*args):  
    
    return


inp = sys.stdin.readlines()

for case_num in [1]:
    
    

    
    
    
    
    

    
    k, nrows = list(map(int,inp[0].split()))

    
    
    
    grid = []
    for n in range(nrows):
        grid.append(list(map(int,inp[n+1].split())))

    res = solve(grid, k)  
    
    
    
    

    
    print(res)

Solution (Python):
class dsu:
    def __init__(self, N):
        self.root = [-1 for _ in range(N)]
        self.size = [1 for _ in range(N)]

    def merge(self, x, y):
        x = self.leader(x)
        y = self.leader(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.root[x] = y
            self.size[y] += self.size[x]
        else:
            self.root[y] = x
            self.size[x] += self.size[y]
    
    def leader(self, x):
        while self.root[x] >= 0:
            x = self.root[x]
        return x

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

N, M = [int(_) for _ in input().split()]
uf = dsu(N)

for i in range(M):
    A, B = [int(_) - 1 for _ in input().split()]
    uf.merge(A, B)

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

Solution (Python):
import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:
  def __init__(self, data, reverse=False):
    self.reverse = -1 if reverse else 1
    self.data = [self.reverse * d for d in data]
    HQ.heapify(self.data)
  def push(self, x): return HQ.heappush(self.data, self.reverse * x)
  def pop(self): return self.reverse * HQ.heappop(self.data) 

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


ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def Ss(): return list(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

n, m = I()
cities = UnionFind(n)
for _ in range(m):
  a, b = I()
  cities.union(a-1, b-1)

print(cities.group_count() - 1)

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



ab = [[] for i in range(n)]

ki = UnionFind(n)

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

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








def solve(N, M, A, B):
    dsu = atcoder.dsu.DSU(N)
    for i in range(M):
        dsu.merge(A[i] - 1, B[i] - 1)
    num_groups = len(dsu.groups())
    return num_groups - 1



def main():
    N, M = map(int, input().split())
    A = [None for _ in range(M)]
    B = [None for _ in range(M)]
    for i in range(M):
        A[i], B[i] = map(int, input().split())
    b = solve(N, M, A, B)
    print(b)


if __name__ == '__main__':
    main()

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

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

    self.rank = [0] * (n+1)

  def find(self, x):
    if self.par[x] < 0:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  
  def same_check(self, x, y):
    return self.find(x) == self.find(y)
  
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return False
    else:
      if self.par[x] > self.par[y]:
        x,y = y,x
      self.par[x] += self.par[y]
      self.par[y] = x

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



uni = UnionFind(n)

for i in range(m):
  uni.unite(ab[i][0],ab[i][1])

result = 0
for i in range(1,n+1):
  if uni.par[i] < 0:
    result += 1
print(result-1)

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

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

N = [[] for _ in range(n)]
V = [0] * n
counter = -1

for _ in range(m):
  x,y = list(map(int, input().split()))
  x -= 1
  y -= 1
  N[x].append(y)
  N[y].append(x)
  
for i in range(n):
  
  if V[i]==0:
    Q = [i]
    while Q:
      node = Q.pop()
      V[node]=1
      for child in N[node]:
        if V[child]==0:
          Q.append(child)
          V[child] = 1
    counter += 1
    
print(counter)