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).



Sample input:
3 1
1 2


Sample output:
1

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
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')
# from math import ceil, floor, log2
# from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


import typing


# See:
# https://github.com/not522/ac-library-python/blob/master/atcoder/dsu.py
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
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
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
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)

Submission status: Accepted

Solution code:
# Connect Cities
# Union Findデータ構造（素集合データ構造）
 
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())
 
#入力:[n1,n2,...nk](int:整数配列)
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)

Submission status: Accepted

Solution code:
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  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # 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, 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)

Submission status: Accepted

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

    # 要素xが所属するグループの根を返す
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Connect Cities
# Union Findデータ構造（素集合データ構造）

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

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

	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)

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

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)