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 get_all_members(self):
        pare_d = {}
        for i in range(self.n):
            parent = self.find(i)
            pare_d.setdefault(parent,[])
            pare_d[parent].append(i)
        return list(pare_d.values())

    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)

cnt = uf.group_count()
ans = max(cnt-1,0)
print(ans)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1



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,ipt().split())
    uf = UnionFind(n)
    for i in range(m):
        a,b = map(int,ipt().split())
        uf.union(a-1,b-1)
    k = uf.roots()
    print(len(k)-1)

    return None

if __name__ == '__main__':
    main()

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


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

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]


uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    uf.merge(a-1, b-1)
print(uf.parent.count(-1)-1)

Solution (Python):
class UnionFind:
    """素集合を木構造として管理する。"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.n = n
        self.cnt = n

    def root(self, x):
        """要素xの代表元を求める。O(α(N))"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を併合する。O(α(N))"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1
        return True

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める。O(α(N))"""
        return self.root(x) == self.root(y)

    def size(self, x):
        """要素xを含む集合の要素数を求める。O(α(N))"""
        return -self.parent[self.root(x)]

    def count(self):
        """集合の個数を求める。O(1)"""
        return self.cnt

    def groups(self):
        """集合を列挙する。list[list[int]]で返す。O(N)"""
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            res[self.root(i)].append(i)
        return [group for group in res if group]


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

uf = UnionFind(n)
for a, b in info:
    a -= 1
    b -= 1
    uf.merge(a, b)
print(uf.count() - 1)

Solution (Python):
import sys, math
from itertools import accumulate
sys.setrecursionlimit(10**9)

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

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


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

    print(uf.group_count()-1)

if __name__ == "__main__":
    main()

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

n,m=map(int,input().split())
UFa=UF(n)
for i in range(m):
  x,y=map(int,input().split())
  UFa.unite(x-1,y-1)
print(UFa.groupnum()-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)

    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.unite(a-1,b-1)
print(uf.group_count()-1)

Solution (Python):
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

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

X=[G.find(i) for i in range(N)]
print(len(set(X))-1)

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


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

    def find(self, x):
        r = x
        while self.par[r] >= 0:
            r = self.par[r]
        while x != r:
            tmp = self.par[x]
            self.par[x] = r
            x = tmp
        return r

    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 same(self, x, y):
        return self.find(x) == self.find(y)

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

N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.unite(A, B)
ans = len(set([uf.find(i) for i in range(N)])) - 1
print(ans)

Solution (Python):

import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y

def getOverlap(a, b):
    return max(0, min(a[1], b[1]) - max(a[0], b[0]) + 1)

def connected_components(n, graph):
    components, visited = [], [False] * n

    def dfs(start):
        component, stack = [], [start]

        while stack:
            start = stack[-1]

            if visited[start]:
                stack.pop()
                continue
            else:
                visited[start] = True
                component.append(start)

            for i in graph[start]:
                if not visited[i]:
                    stack.append(i)

        return component

    for i in range(n):
        if not visited[i]:
            components.append(dfs(i))

    return components

for _ in range(int(input()) if not True else 1):
    
    n, m = map(int, input().split())
    graph = [[] for _ in range(n+1)]
    for __ in range(m):
        x, y = map(int, input().split())
        graph[x] += [y]
        graph[y] += [x]
    cmp = connected_components(n+1, graph)
    print(len(cmp) - 2)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ 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()}


adlist = UnionFind(n+1)
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    if adlist.same(a, b) == False:
        adlist.union(a, b)
print(adlist.group_count()-2)

Solution (Python):

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b,p,rank):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
        elif rank[ap] < rank[bp]:
            p[ap] = bp
        else:
            p[bp] = ap
            rank[ap] += 1

        return False

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

p = [i for i in range(N)]
rank = [0] * N

for i in range(M):

    A,B = map(int,input().split())
    A -= 1
    B -= 1
    uf_union(A,B,p,rank)

ans = 0
for i in range(N):
    if uf_find(i,p) == i:
        ans += 1
print (ans-1)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for _ in range(n)]
def LIR(n):
    return [LI() for _ in range(n)]
def SR(n):
    return [S() for _ in range(n)]
def LSR(n):
    return [LS() for _ in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

    def unite(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 = list(range(n))
    rank = [0]*n
    s = n-1
    for _ in range(m):
        a,b = LI()
        a -= 1
        b -= 1
        if root(a) != root(b):
            s -= 1
            unite(a,b)
    print(s)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N)]
        self.siz=[1 for _ in range(N)]
        self.rank=[0 for _ in range(N)]
    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,a,b):
        a=self.find(a)
        b=self.find(b)
        if a==b:
            return 0
        else:
            if self.rank[a]>self.rank[b]:
                self.par[b]=a
                self.siz[a]+=self.siz[b]
            else:
                self.par[a]=b
                self.siz[b]+=self.siz[a]
                if self.rank[a]==self.rank[b]:
                    self.rank[b]+=1
    def size(self,a):
        return self.siz[self.find(a)]
    def same(self,a,b):
        return self.find(a)==self.find(b)

N,M=map(int,input().split())
DSU=UnionFind(N)
for _ in range(M):
    A,B=map(lambda x:int(x)-1,input().split())
    DSU.union(A,B)
s=set([DSU.find(i) for i in range(N)])
print(len(s)-1)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[y] 
        self.parent[y] = x 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def getsize(self,x): 
        return self.size[self.root(x)]



import sys
readline = sys.stdin.readline
read = sys.stdin.read

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

UF = UnionFind(n)

ans = n-1
for i in range(m):
    a,b = map(int,readline().split())
    if UF.merge(a-1,b-1):
        ans -= 1

print(ans)

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

class UnionFind():
    def __init__(self,num):
        self.n = num         
        self.parents = [-1 for i in range(self.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):
        xx=self.find(x)  
        yy=self.find(y)  
        if xx==yy:
            return     
        else:
            size_xx=abs(self.parents[xx]) 
            size_yy=abs(self.parents[yy]) 
            if size_xx>size_yy:
                xx,yy=yy,xx  

            self.parents[yy]+=self.parents[xx] 
            self.parents[xx]=yy   

    
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

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

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

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

    
    def state_grouping(self):
        return list(self.all_group_members().values())

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

print(len(uf.roots())-1)

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

def init(X):
  global belong
  global group
  belong=list(range(X))
  group=[[i] for i in range(X)]

def unite(x,y):
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  return False

init(N)
a,b=0,0
for i in range(M):
  a,b=map(int,input().split())
  unite(a-1,b-1)
P=0
for i in range(N):
  if len(group[i]):
    P+=1
print(P-1)

Solution (Python):
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    for j in range(2):
        C[i][j] -= 1

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

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

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

    def merge(self, x, y):  
        x = self.leader(x)
        y = self.leader(y)
        if x == y:
            return x
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return x

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

    def groups(self):  
        n = self.n
        leader_index = [-1] * n
        ind = 0
        for i in range(n):
            if self.parents[i] < 0:
                leader_index[i] = ind
                ind += 1
        ANS = [[] for i in range(ind)]
        for i in range(n):
            ld = self.leader(i)
            ANS[leader_index[ld]].append(i)
        return ANS

    def n_cc(self):  
        A = [i for i in self.parents if i < 0]
        return len(A)

U = UnionFind(n)
for i in range(m):
    U.merge(C[i][0],C[i][1])
print(U.n_cc()-1)

Solution (Python):
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

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

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

print(len(set(ds.find(i) for i in range(N)))-1)

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

def grouping(adj):
    "0-indexed の無向グラフを連結成分に分解する。"
    n = len(adj)
    ret = [-1] * n
    g = 0
    for v in range(n):
        if ret[v] == -1:
            ret[v] = g
            stack = [v]
            while stack:
                v = stack.pop()
                for nv in adj[v]:
                    if ret[nv] == -1:
                        ret[nv] = ret[v]
                        stack.append(nv)
            g += 1
    return ret

print(max(grouping(adj)))

Solution (Python):
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 unite(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 get_size(self, x):
        return -self.table[self._root(x)]


n, m = map(int, input().split())
uft = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uft.unite(a, b)

ans = 0
for p in uft.table:
    if p < 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 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()}

(n, m), *d = [[*map(int, o.split())] for o in open(0)]
UF = UnionFind(n)
for a, b in d:
    UF.union(a-1, b-1)
print(UF.group_count()-1)

Solution (Python):
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):
        return -self.root[self.Find_Root(x)]

N, M = map(int, input().split())
uni = UnionFind(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    uni.Unite(a, b)

R = set()
for i in range(1, N+1):
    R.add(uni.Find_Root(i))

print(len(R)-1)