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

Solution (Python):
import sys
sys.setrecursionlimit(2 * (10 ** 6))

def main():
    N, M = map(int, input().split())
    AB = [[] for _ in range(N)]

    for _ in range(M):
        a,b = map(lambda x: int(x)-1, input().split())
        AB[a].append(b)
        AB[b].append(a)

    def dfs(v):
        visited[v] = 1
        for i in AB[v]:
            if visited[i]:
                continue
            dfs(i)

    visited = [0]*N
    cnt = 0
    for i in range(N):
        if visited[i]:
            continue
        dfs(i)
        cnt += 1
    print(cnt-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())

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, 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)
s=set()
for i in range(n):
    s.add(uf.find(i))
print(len(s)-1)

Solution (Python):
def root(x):
    if r[x] < 0:
        return x
    else:
        r[x] = root(r[x])
        return r[x]
def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if r[x] > r[y]:
            x,y = y,x
        r[x] += r[y]
        r[y] = x
n,m = map(int,input().split())
r = [-1] * n
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a,b)
ans = 0
for i in r:
    if i < 0:
        ans += 1
print(ans-1)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict

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):
        self.all_group_member=defaultdict(list)
        for i in range(self.n):
            self.all_group_member[self.find(i)].append(i)
        return self.all_group_member

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots()) 
 
def main():
    n,m=map(int, input().split())
    uf = UnionFind(n+1)
    for _ in range(m):
        a,b=map(int, input().split())
        uf.union(a, b)  
    print(uf.group_count()-2)
    
        
 
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        

    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 union(self, x, y):
        px = self.find(x)
        py = self.find(y)

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1


N,M = map(int,input().split())
ufpc = UnionFindPathCompression(N)
for i in range(M):
    a,b = map(int,input().split())
    ufpc.union(a-1,b-1)

ans = 0
for i in range(N-1):
    if ufpc.find(i) != ufpc.find(i+1):
        ufpc.union(i,i+1)
        ans += 1
print(ans)

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

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

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

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

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

n,m = readints()
u = UnionFind(n)
for i in range(m):
    a,b = readints()
    u.unite(a-1,b-1)

print(sum([1 for x in u.par if x<0])-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 group_cnt(self):  
        return sum(x < 0 for x in self.parents)

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

uf = Unionfind(n)
for a, b in ab:
    uf.union(a - 1, b - 1)
print(uf.group_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 _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
print(len(uf.roots())-1)

Solution (Python):
def main():
    def find(target):
        if parent[target] < 0:
            return target
        else:
            parent[target] = find(parent[target])
            return parent[target]

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

    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x == root_y:
            return
        if parent[root_x] > parent[root_y]:
            root_x, root_y = root_y, root_x
        parent[root_x] += parent[root_y]
        parent[root_y] = root_x

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

    def get_size(x):
        return -parent[find(x)]

    def get_root():
        return [i for i, root in enumerate(parent) if root < 0]
    
    n, m = map(int, input().split())
    parent = [-1 for _ in range(n)]
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        union(a, b)
    ans = len(get_root()) - 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

class UnionFind:
    def __init__(self, n):
        self.prsz = [-1] * n 
    def find(self, v): 
        if self.prsz[v] < 0: return v
        self.prsz[v] = self.find(self.prsz[v])
        return self.prsz[v]
    def union(self, v, u): 
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.prsz[v] > self.prsz[u]: v, u = u, v 
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    uf.union(a, b)
ans = -1
for a in uf.prsz:
    if a < 0: ans += 1
print(ans)

Solution (Python):

class UnionFind:
    def __init__(self, n):
        self.prsz = [-1] * n 
    def find(self, v): 
        if self.prsz[v] < 0: return v
        self.prsz[v] = self.find(self.prsz[v])
        return self.prsz[v]
    def union(self, v, u): 
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.prsz[v] > self.prsz[u]: v, u = u, v 
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    uf.union(a, b)
ans = set()
for i in range(n):
    ans.add(uf.find(i))
print(len(ans) - 1)

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

    def find(self, x) -> int:
        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) -> None:
        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) -> int:
        return -self.parents[self.find(x)]

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

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

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

    def group_count(self) -> int:
        return len(self.roots())

    def all_group_members(self) -> dict:
        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=UnionFind(n)
for i in range(m):
    b,c=map(int,input().split())
    a.union(b-1,c-1)
print(a.group_count()-1)

Solution (Python):

class UnionFind:
    def __init__(self, n):
        self.prsz = [-1] * n 
    def find(self, v): 
        if self.prsz[v] < 0: return v
        self.prsz[v] = self.find(self.prsz[v])
        return self.prsz[v]
    def union(self, v, u): 
        v = self.find(v); u = self.find(u)
        if v == u: return False
        if self.prsz[v] > self.prsz[u]: v, u = u, v 
        self.prsz[v] += self.prsz[u]
        self.prsz[u] = v
        return True

n, m = map(int, input().split())
uf = UnionFind(n)
ans = n - 1
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    if uf.find(a) !=uf.find(b):
        uf.union(a, b)
        ans -= 1
print(ans)

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

    def find(self, x) -> int:
        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) -> None:
        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) -> int:
        return -self.parents[self.find(x)]

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

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

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

    def group_count(self) -> int:
        return len(self.roots())

    def all_group_members(self) -> dict:
        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: int
    M: int
    A: int
    B: int
    N, M = map(int, input().split())
    uni = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        uni.union(A,B)
    
    print(uni.group_count() - 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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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,y=self.find(x),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 all_group_members_list(self):
        
        
        return list(self.all_group_members().values())
    def __str__(self):
        
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())

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



if __name__=='__main__':
    main()

Solution (Python):

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

def g(u,parent):
    if parent[u]!= u:
        parent[u] = g(parent[u], parent)
    return parent[u]
parent = range(n+1)
for _ in range(m):
    u,v = map(int, raw_input().split())
    pu,pv = g(u,parent), g(v,parent)
    if pu!= pv:
        parent[pu] = pv

ans = 0
for u in range(1, n+1):
    if g(u,parent) == u:
        ans+=1
print ans -1

Solution (Python):

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

def g(u,parent):
    if parent[u]!= u:
        parent[u] = g(parent[u], parent)
    return parent[u]
parent = {u:u for u in range(1, n+1)}
for _ in range(m):
    u,v = map(int, raw_input().split())
    pu,pv = g(u,parent), g(v,parent)
    if pu!= pv:
        parent[pu] = pv

ans = 0
for u in parent:
    if g(u,parent) == u:
        ans+=1
print ans -1

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

from collections import defaultdict

n,m=map(int,input().split())
visited=[0]*n
d=defaultdict(list)
def dfs(n):
    visited[n]=1
    
    for i in d[n]:
        if visited[i]==0:
            dfs(i)

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

r=-1
for i in range (n):
    if visited[i]==0:
        dfs(i)
        r+=1
print(r)

Solution (Python):
def main():
    n, m = map(int, input().split())
    
    uf = [-1] * (n+1)

    def uf_leader(a):
        if uf[a]<0:
            return a
        uf[a] = uf_leader(uf[a])
        return uf[a]
    def uf_unite(a, b):
        ua, ub = uf_leader(a), uf_leader(b)
        if ua==ub:
            return False
        if uf[ua] > uf[ub]:
            ua, ub = ub, ua
        uf[ua] += uf[ub]
        uf[ub] = ua
        return True
    def uf_leaders():
        return [v for v in range(1,n+1) if uf[v]<0]

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

    
    
    ans = len(uf_leaders())-1
    print(ans)

main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    
    uf = [-1] * (n+1)

    def uf_leader(a):
        if uf[a]<0:
            return a
        uf[a] = uf_leader(uf[a])
        return uf[a]
    def uf_unite(a, b):
        ua, ub = uf_leader(a), uf_leader(b)
        if ua==ub:
            return False
        if uf[ua] > uf[ub]:
            ua, ub = ub, ua
        uf[ua] += uf[ub]
        uf[ub] = ua
        return True
    def uf_leaders():
        return set([uf_leader(v) for v in range(1,n+1)])

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

    
    
    ans = len(uf_leaders())-1
    print(ans)

main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    
    uf = [-1] * (n+1)

    def uf_leader(a):
        if uf[a]<0:
            return a
        uf[a] = uf_leader(uf[a])
        return uf[a]
    def uf_unite(a, b):
        ua, ub = uf_leader(a), uf_leader(b)
        if ua==ub:
            return False
        if uf[ua] > uf[ub]:
            a, b = b, a
        uf[ua] += uf[ub]
        uf[ub] = ua
        return True
    def uf_leaders():
        return set([uf_leader(v) for v in range(1,n+1)])

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

    
    
    ans = len(uf_leaders())-1
    print(ans)

main()

Solution (Python):

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

N,M = map(int,readline().split())
road = [[] for _ in range(N+1)]
visit = [0]*(N+1)

for i in range(M):
    x,y = map(int,readline().split())
    road[x].append(y)
    road[y].append(x)
  
def dfs(v,prev):
    for x in road[v]:
        if x == prev:
            continue
        if visit[x] != 0:
            continue
        visit[x] = 1
        dfs(x,v)
    return 

count = 0     
for i in range(1,N+1):
    if visit[i] == 0:
        dfs(i,-1)
        count += 1

print(count-1)

Solution (Python):
def main():
    n, m = map(int, input().split())
    uf = [-1] * (n+1)

    def uf_find(a):
        if uf[a]<0:
            uf[a] = a
            return a
        elif uf[a]==a:
            return a
        uf[a] = uf_find(uf[a])
        return uf[a]
    def uf_union(a, b):
        if uf_find(a)==uf_find(b):
            return
        ua, ub = uf_find(a), uf_find(b)
        if ua>ub:
            ua, ub = ub, ua
        uf[ub] = ua
    def uf_leaders():
        return set([uf_find(v) for v in range(1,n+1)])

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

    
    
    
    ans = len(uf_leaders())-1
    print(ans)

main()

Solution (Python):



import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading



sys.setrecursionlimit(300000)
threading.stack_size(10**8)


BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
    
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
     
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
  
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]
 
    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]
 
    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]
 
    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]
 
 
class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)
 
    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD


def main():
    n,m=map(int,input().split())
    visited=[0]*n
    d=defaultdict(list)
    def dfs(n):
        visited[n]=1
        
        for i in d[n]:
            if visited[i]==0:
                dfs(i)
    
    for i in range (m):
        a,b=map(int,input().split())
        a,b=a-1,b-1
        d[a].append(b)
        d[b].append(a)
    
    r=-1
    for i in range (n):
        if visited[i]==0:
            dfs(i)
            r+=1
    print(r)
    
t = threading.Thread(target=main)
t.start()
t.join()

Solution (Python):
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
 a,b=sorted(map(r:=lambda x:x*(p[x]<0)or r(p[x]),a),key=p.__getitem__)
 if a-b:p[a]+=p[b];p[b]=a
print(sum(i<0for i in p)-2)

Solution (Python):
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
 a,b=map(r:=lambda x:x*(p[x]<0)or r(p[x]),a)
 if a-b:
  if p[a]>p[b]:a,b=b,a
  p[a]+=p[b];p[b]=a
print(sum(i<0for i in p)-2)

Solution (Python):
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
 a,b=map(r:=lambda x:x*(p[x]<0)or r(p[x]),a)
 if a!=b:
  if p[a]>p[b]:a,b=b,a
  p[a]+=p[b];p[b]=a
print(sum(i<0for i in p)-2)

Solution (Python):
r=lambda x:x*(p[x]<0)or r(p[x])
(n,m),*a=[map(int,t.split())for t in open(0)]
p=[-1]*-~n
for a in a:
    a,b=map(r,a)
    if a==b:continue
    if p[a]>p[b]:a,b=b,a
    p[a]+=p[b]
    p[b]=a
print(sum(i<0for i in p)-2)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

checked = [False]*n
q = deque([])
cnt = 0



for i in range(n):
    if checked[i]:
        continue
    checked[i] = True
    q.append(i)
    while q:
        v = q.pop()
        s = g[v]
        for j in s:
            if checked[j]:
                continue
            checked[j] = True
            q.append(j)
    cnt += 1

print(cnt - 1)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

dist = [-1]*n
q = deque([])
cnt = 0



for i in range(n):
    if dist[i] != -1:
        continue
    dist[i] = 0
    q.append(i)
    while q:
        v = q.pop()
        s = g[v]
        for j in s:
            if dist[j] != -1:
                continue
            dist[j] = 0
            q.append(j)
    cnt += 1

print(cnt - 1)

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

def root(x):
    if parent[x] == x: return x
    rt = root(parent[x])
    parent[x] = rt
    return rt

def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y: return
    parent[y] = x

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

for i in range(n):
    root(i)

cnt = len(set(parent)) - 1
print(cnt)