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):
from collections import defaultdict

def bfs(s):
  q = [s]
  while q != []:
    p = q[0]
    del q[0]
    for node in adj[p]:
      if not visited[node]:
        visited[node] = True
        q.append(node)

n,m = map(int,input().split())
adj = defaultdict(list)
visited = [False]*(n+1)
comp = 0
for _ in range(m):
  a,b = map(int,input().split())
  adj[a].append(b)
  adj[b].append(a)
for i in range(1,n+1):
  if not visited[i]:
    comp+=1
    bfs(i)
print(comp-1)

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

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

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

        if x == y:
            return

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

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

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

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

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

for 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,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
from decimal import *


BUFSIZE = 8192

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




def main():
    n,m=map(int,input().split())
    s=set()
    fa=[i for i in range(n+1)]
    child_sum=[1]*(n+1)
    
    def find(x):
        if x!=fa[x]:
            fa[x]=find(fa[x])
        return fa[x]
    def union(x,y):
        x = find(x)
        y = find(y)
        if x == y:  
            return
        fa[x] = y
        
        child_sum[y]+=child_sum[x]
    pairs=[]
    for i in range(m):
        a=list(map(int,input().split()))
        pairs.append((a[0],a[1]))
    
    for (i,j) in pairs:
        union(i,j)
    for (i,j) in pairs:
        union(j,i)
    
    for i in range(1,n+1):
        s.add(fa[i])
    print (len(s)-1)
if __name__ == "__main__":
    main()

Solution (Python):



import collections
import sys
import copy
import re
import math


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():
    N,M = LI()
    loadArray = [LI() for _ in range(M)]

    ans = 0

    class UnionFind():
        
        
        def __init__(self, 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

    uf = UnionFind(N)
    for a, b in loadArray:
        
        a -= 1; b -= 1
        uf.union(a, b)

    for u in uf.parents:
        if u<0:
            ans += 1

    

    print(ans-1)


if __name__ == '__main__':
    main()

Solution (Python):

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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





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)
x=uf.group_count()
print(x-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())


def main():
    N, M = list(map(int, input().split()))
    paths = [list(map(int, input().split())) for _ in range(M)]
    result = solve(N, paths)
    print(result)


def solve(N, paths) -> int:
    uf = UnionFind(N)
    for x, y in paths:
        uf.union(x - 1, y - 1)
    return uf.group_count() - 1


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



n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ds = dsu.DSU(n)
for i in ab:
    ds.merge(i[0]-1,i[1]-1)
    
s = ds.groups()

print(len(s)-1)

Solution (Python):
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
from sys import stdin


def makeConnected(n, connections):
    l = list(zip(*connections))
    d = [1] * len(connections)
    a = csr_matrix((d, (l[0], l[1])), (n, n))
    return connected_components(a, return_labels=0)


def main():
    input = lambda: stdin.readline()[:-1]
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]

    ab = [[a - 1, b - 1] for a, b in AB]
    ans = makeConnected(N, ab) - 1
    print(ans)


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())
AB = [list(map(int,input().split())) for m in range(M)]
UF = UnionFind(N)

for A,B in AB:
  UF.union(A-1,B-1)

print(UF.group_count()-1)

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

Solution (Python):
N, M = map(int, input().split())
Pajew = [i for i in range(N)]
import sys
sys.setrecursionlimit(1000000)

def find(x, Pajew):
    if Pajew[x] == x:
        return x
    else:
        a = find(Pajew[x], Pajew)
        Pajew[x] =a
        return a

def unite(x, y):
    x = find(x, Pajew)
    y = find(y, Pajew)
    if x != y:
        Pajew[x] = y

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

grou = 0
for i in range(N):
    if i == Pajew[i]:
        grou +=1


print(grou-1)

Solution (Python):
class disjoint_set:
    def __init__(self,num):

        self.array=[0]+[[i,0] for i in range(1,num+1)]  
    
    def union(self,a,b):
        
        ''' a and b are the vertices that we want to connect them to each other '''
        
        a=self.find(a) 
        b=self.find(b) 
    
        if a==b:
            
            return False
    

        

        if self.array[a][1] > self.array[b][1] :
            self.array[b][0]=a
        
        elif self.array[a][1] < self.array[b][1] :
            self.array[a][0]=b

        else:
            self.array[a][0]=b
            self.array[b][1]+=1
        return True
            
    def find(self,a):
        p=[]
        while self.array[a][0]!=a :
            p.append(a)
            a=self.array[a][0]
        for i in p:
            self.array[i][0]=a
        return a


n,m=map(int,input().split())
dset=disjoint_set(n)
for _ in range(m):
    a,b=map(int,input().split())
    dset.union(a,b)

ans=set()
for i in range(1,n+1) :
    ans.add(dset.find(i))

print(len(ans)-1)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
ls = [[] for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  ls[A-1].append(B-1)
  ls[B-1].append(A-1)
visited = [False]*N
tmp = 0
counter = 0
isl = 0
while True:
  isl += 1
  found = deque()
  for city in ls[tmp]:
    found.append(city)
  visited[tmp] = True
  while len(found) != 0:
    tmp = found.pop()
    if not visited[tmp]:
      for city_ in ls[tmp]:
        found.append(city_)
      visited[tmp] = True
  while visited[counter]:
    counter += 1
    if counter > N-1:
      break
  tmp = counter
  if tmp > N-1:
    break
print(isl-1)

Solution (Python):
import numpy as np
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: int) -> None:
        self.forest = [-1] * n

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x,y = y,x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

    def findRoot(self, x: int) -> int:
        if self.forest[x] < 0:
            return x
        else:
            self.forest[x] = self.findRoot(self.forest[x])
            return self.forest[x]

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)

    def size(self,x: int) -> int:
        return -self.forest[self.findRoot(x)]


n,m = map(int,input().split())
uf = UnionFind(n)
s = set()
for i in range(m):
    ai,bi = map(int,input().split())
    uf.union(ai-1,bi-1)

for i in range(n):
    s.add(uf.findRoot(i))
print(len(s)-1)

Solution (Python):
from collections import deque
N, M = map(int, input().split())
A = [[] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  A[a-1].append(b - 1)
  A[b-1].append(a - 1)
B = [0 for i in range(N)]
cnt = 0
for i in range(N):
  if B[i] == 0:
    cnt += 1
    B[i] = cnt
    D = deque([i])
    while len(D) > 0:
      d = D.pop()
      for j in A[d]:
        if B[j] == 0:
          B[j] = cnt
          D.append(j)
print(cnt - 1)

Solution (Python):
class uf():


    def __init__(self,n):
        self.size=n
        self.parents=list(range(n))


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


    def union(self,a,b):
        x=self.find(a)
        y=self.find(b)
        if x==y:
            return
        if x>y:
            x,y=y,x
        self.parents[y]=x


    def roots(self):
        s=0
        for c in range(self.size):
            if self.find(c)==c:
                s+=1
        return s-1


n,m=map(int,input().split())
city=uf(n)
for c in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    city.union(a,b)
print(city.roots())

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

for i in range(n):
    if group[i] is not None: continue
    newly_visited = [i]
    group[i] = i
    while len(newly_visited) > 0:
        new = newly_visited.pop()
        for j in connected[new]:
            if group[j] is not None: continue
            group[j] = i
            newly_visited.append(j)

print(len(Counter(group)) - 1)

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


ans = 0
for i, k in enumerate(pair[1:], 1):
    if i == k:
        ans += 1
    
print(ans - 1)

Solution (Python):
import sys
r=sys.stdin.readline
N,M=map(int,r().split())
city=[[] for _ in range(N+1)]
for _ in range(M):
    a,b=map(int,r().split())
    city[a].append(b)
    city[b].append(a)
check=[True]+[False]*(N)
def dfs(v):
    stack=[v]
    while stack:
        cur=stack.pop()
        check[cur]=True
        for v in city[cur]:
            if not check[v]:
                stack.append(v)
cnt=0
for i in range(1,N+1):
    if not check[i]:
        dfs(i)
        cnt+=1
print(cnt-1)

Solution (Python):



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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N , M = map(int, input().split())
uf = UnionFind(N)
while True:
    try:
        listA = list(map(int,input().split()))
        uf.union(listA[0] - 1,listA[1] - 1)
    except:
        break

print(uf.group_count() - 1)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
data = [1 for i in range(m)]
a = []
b = []

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

csr = csr_matrix((data, (a, b)), (n, n))

print(connected_components(csr, return_labels=False) - 1)

Solution (Python):
import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n, m = map(int, read().split())
    al = [[] for _ in range(n)]
    for _ in range(m):
        a, b = [int(i) - 1 for i in read().split()]
        al[a].append(b)
        al[b].append(a)
    cnt = 0
    seen = set()
    for i in range(n):
        if i in seen:
            continue
        todo = [i]
        while todo:
            p = todo.pop()
            if p in seen:
                continue
            seen.add(p)
            todo += al[p]
        cnt += 1
    print(cnt - 1)


if __name__ == '__main__':
    main()

Solution (Python):
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7

import sys
import math
import collections
par = []
def init(n):
    for i in range(n):
        par.append(i)

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

def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False

def unite(x,y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    par[y] = x
n,m = L()
ab = NL(m)
init(n)


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

for i in range(len(par)):
    root(i)

count = collections.Counter(par)
print(len(count)-1)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
ad_list = [[] for i in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    ad_list[i - 1].append(j - 1)
    ad_list[j - 1].append(i - 1)


def bfs(node, ad_list):
    visited = [-1] * node
    queue = deque()
    count = 0
    for i in range(node):
        if visited[i] == 0: continue
        queue.append(i)
        visited[i] = 0
        while queue:
            n = queue.popleft()
            for ad in ad_list[n]:
                if visited[ad] == -1:
                    visited[ad] = 0
                    queue.append(ad)
        count += 1
    return count

ans = bfs(n, ad_list) - 1
print(ans)

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,m = lr()
uf = UnionFind(n)
for i in range(m):
    a,b = lr()
    a-=1
    b-=1
    uf.union(a,b)
k = len(uf.roots())
print(k-1)

Solution (Python):
import collections
import sys


def count_connected_components(max_v, adj_list):
    result = 0
    visited = collections.defaultdict(bool)

    def depth_first_search(start_v):
        visited[start_v] = True
        for v in adj_list[start_v]:
            if not visited[v]:
                depth_first_search(v)
    for u in range(max_v):
        if not visited[u]:
            depth_first_search(u)
            result += 1
    return result


def main():
    sys.setrecursionlimit(50000)
    n, m = map(int, input().split())
    adj_list = collections.defaultdict(set)
    for _ in range(m):
        a, b = map(lambda x: int(x) - 1, input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    print(count_connected_components(n, adj_list) - 1)


if __name__ == '__main__':
    main()

Solution (Python):
class union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[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.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


N,M = map(int,input().split())
g = union_find(N)
group = 0
for i in range(M):
  A,B= map(int,input().split())
  g.unite(A,B)

for j in g.root:
  if j < 0:
    group += 1

print(group - 2)

Solution (Python):
N, M = list(map(int, input().split()))

class UnionFind():
	def __init__(self, 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())

uf = UnionFind(N)
for _ in range(M):
	a, b = [int(t) - 1 for t in input().split()]
	uf.union(a, b)

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