Problem:
 Score : 300 points    Problem Statement There are N cities numbered 1 through N , and M bidirectional roads numbered 1 through M .
Road i connects City A_i and City B_i .  Snuke can perform the following operation zero or more times:   Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.   After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).  What is the minimum number of roads he must build to achieve the goal?      Constraints  2 \leq N \leq 100,000  1 \leq M \leq 100,000  1 \leq A_i < B_i \leq N  No two roads connect the same pair of cities.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  A_1  B_1  :  A_M  B_M       Output Print the answer.        Sample Input 1 3 1
1 2      Sample Output 1 1  Initially, there are three cities, and there is a road between City 1 and City 2 .  Snuke can achieve the goal by building one new road, for example, between City 1 and City 3 .
After that,   We can travel between 1 and 2 directly.  We can travel between 1 and 3 directly.  We can travel between 2 and 3 by following both roads ( 2 - 1 - 3 ).

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]

n,m = list(map(int, input().split()))
uf = UnionFindTree(n)
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    uf.connect(a,b)
s = set()
for i in range(n):
    s.add(uf.root(i))
print(len(s)-1)

Solution (Python):
N,M = map(int,input().split( ))
loads = []
teams = [[i] for i in range(N)]
syozoku = {i:i for i in range(N)}
for _ in range(M):
    A,B = map(int,input().split( ))
    if syozoku[A-1] != syozoku[B-1]:
        hairu,nukeru = min(syozoku[A-1],syozoku[B-1]),max(syozoku[A-1],syozoku[B-1])
        team = teams[nukeru]
        teams[nukeru] = []
        teams[hairu] += team
        for i in team:
            syozoku[i] = hairu

ans = -1
for team in teams:
    if len(team) != 0:
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
xy = [map(int, input().split()) for _ in range(m)]
x, y = [list(i) for i in zip(*xy)]
ans=0

l=[-1]*n

def rootfind(a):
    changelist=[]
    while 1:
        if l[a-1]>0:
            changelist.append(a)
            a=l[a-1]
        else:
            break
    for e in changelist:
        l[e-1]=a
    return a


def rootunion(c,d):
    cr=rootfind(c)
    dr=rootfind(d)
    if cr==dr:
        pass
    else:
        l[cr-1]=dr


for j in range(m):
    p=x[j]
    q=y[j]
    rootunion(p,q)

for o in l:
    if o<0:
        ans+=1

print(ans-1)

Solution (Python):
n,m=map(int,input().split())
data=list(range(n))
cnt=n-1
def find(x):
    if data[x]==x:
        return x
    else:
        data[x]=find(data[x])
        return data[x]
for i in range(m):
    a,b=map(int,input().split())
    a=find(a-1)
    b=find(b-1)
    if a!=b:
        data[a]=b
        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
 
 
 
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)
print(len(u.roots())-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 roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]

N,M = map(int, input().split())
towns = UnionFind(N)
for i in range(M):
    a,b= map(lambda x: int(x)-1, input().split())
    towns.union(a,b)

print(len(towns.roots())-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]
 
    def group_count(self):
        return len(self.roots())
 
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
 
 
 
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)

print(u.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())
ans=0
U = UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  U.union(a,b)
print(U.group_count()-1)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.r = [-1 for i in range(n)]
    
    def root(self, x):
        if self.r[x] < 0:
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] < self.r[y]:
            temp = x
            x = y
            y = temp
        self.r[x] += self.r[y]
        self.r[y] = x
        return True
    
    def size(self, x):
        return -self.r[self.root(x)]

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

ans = 0
for i in UF.r:
    if i < 0:
        ans += 1

print(ans-1)

Solution (Python):


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



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

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



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



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


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


par = [-1] * n

for _ in range(m):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
print(len(list(filter(lambda x: x < 0, par))) - 1)

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


n, m = map(int, input().split())
g = DSU(n)
ab = [tuple(map(int, input().split())) for _ in range(m)]
for a, b in ab:
    g.merge(a - 1, b - 1)
print(len(g.groups()) - 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)

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,io,os
z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
y=lambda:map(int,z().split())
n,m=y()
k={}
p={}
r=0
e=0
def path(r):
    while p[r]>=0:r=p[r]
    return r
for i in range(m):
    a,b=y();a-=1;b-=1;e+=1
    if a in k:
        if b in k:
            va,vb=path(k[a]),path(k[b])
            if va>vb:p[va]=vb
            elif va<vb:p[vb]=va
            else:e-=1
        else:k[b]=k[a]
    else:
        if b in k:k[a]=k[b]
        else:
            k[a]=r
            k[b]=r
            p[r]=-1
            r+=1
print(n-1-e)

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=[int(_) for _ in input().split()]
uf =UnionFind(n)

for i in range(m):
    a,b=[int(_) for _ in 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.parent = list(range(n))
        self.rank = [1] * n
        self.grp = n
    
    def root(self,x):
        if self.parent[x] == x :
            return x
        else :
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    
    def same(self,x,y):
        return self.root(x) == self.root(y)
    
    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
 
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else :
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        self.grp -= 1
        

def input_1():
    n, m = map(int,input().split())
    brg = [tuple(map(int,input().split())) for i in range(m)]
    return n,m,brg

def input_2(n):
    brg = [( 2*i-1 , 2*i ) for i in range(1,int(n/2))]
    return n,int(n/2)-1,brg

def main():
    n,m,brg = input_1()
    
    uf = UnionFind(n)
    for i in range(m):
        uf.unite(brg[i][0]-1,brg[i][1]-1)
    
    print(uf.grp-1)


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
g = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

from collections import deque

d = [None] * n
def bfs(u):
    queue = deque([u])
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
cnt=0
for i in range(n):
    if d[i] is None:
        cnt+=1
        bfs(i)
print(cnt-1)

Solution (Python):
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().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())
 
 
N, K = MI()
uf = UnionFind(N)
        
for i in range(K):
    A, B = MI()
    uf.union(A-1, B-1)
 
print(uf.group_count()-1)

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

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





def root(i):
    if par[i]==i:
        return i
    else:
        a=root(par[i])
        par[i]=a
        return a

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

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

ans=set()

for i in range(n):
    rt=root(i)
    ans.add(rt)






print(len(ans)-1)

Solution (Python):
n,m = map(int,input().split())
par = [i for i in range(n+1)]
root = [i for i in range(n+1)]
par[0] = 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
    
for i in range(m):
    a,b = map(int,input().split())
    unite(a,b)
for i in range(n+1):
  root[i] = find(i)
print(len(set(root))-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):
class UnionFind:
    def __init__(self, num):
        self.parent = [-1] * num

    def find(self, node):
        if self.parent[node] < 0:
            return node
        self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, node1, node2):
        node1 = self.find(node1)
        node2 = self.find(node2)
        if node1 == node2:
            return
        if self.parent[node1] > self.parent[node2]:
            node1, node2 = node2, node1
        self.parent[node1] += self.parent[node2]
        self.parent[node2] = node1
        return

    def same(self, node1, node2):
        return self.find(node1) == self.find(node2)

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

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

    def group_count(self):
        return len(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):
import sys
sys.setrecursionlimit(10**9)

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

def unite(x,y):
    x, y = find(x), find(y)
    if x == y:
        return False
    
    if par[x] > par[y]:
        x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

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

n, m = map(int, input().split())
ab = []
for _ in range(m):
    a, b = map(int, input().split())
    ab.append([a-1, b-1])

par = [-1]*n

for a, b in ab:
    unite(a, b)

nset=set()
for i in range(n):
    if not find(i) in nset:
        nset.add(find(i))
else:
    print(len(nset)-1)

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.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())
uni = UnionFind(n)
for i in range(m):
    a, b = ab[i]
    uni.union(a - 1, b - 1)
print(uni.group_count() - 1)

Solution (Python):


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 roots(self):
        return [i for i, x in enumerate(self.root) if x < 0]

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


def main():
    n, m = map(int, input().split())
    UF = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        UF.Unite(a, b)

    print(UF.group_count() - 2)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

from collections import Counter

class UnionFind:
    def __init__(self, N):
        self.root = [n for n in range(N)]

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

    def unite(self, x, y):
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        if root_x != root_y:
            self.root[root_x] = root_y


    def final(self):
        for i in range(N):
            root_r = self.get_root(self.root[i])
            if root_r != self.root[i]:
                self.root[self.root[i]] = root_r

def main(N, M, AB):
    uf = UnionFind(N)
    {uf.unite(*ab) for ab in AB}
    c = Counter(map(uf.get_root, uf.root))
    print(len(c) - 1)

if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    AB = {tuple(map(lambda x:int(x)-1, input().split())) for m in range(M)}
    main(N, M, AB)

Solution (Python):
import queue
n, m = map(int, input().split())
a = [[] for _ in range(n)]
ans = 0
 
for _ in range(m):
    x, y = map(int, input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)
 
route = set()
route.add(0)
q = queue.Queue()
q.put(0)
 
for i in range(n):
    if not i in route:
        route.add(i)
        q.put(i)
        ans += 1
    while not q.empty():
        c = q.get()
        for k in a[c]:
            if not k in route:
                q.put(k)
                route.add(k)
    if len(route) == n:
        print(ans)
        break

Solution (Python):

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n + 1)]

    def find(self, x):
        if self.parents[x] == x:
            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 0
        elif x < y:
            self.parents[y] = x
        else:
            self.parents[x] = y
        return 1

from collections import Counter
n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)
    
roots = []
for num in uf.parents:
    roots.append(uf.find(num))
roots.pop(0)

mn = Counter(roots)
print(len(mn)-1)

Solution (Python):
import sys
from collections import deque

n,m = map(int, sys.stdin.readline().rstrip("\n").split())
bridges = [[] for _ in range(n)]
done = [False]*n
for _ in range(m):
    a,b = map(int, sys.stdin.readline().rstrip("\n").split())
    bridges[a-1].append(b-1)
    bridges[b-1].append(a-1)
d = deque()
ans = -1
for i in range(n):
    if not done[i]:
        done[i] = True
        d.append(i)
        while d:
            cp = d.pop()
            for np in bridges[cp]:
                if not done[np]:
                    done[np] = True
                    d.append(np)
        ans += 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 i 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())


N, m = map(int, input().split())
uf = UnionFind(N)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)
print(uf.group_count() - 1)

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

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

A = []
B = []

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)

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

def find(x):
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]

def unite(x, y):
    x = find(x)
    y = find(y)
    root[y] = x

for i in range(M):
    unite(A[i], B[i])

for x in range(N):
    find(x)

roots = set(root)

print(len(roots) - 1)

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
for i in range(m):
    a,b=map(int,input().split())
    unite(a,b)
ans=[find(i) for i in range(1,n+1)]
ans=set(ans)
print(len(ans)-1)