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):
N, M = map(int, input().split())
L = [0] * N
D = {}
c = 1
for i in range(M):
  A, B = map(int, input().split())
  if L[A - 1] == L[B - 1] == 0:
    D[c] = set()
    D[c].add(A)
    D[c].add(B)
    L[A - 1] = c
    L[B - 1] = c
    c += 1
  elif L[A - 1] == 0:
    D[L[B - 1]].add(A)
    L[A - 1] = L[B - 1]
  elif L[B - 1] == 0:
    D[L[A - 1]].add(B)
    L[B - 1] = L[A - 1]
  elif L[A - 1] != L[B - 1]:
    if len(D[L[A - 1]]) < len(D[L[B - 1]]):
      A, B = B, A
    D[L[A - 1]] |= D[L[B - 1]]
    for j in D.pop(L[B - 1]):
      L[j - 1] = L[A - 1]
  
print(len(D) + L.count(0) - 1)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, M, *AB = map(int, open(0).read().split())

uf = UnionFind(N)
for a, b in zip(*[iter(AB)] * 2):
    uf.union(a - 1, b - 1)

print(len({uf.find(i) for i in range(N)}) - 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())
  
v, e = map(int, input().split())
uf = UnionFind(v)
for i in range(e):
  a, b = map(int, input().split())
  uf.union(a-1, b-1)
  
print(uf.group_count()-1)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind:
    from typing import List, Set

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def merge(self, x, y) -> int:
        x = self.leader(x)
        y = self.leader(y)

        if x == y:
            return 0

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

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

        return self.parent[x]

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

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

    def size(self, x) -> int:
        return -self.parent[self.leader(x)]

    def groups(self) -> List[Set[int]]:
        groups = dict()

        for i in range(self.n):
            p = self.leader(i)
            if not groups.get(p):
                groups[p] = set()
            groups[p].add(i)

        return list(groups.values())


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

    uf = UnionFind(N)

    for _ in range(M):
        A, B = map(lambda x: int(x) - 1, input().split())
        uf.merge(A, B)

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

from typing import Iterable, List
import sys
def main(N, M, AB):
    uf = UnionFindTree(N)
    for a, b in AB:
        a, b = a - 1, b - 1
        uf.union(a, b)
    print(len(uf.groups()) - 1)

class UnionFindTree:
    __slots__ = ('parent')

    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

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

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

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

    def groups(self) -> List[int]:
        return [i for i, p in enumerate(self.parent) if p < 0]

if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(M)]
    main(N, M, AB)

Solution (Python):
class UnionFind:
	"""
	class UnionFind
	https://note.nkmk.me/python-union-find/
	
	order O(log(n))
	
	n = the number of elements
	parents = the list that contains "parents" of x. be careful that it doesn't contain "root" of x.
	"""
	def __init__(self, n):
		"""
		make UnionFind
		:param n: the number of elements
		"""
		self.n = n
		self.parents = [-1] * n
	
	def find(self, x):
		"""
		:param x: an element
		:return: the root containing 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):
		"""
		:param x, y: an element
		"""
		
		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()}

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

Solution (Python):
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

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

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


def main():
    n, m = map(int, sys.stdin.buffer.readline().split())
    U = UnionFind(n)
    for i in sys.stdin.buffer.readlines():
        a, b = map(lambda x: int(x) - 1, i.split())
        U.union(a, b)
    print(U.group_count() - 1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

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

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


def main():
    n, m = map(int, sys.stdin.buffer.readline().split())
    U = UnionFind(n)
    for x in sys.stdin.buffer.readlines():
        a, b = map(lambda x: int(x) - 1, x.split())
        U.union(a, b)
    print(U.group_count() - 1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

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

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


def main():
    n, m = map(int, sys.stdin.buffer.readline().split())
    U = UnionFind(n)
    for x in sys.stdin.buffer.readlines():
        a, b = map(int, x.split())
        U.union(a-1, b-1)
    print(U.group_count() - 1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, m = map(int, sys.stdin.buffer.readline().split())
    U = UnionFind(n)
    for x in sys.stdin.buffer.readlines():
        a, b = map(int, x.split())
        U.union(a-1, b-1)
    ans = {}
    for i in range(n):
        ans.setdefault(U._root(i), []).append(i)
    print(len(ans) - 1)


if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
    
    
    
    
    from collections import deque
    n,m=map(int,input().split())
    ab=[[] for _ in range(n)]
    for i in range(m):
        a,b=map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    visit=[False]*n
    cnt=0
    while False in visit:
        for i in range(n):
            if visit[i]==True:
                continue
            cnt+=1
            q=deque()
            q.append(i)
            while q:
                x=q.popleft()
                visit[x]=True
                for nx in ab[x]:
                    if visit[nx]==True:
                        continue
                    q.append(nx)
    print(cnt-1)            

if __name__ == '__main__':
    resolve()

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

parent = [-1] * N


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


for i in range(0, M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1

    groupA = get_group_root(A)
    groupB = get_group_root(B)

    if groupA == groupB:
        continue
    elif parent[groupA] < parent[groupB]:
        parent[groupB] = A
        parent[groupA] -= 1
    else:
        parent[groupA] = B
        parent[groupB] -= 1


def check(x):
    return x < 0


print(sum(list(map(check, parent))) - 1)

Solution (Python):

from collections import deque

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

w = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    w[a-1].append(b-1)
    w[b-1].append(a-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        d.append(i)
        while d:
            x = d.pop()
            for i in w[x]:
                if c[i] == 0:
                    c[i] = 1
                    d.append(i)

print(ans)

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

par=[i for i in range(n)]
size=[1]*n

def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return

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

ans={find(i) for i in range(n)}

print(len(ans)-1)

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

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

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

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

        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


    def count(self, x):
        return (-1)*self.root[self.find(x)]

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

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

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.par = [-1]*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 roots(self):
        return [i for i, x in enumerate(self.par) if x<0]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)      
        if x==y:
            return        
        if self.par[x] > self.par[y]:
            x, y = y, x       
        self.par[x] += self.par[y]
        self.par[y] = x
    def group_count(self):
        return len(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):
n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
done = [False] * n
s = []
cnt = 0
for i in range(n):
    if not done[i]:
        s.append(i)
        while not s == []:
            v = s.pop()
            done[v] = True
            for nxt in edge[v]:
                if not done[nxt]:
                    s.append(nxt)
        cnt += 1
print(cnt - 1)

Solution (Python):
N,M =map(int,input().split())
A = [0] * M
B = [0] * 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 i in range(M):
    a, b = map(int, input().split())
    uf.union(a-1,b-1)
print(len(uf.roots())-1)

Solution (Python):
import networkx as nx
N, M = map(int, input().split())

G=nx.Graph()

for _ in range(M):
    a, b = map(int, input().split())
    G.add_edge(a,b)

tmp= list(nx.connected_components(G))

count=0

for i in tmp:
    count+=len(i)


print(N-count+len(tmp)-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 same(self, x, y):
        return self.find(x) == self.find(y)


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

h = {}
for i in range(N):
    h[u.find(i)] = True

print(len(h)-1)

Solution (Python):
N, M = map(int, input().split())
Ne = [[] for _ in range(N)]
C = [0] * N
for i in range(M):
    A, B = map(int, input().split())
    Ne[A-1].append(B-1)
    Ne[B-1].append(A-1)
c=0
l = []
for i in range(N):
    if C[i] == 0:
        c+=1
        l.append(i)
        while len(l)>0:
            v=l.pop()
            C[v] = c
            for j in Ne[v]:
                if C[j] == 0:
                    l.append(j)
print(c-1)

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

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

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
n,m=map(int,input().split())
uf=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    uf.union(a,b)
ans=set()
for i in range(1,n+1):
    
    ans.add(uf.find(uf.par[i]))
print(len(ans)-1)

Solution (Python):

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

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


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


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


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


par = [-1]*n


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

Solution (Python):
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]

class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)
        self.sizes = [1] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    def union(self, x, y, w=1):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.sizes[ry] += self.size(rx)
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.sizes[rx] += self.size(ry)
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

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

uf=WeightedUnionFind(n)

for a,b in ab:
    uf.union(a,b)

s=set()
ans=0
for i in range(n):
    if not uf.find(i+1) in s:
        ans+=1
        s.add(uf.find(i+1))
print(ans-1)

Solution (Python):
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
d={i+1:[] for i in range(n)}
for i in range(m):
    x,y=map(int,input().split())
    d[x].append(y)
    d[y].append(x)

visit=set()
ans= 0 
for i in range(1,n+1):
    if i not in visit:
        ans+=1
        stack = [i]
        while stack:
            c=stack.pop()
            visit.add(c)
            for j in d[c]:
                if j not in visit:
                    stack.append(j)
print(ans-1)

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.rank = [0] * (n+1)
 
    
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
 
  
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if self.rank[x] < self.rank[y]:
      self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
 
  
  def same_check(self, x, y):
    return self.find(x) == self.find(y)
n,m = map(int,input().split())
u = UnionFind(n)
for _ in range(m):
  ai,bi = map(int,input().split())
  u.union(ai,bi)
s = [0 for _ in range(n+1)]
for i in range(1,n+1):
  s[u.find(i)] = 1
print(sum(s)-1)

Solution (Python):
import sys
input = sys.stdin.readline

n,m=map(int,input().split())
d={i+1:[] for i in range(n)}
for i in range(m):
    x,y=map(int,input().split())
    d[x].append(y)
    d[y].append(x)

visit=set()
ans= 0 
for i in range(1,n+1):
    if i not in visit:
        ans+=1
        stack = [i]
        while stack:
            c=stack.pop()
            visit.add(c)
            for i in d[c]:
                if i not in visit:
                    stack.append(i)
print(ans-1)

Solution (Python):
def root(list_parent, x):
    if(list_parent[x] == x):
        return x
    else:
        list_parent[x] = root(list_parent, list_parent[x])
        return list_parent[x]

def unite(list_parent, x, y):
    x = root(list_parent, x)
    y = root(list_parent, y)

    if(x == y):
        return list_parent

    if x > y:
        list_parent[y] = x
    else:
        list_parent[x] = y

    return list_parent

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

    list_parent = []
    for i in range(N):
        list_parent.append(i)

    for i in range(M):
        A, B = map(int, input().split())
        list_parent = unite(list_parent, A-1, B-1)

    set_root = set()
    for i in list_parent:
        root_i = root(list_parent, i)
        if root_i not in set_root:
            set_root.add(root_i)

    print(len(set_root) - 1)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(500*500)

N, M = map(int, input().split())
UF = [-1] * (N+1)
def find(x):
    global UF
    if UF[x] == -1:
        return x
    else:
        UF[x] = find(UF[x])
        return UF[x]
def union(x,y):
    global UF
    xx = find(x)
    yy = find(y)
    if UF[x] == UF[y] == -1:
        UF[y] = xx
        return
    elif xx == yy:
        return 
    else:
        UF[yy] = xx
        return 
    
for _ in range(M):
    a, b = map(int, input().split())
    union(a,b)

ans = set()
for i in range(1,N+1):
    ans.add(find(i))
    
print(len(ans)-1)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


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

def union(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


n, m = LI()
par = [i for i in range(n)]
rank = [0] * n
for _ in range(m):
    a, b = LI()
    if root(a-1) != root(b-1):
        union(a-1, b-1)

s = set()
for i in range(n):
    s.add(root(i))
ans = len(s)-1
print(ans)

Solution (Python):

def input2():
	return map(int,input().split())


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

class UnionFind():
	"""docstring for 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
		
n,m=input2()
AB=[input_array() for _ in range(m)]


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

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

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

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

print(uf.group_count()-2)

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.g = [i for i in range(n)]
    self.n = n
  def whichclass(self, x):
    if self.g[x]==x:
      return x
    else:
      self.g[x] = self.whichclass(self.g[x])
      return self.g[x]
  def union(self, x, y):
    cx = self.whichclass(x)
    cy = self.whichclass(y)
    if cx==cy:
      return
    minc = min(cx, cy)
    maxc = max(cx, cy)
    self.g[maxc] = minc
  def __getitem__(self, x):
    return self.whichclass(x)
  
N, M = map(int, input().split())
UF = UnionFind(N)
for i in range(M):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  UF.union(a, b)
count = [0 for i in range(N)]
for i in range(N):
  count[UF[i]] = 1
print(sum(count)-1)