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

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())
if __name__ == '__main__':
    input = sys.stdin.readline
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for i in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        uf.union(a, b)

    print(uf.group_count()-1)

Solution (Python):
class UnionFind:
  par = None
  
  def __init__(self, n):
    self.par = [0] * n
    
  def root(self, x):
    if(self.par[x] == 0):
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.root(self.par[x])
  
  def unite(self, x, y):
    if(self.root(x) != self.root(y)):
      self.par[self.root(x)] = self.root(y)
      
  def same(self, x, y):
    return self.root(x) == self.root(y)
  
N, M = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(M):
  A, B = list(map(int, input().split()))
  UF.unite(A - 1, B - 1) 
ans = 0
for i in range(N):
  if(UF.par[i] == 0):
    ans += 1
print(ans - 1)

Solution (Python):
import types

_atcoder_code = """


__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_dsu_code = """
import typing


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

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

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

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

        if x == y:
            return x

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

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

        return x

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

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

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

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

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

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

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

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

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

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

atcoder.dsu = types.ModuleType('atcoder.dsu')
exec(_atcoder_dsu_code, atcoder.dsu.__dict__)
DSU = atcoder.dsu.DSU

import sys


sys.setrecursionlimit(10**9)

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

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

print(len(d.groups()) - 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m = list(map(int,input().split()))

d = {}
for i in range(m):
    fr, to = list(map(int,input().split()))
    d[fr] = d.get(fr, []) + [to]
    d[to] = d.get(to, []) + [fr]
    
visited = [0 for i in range(n+1)]

def connect(node, i):
    visited[node] = i
    
    if node in d:
        for neig in d[node]:
            if visited[neig] == 0:
                connect(neig, i)
ans = 1
for key in range(1,n+1):
    if visited[key] == 0:
        connect(key, ans)
        ans += 1

print(max(visited)-1)

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]
"""
n,k = ip()
x = [inp() for i in range(n)]
"""
import sys
sys.setrecursionlimit(10**6)
def dfs(u):
    global vis,graph
    vis.add(u)
    for i in graph[u]:
        if i not in vis:
            dfs(i)


n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)
vis = set()
ct = 0
for i in range(1,n+1):
    if i not in vis:
        dfs(i)
        ct += 1
print(ct-1)

Solution (Python):
def main():
    import sys
    from collections import deque

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    sys.setrecursionlimit(100001)
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)


    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            d=deque()
            d.appendleft(i)
            while d:
                a=d.popleft()
                mark[a]=1
                for j in dic[a]:
                    if mark[j]:
                        continue
                    
                    d.appendleft(j)
        i+=1
        if i==N:
            break
    
    print(count-1)
main()

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

arr=[[] for i in range(N)]

check=[0]*N
ans=[]

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

q=[]
cnt=0
for i in range(N):
    if check[i]==0:
        cnt+=1
    q.append(i)
    
    while q:
        x=q.pop()
        if check[x]==0:
            check[x]=1
            for j in arr[x]:
                q.append(j)
        
print(cnt-1)

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

print(uf.group_count()-2)

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

A = [-1 for _ in range(N + 1)]

def search(ls, n):
  while ls[n] > 0:
    n = ls[n]
  return n

for i in range(M):
  a, b = map(int, input().split())
  aa = search(A, a)
  bb = search(A, b)
  if aa != bb:
    A[b] = aa
    A[bb] = aa
    
group = -1
for i in range(1, N + 1):
  if A[i] == -1:
    group += 1
    
print(group)

Solution (Python):
N, M = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(M)]

par = [i for i in range(N)]

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

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

for x in range(N):
    find(x)

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

Solution (Python):
from collections import deque

N, M = [int(x) for x in input().split()]
route = {int(x): [] for x in range(N)}

for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    route[a].append(b)
    route[b].append(a)

queue = deque()
queue.append(0)

all_town = set([int(x) for x in range(N)])

result = 0
while queue:
    pos = queue.popleft()
    all_town.discard(pos)

    for next_pos in route[pos]:
        if next_pos in all_town:
            queue.append(next_pos)

    if not queue:
        if all_town:
            queue.append(all_town.pop())
            result += 1

print(result)

Solution (Python):
def main():


    

    
    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)
    
    tank = set([])
    for i in range(n):
        tank.add(find(i))
    
    print(len(tank)-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 test(self):
        return self.parents
    def test2(self):
        return sum(z <0 for z in self.parents)
    
N, M = map(int, input().split()) 
uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    uf.union(A, B)
    
print(uf.test2()-1)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    a,b=map(int,input().split())
    a-=1;b-=1
    uf.union(a,b)
print(len(set([uf.find(i)for i in range(N)]))-1)

Solution (Python):
f=lambda:map(int,input().split())
def r(x):
  while p[x]>=0: x=p[x]
  return x
def u(x,y):
  x,y=r(x),r(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
n,m=f()
p=[-1]*n
for _ in range(m):
  a,b=f()
  u(a-1,b-1)
print(sum(i<0 for i in p)-1)

Solution (Python):
from collections import deque
from collections import defaultdict

n, m = map(int, input().split())
g = defaultdict(list)
s = set(list(range(1, n+1)))
ans = 0

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

while s:
    root = s.pop()
    q = deque()
    q.append(root)
    done = set()
    done.add(root)

    while q:
        node = q.popleft()

        for adj in g[node]:
            if adj not in done:
                done.add(adj)
                q.append(adj)
                s.remove(adj)
    ans += 1

print(ans - 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())
uf = UnionFind(n)
for i in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  uf.Unite(a,b)
s = set()
for i in range(n):
  s.add(uf.Find_Root(i))
print(len(s)-1)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
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()}

uf = UnionFind(N)
for _ in range(M):
    a, b = mapint()
    uf.union(a-1, b-1)
print(uf.group_count()-1)

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

N, M = map(int, input().split())
ABs = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

uf = UnionFind(N)

for AB in ABs:
    uf.union(AB[0], AB[1])

print(uf.group_count()-1)

Solution (Python):
from collections import deque

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

adjacency_list = [[] for i in range(N)]
for i in range(M):
    tmp = list(map(int, input().split()))
    adjacency_list[tmp[0] - 1].append(tmp[1] - 1)
    adjacency_list[tmp[1] - 1].append(tmp[0] - 1)
con_component = 0


visited_set = set(range(N))
queue = deque()
while visited_set:
    con_component += 1
    queue.append(visited_set.pop())
    while len(queue) != 0:
        ind = queue.popleft()
        
        for adjacency in adjacency_list[ind]:
            
            if adjacency in visited_set:
                visited_set.remove(adjacency)
                queue.append(adjacency)
print(con_component - 1)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(idx):
    for x in arr[idx]:
        if not vis[x]:
            vis[x] = True
            dfs(x)


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

arr = [[] * (n + 1) for _ in range(n + 1)]
vis = [False] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)

ans = 0

if m == 0:
    print(n-1)
    sys.exit()

dfs(1)
for i in range(2, n + 1):
    if not vis[i]:
        vis[i] = True
        dfs(i)
        ans += 1

print(ans)

Solution (Python):
from collections import deque
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)
visited=[0]*n
def bfs(s):
    q=deque([s])
    visited[s]=1
    while q:
        x=q.popleft()
        for nx in edge[x]:
            if visited[nx]==0:
                visited[nx]=1
                q.append(nx)
    return
ans=0
for s in range(n):
    if visited[s]==0:
        bfs(s)
        ans+=1
print(ans-1)

Solution (Python):
class UnionFind:
    __slots__ = ["_data_size", "_roots"]
 
    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size
 
    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x
 
    def is_connected(self, x: int, y: int) -> bool:
        return self[x] == self[y]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x
 
 
import sys
 
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())
tree = UnionFind(N)
res = []
ans=0
for _ in range(Q):
  u, v = map(int, readline().split())
  tree.unite(u-1, v-1)
for u in range(1,N):
  if not tree.is_connected(u, 0):
      ans+=1
      tree.unite(u, 0)
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        return self.find(x) == self.find(y)
N,M = map(int,input().split())
q = UnionFind(N)

for _ in range(M):
    x,y = map(int,input().split())
    q.union(x-1,y-1)
set_ = set()
cnt = 0
for i in range(N):
    if q.find(i)<0:
        cnt += 1
    else:
        set_.add(q.find(i))
print(cnt + len(set_)-1)

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

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

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

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

        if x == y:
            return

        self.parents[y] = x
        
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)

size = 0
for i in range(n):
    if uf.parents[i] == i:
        size += 1
print(size-1)

Solution (Python):
class UnionFind():
    """
        unionfindtree のクラス
            グループを管理するデータ構造.
            全てのメソッドの計算量が O(log(n)) よりも小さい
        init: 管理対象の個数 n を用いて初期化
        find: ある要素 x の親がどの要素か返す
        union: ある要素 x と y が属しているグループを結合して1つのグループとする
        msize: ある要素 x が属するグループの大きさを返す
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n
        self.rank = [0]*n
        self.size = [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 の属するグループを結合するメソッド
            x と y のランク(子の数)の小さい方が結合先の親となる
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def msize(self, x):
        """
            ある要素 x の属するグループの大きさを返すメソッド
        """
        return self.size[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())


def main():
    N, Q = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(Q):
        u, v = map(int, input().split())
        uf.union(u-1, v-1)
    print(uf.group_count()-1)   
if __name__ == "__main__":
    main()

Solution (Python):
v, e = map(int,input().split())
par = [i for i in range(v+1)]

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

for i in range(e):
  a, b = map(int, input().split())
  unite(a, b)
  
cnt = 0
for i in range(v+1):
  if i == par[i]:
    cnt += 1

print(cnt-2)

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


for i in range(M):
    a = list(map(int, input().split()))
    uf.union(a[0]-1, a[1]-1)

print(uf.group_count()-1)

Solution (Python):


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

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

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

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

par = [-1]*n

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

ans = 0
for i in range(n):
    if -par[i]>0:
        ans += 1
print(ans-1)

Solution (Python):

from collections import Counter
N,M=map(int,input().split())
 

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

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


  
 
for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1, b-1
  unite(a,b)
 
for i in range(N):
  find(i)
c=Counter(par)
print(len(c)-1)

Solution (Python):




import sys

def read_str(): return sys.stdin.readline().strip()
def read_int(): return int(sys.stdin.readline().strip())
def read_ints(): return map(int, sys.stdin.readline().strip().split())
def read_str_split(): return list(sys.stdin.readline().strip())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))

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

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a and a < self._n
        assert 0 <= b and a < 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 and a < self._n
        assert 0 <= b and a < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a and 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 and a < self._n
        return -self.parent_or_size[self.leader(a)]

    def groups(self):
        leader_buf = [0] * self._n; group_size = [0] * self._n
        for i in range(self._n):
            leader_buf[i] = self.leader(i)
            group_size[leader_buf[i]] += 1
        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)
        result = [v for v in result if v]
        return result

def Main():
    n, m = read_ints()
    uf = dsu(n)
    for _ in range(m):
        a, b = read_ints()
        uf.merge(~-a, ~-b)
    ans = len(uf.groups())
    print(ans-1)

if __name__ == '__main__':
    Main()

Solution (Python):

from networkx.utils import UnionFind
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n,m=map(int, input().split())
    uf = UnionFind()
    for i in range(1,n+1):
        _=uf[i]
    for _ in range(m):
        a,b=map(int, input().split())
        uf.union(a, b)  
    print(len(list(uf.to_sets()))-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 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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def group_count(self):
        return len(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 collections
n,m=map(int,input().split())
par=[i for i in range(n)]
def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
for _ in range(m):
    a,b=map(int,input().split())
    aa=find(a-1)
    bb=find(b-1)
    
    par[aa]=bb


for i in range(n):
    par[i]=find(i)

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

Solution (Python):
import sys


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

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

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

        
        if X == Y:
            return

        
        if self.parents[X] > self.parents[Y]:
            X, Y = Y, X

        
        self.parents[X] += self.parents[Y]
        
        self.parents[Y] = X


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]


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

c = 0
for i in range(N):
  if uf.parents[i] < 0:
    c += 1

print(c-1)