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

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

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

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        print(self.root)
        return -self.root[self.Find_Root(x)]
    
    def Output(self):
        return [i for i in self.root if i < 0]

uf = UnionFind(n)
for i in range(m):
    ab = list(map(int, input().split()))
    uf.Unite(ab[0],ab[1])


print(len(uf.Output())-2)

Solution (Python):
from collections import defaultdict
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 queue

N, M = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    e[A].append(B)
    e[B].append(A)


seen = [-1] * N
k = -1
for i in range(N):
    if seen[i] == -1:
        k += 1
        seen[i] = k
        que = queue.Queue()
        que.put(i)
        while not que.empty():
            v = que.get()
            for nv in e[v]:
                if seen[nv] != -1: continue
                seen[nv] = k
                que.put(nv)

print(k)

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())
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)

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 i in range(m):
    uf.union(a[i]-1,b[i]-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())
t = [-1] * N
import sys
sys.setrecursionlimit(10 ** 9)

root = [-1] * N

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


def union(x, y):
    x_parent = parent(x)
    y_parent = parent(y)
    if x_parent == y_parent:
        return
    root[x_parent] += root[y_parent]
    root[y_parent] = x



for i in range(M):
    a,b = map(int, input().split())
    union(a-1,b-1)
ans = -1
for i in root:
    if i < 0:
        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 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())
a = [list(map(int, input().split())) for i in range(m)]
uf = UnionFind(n)
for i in range(m):
    uf.union(a[i][0]-1, a[i][1]-1)
print(uf.group_count()-1)

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))
count_roots = Counter(roots)
 
 
print(len(count_roots)-2)

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

uf_t = numba.types.UniTuple(i8[:], 2)


@njit((uf_t, i8), cache=True)
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit((uf_t, i8, i8), cache=True)
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8, i8, i8[:]), cache=True)
def main(N, M, AB):
    ans = N - 1
    root = np.arange(N + 1, dtype=np.int64)
    size = np.ones_like(root)
    uf = (root, size)

    for i in range(0, len(AB), 2):
        a, b = AB[i:i + 2]
        if merge(uf, a, b):
            ans -= 1
    return ans

N, M = map(int, readline().split())
AB = np.array(read().split(), np.int64)

print(main(N, M, AB))

Solution (Python):
import networkx as nx
n, m = map(int, input().split())
nodes = [0 for i in range(n)]
L = []
for i in range(m):
    a, b = map(int, input().split())
    L.append((a,b))
    nodes[a-1] += 1
    nodes[b-1] += 1

num = 0

for node in nodes:
    if node == 0:
        num += 1

graph = nx.from_edgelist(L)
num += len(list(nx.connected_components(graph)))

print(num-1)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
n,m = map(int, input().split())
ab = []
c = [set() for i in range(n)]

for i in range(m):
  a = list(map(int, input().split()))
  a.sort()
  x,y = a[0]-1,a[1]-1
  c[x].add(y)
  c[y].add(x)

def dfs(s):
  if vis[s] == False:
    ary.append(s)
    vis[s] = True
    for j in c[s]:
      dfs(j)

vis = [False for i in range(n)]

ans= []

for i in range(n):
  ary = []
  dfs(i)
  if len(ary) == 0:
    continue
  ans.append(len(ary))

print (len(ans)-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)
l = []

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(M)]
    for j in range(M):
        A[j][0] -= 1
        A[j][1] -= 1
    uf = AlgUnionFind(N)
    for i in range(M):
        uf.union(A[i][0], A[i][1])
    count = uf.group_count() - 1
    print(count)

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

def dfs(f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        dfs(t)
          
          
n, m = map(int, input().split())
E = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]
V = [[] for _ in range(n)]
for a, b in E: V[a].append(b); V[b].append(a)
ans = 0
vis = [0]*n

for a in range(n):
    if vis[a]==1:
      continue
    ans+=1
    dfs(a)
print(ans-1)

Solution (Python):
class UnionFind:
    def __init__(self):
        '''\
Create an empty union find data structure.'''
        self.num_weights = {}
        self.parent_pointers = {}
        self.num_to_objects = {}
        self.objects_to_num = {}
        self.__repr__ = self.__str__
    def insert_objects(self, objects):
        '''\
Insert a sequence of objects into the structure.  All must be Python hashable.'''
        for object in objects:
            self.find(object);
    def find(self, object):
        '''\
Find the root of the set that an object is in.
If the object was not known, will make it known, and it becomes its own set.
Object must be Python hashable.'''
        if not object in self.objects_to_num:
            obj_num = len(self.objects_to_num)
            self.num_weights[obj_num] = 1
            self.objects_to_num[object] = obj_num
            self.num_to_objects[obj_num] = object
            self.parent_pointers[obj_num] = obj_num
            return object
        stk = [self.objects_to_num[object]]
        par = self.parent_pointers[stk[-1]]
        while par != stk[-1]:
            stk.append(par)
            par = self.parent_pointers[par]
        for i in stk:
            self.parent_pointers[i] = par
        return self.num_to_objects[par]
    def union(self, object1, object2):
        '''\
Combine the sets that contain the two objects given.
Both objects must be Python hashable.
If either or both objects are unknown, will make them known, and combine them.'''
        o1p = self.find(object1)
        o2p = self.find(object2)
        if o1p != o2p:
            on1 = self.objects_to_num[o1p]
            on2 = self.objects_to_num[o2p]
            w1 = self.num_weights[on1]
            w2 = self.num_weights[on2]
            if w1 < w2:
                o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1
            self.num_weights[on1] = w1+w2
            del self.num_weights[on2]
            self.parent_pointers[on2] = on1
    def __str__(self):
        '''\
Included for testing purposes only.
All information needed from the union find data structure can be attained
using find.'''
        sets = {}
        for i in range(len(self.objects_to_num)):
            sets[i] = []
        for i in self.objects_to_num:
            sets[self.objects_to_num[self.find(i)]].append(i)
        out = []
        for i in sets.values():
            if i:
                out.append(repr(i))
        return ', '.join(out)

 
uf = UnionFind()
n, m = map(int, input().split())
uf.insert_objects(range(1, n+1))
for _ in range(m):
  i, j = map(int, input().split())
  uf.union(i, j)
components = len({uf.find(i) for i in range(1,n+1)})
print(components - 1)

Solution (Python):
n, m = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [1]*n
        self.size = [1]*n
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x); y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    def group_size(self, x):
        return self.size[self.find(x)]
uf = UnionFind(n); x = []
for _ in range(m):
    a, b = map(int, input().split()); a -= 1; b -= 1
    uf.unite(a, b)
for i in range(n): x.append(uf.find(i))
print(len(set(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())

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

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

Solution (Python):

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 = [int(i) for i in input().split()]
    uf = UnionFind(N)
    for i in range(M):
        A,B = [int(i) for i in input().split()]
        uf.union(A-1,B-1)
    print(uf.group_count()-1)

if __name__ == "__main__":
    main()

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

Solution (Python):


from collections import deque

N, M = (int(i) for i in input().split())

graph = [deque([]) for _ in range(N + 1)]
for _ in range(M):
    a, b = (int(i) for i in input().split())
    graph[a].append(b)
    graph[b].append(a)


seen = [-1] * (N + 1) 

def dfs(v):
    stack = [v]
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if seen[w] < 0:
                seen[w] = 0
                stack.append(w) 
        else:
            stack.pop()

ans = 0
for i in range(N):
    if seen[i + 1] < 0:
        dfs(i + 1)
        ans += 1

print(ans - 1)

Solution (Python):

class UnionFind:
    """Union-Find(素集合データ構造)"""
    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node
        
        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int):
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]
    
    def unite(self, x: int, y: int):
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def same(self, x: int, y: int):
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)
    
    def size(self, x: int) -> bool:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1


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

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

    ans = -1
    for i in lst.root:
        if i < 0:
            ans += 1
    print(ans)
    


if __name__ == '__main__':
    main()

Solution (Python):
n,m = list(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())

uf = UnionFind(n)
 
for a,b in ab:
    uf.union(a-1,b-1)

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

import sys
sys.setrecursionlimit(10**9)

def readInt():
    return list(map(int, input().split()))

n, m = readInt()

root = [-1] * n

def r(x):
    
    if root[x] < 0:
        
        return x
    else:
        root[x] = r(root[x])
        
        return root[x]

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

def size(x):
    x = r(x)
    
    return -root[x]

for i in range(m):
    x, y = readInt()
    x -= 1
    y -= 1
    unite(x, y)
    









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

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			if self.table[self.table[x]] >= 0:
				self.table[x] = self.table[self.table[x]]
			x = self.table[x]
		return x

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
		return

n, m = map(int, input().split())
uf = UnionFind(n)
ans = n-1
for _ in range(m):
	a, b = map(int, input().split())
	if uf.find(a-1) != uf.find(b-1):
		ans -= 1
		uf.unite(a-1, b-1)

print(ans)