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 bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    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()
    uf = UnionFind(n)

    for i in range(m):
        a, b = LI()
        a -= 1
        b -= 1
        uf.union(a, b)

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


main()

Solution (Python):
class unionfind():
    def __init__(self, n):
        self.parents = [-1 for i in range(n)]

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if x < y:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self):
        return len(list(filter(lambda x: x < 0, self.parents))) - 1

n, m = map(int, input().split())
uf = unionfind(n)
for i in range(m):
    tmp = list(map(int, input().split()))
    uf.union(tmp[0] - 1, tmp[1] - 1)

print(uf.size())

Solution (Python):
def resolve():
    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)
    grp = UF.group_count()
    if grp == 1:
        print(0)
    else:
        print(grp-1)

resolve()

Solution (Python):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for x in range(M)]

group = 0
parents = [-1]*N

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

def union(x,y):
    global parents
    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

for q in range(M):
    union(AB[q][0]-1,AB[q][1]-1)

for p in range(N):
    if parents[p] < 0:
        group += 1

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

g = [[]*(n+1) for _ in range(n+1)]

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for i in range(m):
    x, y = ab[i][0], ab[i][1]
    x -= 1
    y -= 1
    uf.union(x, y)
print(uf.group_count()-1)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())

root = [-1]*n

def find(n):
    if root[n] < 0:
        return n
    else:
        root[n] = find(root[n])
        return root[n]

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    else:
        root[x] += root[y]
        root[y] = x

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

ans = -1
for i in root:
    if i < 0:
        ans += 1

print(ans)

Solution (Python):
import sys

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

input = sys.stdin.readline
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):
import sys


class UnionFind:
    def __init__(self, N):
        self.N = N  
        
        self.parent = [-1] * N

    def root(self, A):
        
        
        
        if self.parent[A] < 0:
            return A
        self.parent[A] = self.root(self.parent[A])
        return self.parent[A]

    def size(self, A):
        
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        
        
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False  

        if self.size(A) < self.size(B):
            
            
            A, B = B, A

        
        self.parent[A] += self.parent[B]
        
        self.parent[B] = A

        return True

    def same(self, A, B):
        return self.root(A) == self.root(B)



input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    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.unite(a, b)

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


if __name__ == "__main__":
    main()

Solution (Python):


class UnionFindTree:
    def __init__(self, n):
        self._tree = [i for i in range(n)]
        self._rank = [1] * n
    def root(self, a):
        if self._tree[a] == a:return a
        self._tree[a] = self.root(self._tree[a])
        return self._tree[a]
    def is_same_set(self, a, b):
        return self.root(a) == self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._rank[ra] < self._rank[rb]:
            self._tree[ra] = rb
        else:
            self._tree[rb] = ra
            if self._rank[ra] == self._rank[rb]:
                self._rank[ra] += 1

def solve(n, m, x):
    uft = UnionFindTree(n)
    for a,b in x:
        uft.unite(a-1, b-1)
    return len(set(uft.root(i) for i in range(n)))-1

if __name__ == "__main__":
    n,m = map(int, input().split())
    *edges, = [list(map(int, input().split())) for _ in range(m)]
    print(solve(n,m,edges))

Solution (Python):
from collections import defaultdict
from sys import setrecursionlimit
setrecursionlimit(10**6)
n,m=map(int,input().split())
d=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    d[a].append(b)
    d[b].append(a)
def dfs(node):
    vis.add(node)
    for i in d[node]:
        if i not in vis:
            dfs(i)
vis=set()
ans=0
for i in range(1,n+1):
    if i not in vis:
        dfs(i)
        ans+=1
print(ans-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())


uf = UnionFind(N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a, b)


ans = 0
now = 1
for i in range(1, N + 1):
    if i == 1:
        continue

    if uf.same(now, i):
        continue
    else:
        uf.union(now, i)
        ans += 1
print(ans)

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

global fri
fri=[]
global tab
tab=[0]*n
def run(nn):
  
  global cnt
  if tab[nn]:
    return
  tab[nn]=1
  cnt+=1
  for i in fri[nn]:
    que.append(i)
for i in range(n):
  fri.append([])
for i in range(m):
  a,b=map(int,input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
i=0
mx=0
cc=0
while i<n:
  if tab[i]:
    i+=1
    continue
  que=[i]
  cnt=0
  while len(que)!=0:
    run(que.pop())
  mx=max(cnt,mx)
  i+=1
  cc+=1
print(cc-1)

Solution (Python):
import networkx as nx


def solve(n, m, ab_list):
    g = nx.Graph()
    g.add_nodes_from(list(range(1, n + 1)))
    g.add_edges_from(ab_list)
    res = nx.algorithms.components.number_connected_components(g) - 1
    return res


def main():
    n, m = map(int, input().split())
    ab_list = []
    for _ in range(m):
        ab_list.append(tuple(map(int, input().split())))
    res = solve(n, m, ab_list)
    print(res)


def test():
    assert solve(3, 1, [(1, 2)]) == 1


if __name__ == "__main__":
    test()
    main()

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

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

    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x!=y:
            if self.rank[x]<self.rank[y]:
                self.parent[x]=y
                self.size[y]+=self.size[x]
            else:
                self.parent[y]=x
                self.size[x]+=self.size[y]
                if self.rank[x]==self.rank[y]:
                    self.rank[x]+=1

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

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

    def group_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.parent) if i==x]

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

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

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

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

    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.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, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]    
    
    def members(self, x):
        root = self.find_root(x)
        return [i for i in range(self.n) if self.find_root(i) == 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 = map(int,input().rstrip().split())
AB=[list(map(int,input().rstrip().split()))for _ in range(m)]
u = UnionFind(n)
for a,b in AB:
    u.unite(a-1,b-1)
print(u.group_count()-1)

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

    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):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.parents[x] > self.parents[y]:
            rx, ry = ry, rx
        self.parents[rx] += self.parents[ry]
        self.parents[ry] = rx

    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

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


if __name__ == '__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.unite(a, b)

    cnt = 0
    for i in range(n):
        if uf.root(i) == i:
            cnt += 1
    print(cnt-1)

Solution (Python):

import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n,m = MAP()

graph = defaultdict(list)

for _ in range(m):
    u,v = MAP()
    graph[u].append(v)
    graph[v].append(u)

comp = 0
vis = [False]*(n+1)
for i in range(1,n+1):
    if(vis[i]==False):
        comp+=1
        stack = [i]
        while(stack):
            node = stack.pop()
            vis[node] = True
            for adj in graph[node]:
                if(vis[adj]==False):
                    stack.append(adj)



print(comp - 1)

Solution (Python):
import collections

def searchRoot(n):
    par = parList[n]
    if n == par:
        if len(q) > 0:
            rootIn(q,n)
        return n
    else:
        q.append(n)
        return(searchRoot(par))

def rootIn(q,root):
    while len(q) > 0:
        parList[q.popleft()] = root

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

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

for i in range(m):
    a,b = list(map(int,input().split()))
    aRoot = searchRoot(a)
    bRoot = searchRoot(b)
    if aRoot != bRoot:
        parList[max(aRoot,bRoot)] = min(aRoot,bRoot)
    

ansDic = dict()
rootSet = set()
for i in range(1,n+1):
    root = searchRoot(i)
    if root in rootSet:
        ansDic[root] += 1
    else:
        rootSet.add(root)
        ansDic[root] = 1
print(len(rootSet) - 1)

Solution (Python):



import sys


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


def main():
    n, m = list(get_ints())

    ab = [(0, 0)] * m
    i_to_x = {}
    for i in range(m):
        a, b = map(int, input().split())
        ab[i] = (a-1, b-1)
        i_to_x[i] = a-1

    uf = UnionFind(n)

    for i in range(m):
        uf.union(ab[i][0], ab[i][1])

    print(uf.group_count() - 1)


class UnionFind:
    """Union-Find
    Note:
        https://note.nkmk.me/python-union-find/
    """
    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())


if __name__ == "__main__":
    main()

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




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


AB = [list(map(int, input().split())) for _ in range(M)]

g = DSU(N)

for a, b in AB:
    g.merge(a-1, b-1)

grp = g.groups()

if grp == None:
    print(0)
else:
    print(len(grp) - 1)

Solution (Python):
def acl_beginner_c():
    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())
    uft = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        uft.union(a-1, b-1)
    print(uft.group_count()-1)
acl_beginner_c()

Solution (Python):

"""
Created on Mon Aug 31 01:34:43 2020

@author: liang
"""

"""
Union-Find クラス
素集合の併合・判定アルゴリズム
グラフの問題を集合と見なして解く時に使用する
"""

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.par = [-1]*(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 union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        
    def same(self,x,y):
        x = self.find(x)
        y = self.find(y)
        return x==y
    
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)
ans = sum([uf.par[i] < 0 for i in range(N)]) - 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())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i],B[i] = map(int,input().split())
uf = UnionFind(N)
for i in range(M):
    uf.union(A[i]-1,B[i]-1)
groups = uf.group_count()
print(groups-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 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]

N,M=map(int,input().split())
uf=UnionFind(N)
for _ in range(M):
  a,b=map(int,input().split())
  a-=1
  b-=1
  uf.unite(a,b)
print(len(set(uf.roots()))-1)

Solution (Python):

import os

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



def input():
    return sys.stdin.readline().rstrip()


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

    uf = UnionFind(n)

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

    for i in range(1, n + 1):
        uf.Find_Root(i)

    count = -1
    
    
    for rt in uf.root:
        if rt < 0:
            count += 1

    if count > 0:
        count -= 1

    print(count)


main()