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

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

class UnionFind:

    def __init__(self, n: int):
        self._n = n
        self._parents = [i for i in range(n)]
        self._rank = [1 for _ in range(n)]

    def unite(self, x: int, y: int) -> None:
        px = self.find(x)
        py = self.find(y)

        
        if px != py:
            self._link(px, py)

    def _link(self, x: int, y: int):
        if self._rank[x] < self._rank[y]:
            self._parents[x] = y
        elif self._rank[x] > self._rank[y]:
            self._parents[y] = x
        else:
            self._parents[x] = y
            self._rank[y] += 1

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

    def find(self, x: int) -> int:
        if self._parents[x] == x:
            return x

        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

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

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

s = set()
for i in range(1, N + 1):
    s.add(uf.find(i))

print(len(s) - 1)

Solution (Python):
from collections import deque
n, m = map(int ,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
v = [0]*n
ans = 0
for i in range(n):
  if v[i] == 0:
    ans += 1
    q = deque()
    q.append(i)
    v[i] = 1
    while q:
      node = q.popleft()
      for j in graph[node]:
        if v[j] == 0:
          q.append(j)
          v[j] = 1
print(ans-1)

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

def solve():
    n,m = map(int,input().split())
    p = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    father = [-1] * n
    count = n
    def getfather(x):
        if father[x] < 0: return x
        father[x] = getfather(father[x])
        return father[x]


    def union(x, y):
        x = getfather(x)
        y = getfather(y)
        nonlocal count
        if x != y:
            count -= 1
            if father[x] > father[y]:
                x,y = y,x
            father[x] += father[y]
            father[y] = x

    for a,b in p:
        union(a-1,b-1)
        
    print(count - 1)

if __name__ == '__main__':
    solve()

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 = map(int, input().split())
    AB = [[int(x) for x in input().split()] for _ in range(M)]
    
    uf = UnionFind(N)
    
    for a, b in AB:
        uf.union(a - 1, b - 1)
        
    print(uf.group_count() - 1)
    
if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
uf=UnionFind(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  uf.Unite(a,b)
s=set()
for i in range(1,n+1):
  s.add(uf.FindRoot(i))
print(len(s)-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):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')







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 solve():
    N, M = MI()
    uf = UnionFind(N)
    for i in range(M):
        a, b = MI1()
        uf.union(a, b)
    print(uf.group_count()-1)

        
if __name__ == '__main__':
    solve()

Solution (Python):



import typing




class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

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

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))


def main():
    import sys
    input = sys.stdin.readline

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

    for i in range(m):
        ai, bi = map(int, input().split())
        ai -= 1
        bi -= 1
        dsu.merge(ai, bi)

    ans = 0

    for j in range(1, n):
        if not dsu.same(0, j):
            dsu.merge(0, j)
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをほぼ定数オーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        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, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        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 = map(int, input().split())
    tree = UnionFind(n)
    for _ in range(m):
        a, b = map(int, input().split())
        tree.union(a - 1, b - 1)
    print(tree.group_count() - 1)

if __name__ == "__main__":
    main()

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 find(x):
    if parent[x]<0:
        return x
    else:
        parent[x]=find(parent[x])
        return parent[x]

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

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

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

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

def get_root():
    return [i for i, root in enumerate(parent) if root<0]

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

ans=0
for i in parent:
    if i<0:
        ans+=1

print(ans-1)

Solution (Python):
class UnionFind():
  def __init__(self,n):
    self.n = n
    self.parents = [-1] * (n+1)
  
  def find(self, x):
    if self.parents[x] < 0:
      return x
    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 -1 * self.parents[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()) - 1
  
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 = uf.group_count() - 1
print(ans)

Solution (Python):



def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return 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)]


def numb():
    l = len(par)
    num = 0
    for ij in range(l):
        if par[ij] < 0:
            num += 1
    return num

n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
par = [-1]*(n+1)
for j in range(m):
    unite(ab[j][0], ab[j][1])

print(numb() - 2)

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[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):
from sys import setrecursionlimit
setrecursionlimit(10**8)
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 roots(self):  
        return [i for i, x in enumerate(self.parent) if i == x]

N,M = map(int,input().split())
uf = UnionFind(N+1)
for i in range(M):
    a,b = map(int,input().split())
    uf.unite(a,b)
ans = len(uf.roots())-2
print(ans)

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

    
    def root(self, x) -> int:
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        elif x > y:
            u.parents[x] = y
        elif x < y:
            u.parents[y] = x

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


n, m = map(int, input().split())
cnt = n
u = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    if u.same(a-1, b-1):
        continue
    else:
        u.unite(a-1, b-1)
        cnt -= 1
if cnt > 0:
    print(cnt-1)
else:
    print(cnt)

Solution (Python):
from collections import deque 

def bfs(G,dist,s):
    q = deque([])
    dist[s] = 0
    q.append(s)
    
    while len(q) > 0:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv] != -1:
                continue
            
            dist[nv] = dist[v] + 1
            q.append(nv)
  


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

G = [[] for _ in range(n)]

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

dist = [-1]*n

cnt = 0
for v in range(n):
    if dist[v] != -1:
        continue
    bfs(G,dist,v)
    cnt += 1
    
print(cnt-1)

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


N,M=[int(i) for i in input().split(" ")]
uf = UnionFind(N)
for _ in range(M):
    A,B=[int(i) for i in input().split(" ")]
    uf.union(A-1,B-1)

c=Counter([uf.find(i) for i in range(N)])
print(len(c)-1)

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

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

print(uf.group_count() - 1)

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

    def ans(self):
        print(len(set(self.par))-1-1)

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

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

for i in range(1,n+1):
    uf.find(i)
uf.ans()

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def main():
    N,M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        a, b = map(int,input().split())
        uf.union(a,b)
    print(uf.group_count()-2)
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 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):




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[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):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)

N,M=map(int,input().split())
UF=UnionFind(N);c=0

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

for i in range(UF.n):
  if UF.parents[i]<0:
    c+=1
print(c-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 unite(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 size(self, x):
        return -self.par[self.find(x)]

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

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    uf.unite(a - 1, b - 1)
cnt = 0
for i in range(n):
    cnt += (uf.par[i] < 0)
print(cnt - 1)

Solution (Python):
N, M = map(int, input().split())
parents = [i for i in range(N+1)]

def find(x):
    if x == parents[x]:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
    
def same(A, B):
    x, y = find(A), find(B)
    if x==y:
        return
    else:
        parents[x] = y

for _ in range(M):
    A, B = map(int, input().split())
    same(A, B)
    
for i in range(N):
    find(i+1)

print(len(set(parents)) - 2)

Solution (Python):
N, M = map(int, input().split())
parents = [i for i in range(N+1)]

def find(x):
    if x == parents[x]:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
    
def same(A, B):
    x, y = find(A), find(B)
    if x==y:
        return
    else:
        parents[x] = y

for _ in range(M):
    A, B = map(int, input().split())
    same(A, B)
    
for i in range(N):
    find(i+1)

print(len(set(parents)) - 2)

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

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

def find(x):
    if x == par[x]:
        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
    par[x] = y

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

for i in range(q):
    a, b = map(int, input().split())
    unite(a, b)

for i in range(n):
    find(i+1)

par.pop(0)

al = set(par)
print(len(al) - 1)

Solution (Python):




from collections import deque

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


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

NIL = -1  
d = [-1 for i in range(n+1)]  
color = [NIL for i in range(n+1)]  


def bfs(start_node, color_id):  
    global color, d
    q = deque([start_node])
    d[start_node] = 0
    color[start_node] = color_id
    while len(q) != 0:
        u = q.popleft()
        for v in adjl[u]:
            if color[v] == NIL:
                d[v] = d[u]+1
                color[v] = color_id
                q.append(v)


color_id = 0
for u in range(1, n+1):  
    if color[u] == NIL:
        color_id += 1
        bfs(u, color_id)

colordic = {}
for u in range(1, n+1):
    colordic[color[u]] = True

print(len(colordic)-1)

Solution (Python):




from collections import deque

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


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

NIL = -1  
d = [-1 for i in range(n+1)]  
color = [NIL for i in range(n+1)]  


def bfs(start_node, color_id):  
    global color, d
    q = deque([start_node])
    d[start_node] = 0
    color[start_node] = color_id
    while len(q) != 0:
        u = q.popleft()
        for v in adjl[u]:
            if color[v] == NIL:
                d[v] = d[u]+1
                color[v] = color_id
                q.append(v)


color_id = 0
for u in range(1, n+1):  
    if color[u] == NIL:
        color_id += 1
        bfs(u, color_id)

colordic = {}
for u in range(1, n+1):
    colordic[color[u]] = True

print(len(colordic)-1)