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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
#print(uf.parents)

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

Submission status: Accepted

Solution code:
#unionfind木_集合の管理_同じ集合の数を数える場合：
#parには集合の数と親の名前を同時にメモ化する（根なら-size, 子なら親）
def find(k):#要素k
    if par[k] < 0:#初期はparがすべて負の値
        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:
        #sizeが大きい方がi
        if i > j:#sizeはマイナス管理なので、i>jの時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)

Submission status: Accepted

Solution code:
#Union-Find木の実装
from collections import Counter
N,M=map(int,input().split())
 
#初期化
par=[i for i in range(N)]#親の要素(par[x]=xのときxは木の根)
rank=[0]*N#木の深さ
 
#木の根を求める
def find(x):
  #xが根だった場合xをそのまま返す
  if par[x] == x:
    return x
  else:
    #根が出るまで再帰する
    par[x] = find(par[x])
    return par[x]
 
#xとyの属する集合を併合
def unite(x,y):
  x=find(x)#xの根
  y=find(y)#yの根
  #根が同じなら何もしない
  if x == y:
    return
  #もし根の深さがyの方が深いなら
  if rank[x] < rank[y]:
    par[x] = y#yを根にする
  else:
    par[y] = x#xを根にする
    if rank[x] == rank[y]:
      rank[x]+=1
 
#xとyが同じ集合に属するか否か
#def same(x,y):
  #return find(x)==find(y)
 
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)

Submission status: Accepted

Solution code:
# Date [ 2020-09-26 21:09:39 ]
# Problem [ c.py ]
# Author Koki_tkg

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)  # aとbをマージ
    print(len(list(uf.to_sets()))-1)
    #for group in uf.to_sets():  # すべてのグループのリストを返す
        #print(group)

if __name__ == '__main__':
    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 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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

#UnionFindTreeクラスの定義
class UnionFind():
    #クラスコンストラクタ
    #selfはインスタンス自身
    def __init__(self, n):
        #親ノードを-1に初期化する
        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]

    #xとyの木を併合する
    def union(self, x, y):
        #x,yの根をX,Yとする
        X = self.find(x)
        Y = self.find(y)

        #根が同じなら結合済み
        if X == Y:
            return

        #ノード数が多い方をXとする
        if self.parents[X] > self.parents[Y]:
            X, Y = Y, X

        #XにYのノード数を足す
        self.parents[X] += self.parents[Y]
        #Yの根を X>0 とする
        self.parents[Y] = X


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

#UnionFindインスタンスの生成
uf = UnionFind(N)
for a, b in info:
    #インデックスを調整し、a,bの木を結合
    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)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]

n,m = list(map(int, input().split()))
uf = UnionFindTree(n)
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    uf.connect(a,b)
s = set()
for i in range(n):
    s.add(uf.root(i))
print(len(s)-1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split( ))
loads = []
teams = [[i] for i in range(N)]
syozoku = {i:i for i in range(N)}
for _ in range(M):
    A,B = map(int,input().split( ))
    if syozoku[A-1] != syozoku[B-1]:
        hairu,nukeru = min(syozoku[A-1],syozoku[B-1]),max(syozoku[A-1],syozoku[B-1])
        team = teams[nukeru]
        teams[nukeru] = []
        teams[hairu] += team
        for i in team:
            syozoku[i] = hairu

ans = -1
for team in teams:
    if len(team) != 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
xy = [map(int, input().split()) for _ in range(m)]
x, y = [list(i) for i in zip(*xy)]
ans=0

l=[-1]*n

def rootfind(a):
    changelist=[]
    while 1:
        if l[a-1]>0:
            changelist.append(a)
            a=l[a-1]
        else:
            break
    for e in changelist:
        l[e-1]=a
    return a


def rootunion(c,d):
    cr=rootfind(c)
    dr=rootfind(d)
    if cr==dr:
        pass
    else:
        l[cr-1]=dr


for j in range(m):
    p=x[j]
    q=y[j]
    rootunion(p,q)

for o in l:
    if o<0:
        ans+=1

print(ans-1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
data=list(range(n))
cnt=n-1
def find(x):
    if data[x]==x:
        return x
    else:
        data[x]=find(data[x])
        return data[x]
for i in range(m):
    a,b=map(int,input().split())
    a=find(a-1)
    b=find(b-1)
    if a!=b:
        data[a]=b
        cnt-=1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
    # ノードxのrootノードを見つける
        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):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        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が属する木のサイズを返す
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
    # 入力ノード(x,y)が同じグループに属するかを返す
        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())
 
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
 
 
 
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
print(len(u.roots())-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 roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]

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

print(len(towns.roots())-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)
 
    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())
 
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
 
 
 
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
 
n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)

print(u.group_count()-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())
ans=0
U = UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  U.union(a,b)
print(U.group_count()-1)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.r = [-1 for i in range(n)]
    
    def root(self, x):
        if self.r[x] < 0:
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] < self.r[y]:
            temp = x
            x = y
            y = temp
        self.r[x] += self.r[y]
        self.r[y] = x
        return True
    
    def size(self, x):
        return -self.r[self.root(x)]

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

ans = 0
for i in UF.r:
    if i < 0:
        ans += 1

print(ans-1)

Submission status: Accepted

Solution code:
# Union Find
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[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)]


n, m = map(int, input().split())
# 初期化
# 根なら-size,子なら親の頂点
par = [-1] * n

for _ in range(m):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)
print(len(list(filter(lambda x: x < 0, par))) - 1)

Submission status: Accepted

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


n, m = map(int, input().split())
g = DSU(n)
ab = [tuple(map(int, input().split())) for _ in range(m)]
for a, b in ab:
    g.merge(a - 1, b - 1)
print(len(g.groups()) - 1)

Submission status: Accepted

Solution code:
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 _ 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,io,os
z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
y=lambda:map(int,z().split())
n,m=y()
k={}
p={}
r=0
e=0
def path(r):
    while p[r]>=0:r=p[r]
    return r
for i in range(m):
    a,b=y();a-=1;b-=1;e+=1
    if a in k:
        if b in k:
            va,vb=path(k[a]),path(k[b])
            if va>vb:p[va]=vb
            elif va<vb:p[vb]=va
            else:e-=1
        else:k[b]=k[a]
    else:
        if b in k:k[a]=k[b]
        else:
            k[a]=r
            k[b]=r
            p[r]=-1
            r+=1
print(n-1-e)

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=[int(_) for _ in input().split()]
uf =UnionFind(n)

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

print(uf.group_count()-1)

Submission status: Accepted

Solution code:
#input

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.rank = [1] * n
        self.grp = n
    
    def root(self,x):
        if self.parent[x] == x :
            return x
        else :
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    
    def same(self,x,y):
        return self.root(x) == self.root(y)
    
    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
 
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else :
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        self.grp -= 1
        

def input_1():
    n, m = map(int,input().split())
    brg = [tuple(map(int,input().split())) for i in range(m)]
    return n,m,brg

def input_2(n):
    brg = [( 2*i-1 , 2*i ) for i in range(1,int(n/2))]
    return n,int(n/2)-1,brg

def main():
    n,m,brg = input_1()
    #n,m,brg = input_2(100000)
    uf = UnionFind(n)
    for i in range(m):
        uf.unite(brg[i][0]-1,brg[i][1]-1)
    
    print(uf.grp-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
g = [[] for _ in range(n)]

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

from collections import deque

d = [None] * n
def bfs(u):
    queue = deque([u])
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
cnt=0
for i in range(n):
    if d[i] is None:
        cnt+=1
        bfs(i)
print(cnt-1)

Submission status: Accepted

Solution code:
import sys
from sys import stdin
def I():
    return stdin.readline().rstrip()
def MI():
    return map(int,stdin.readline().rstrip().split())
def LI():
    return list(map(int,stdin.readline().rstrip().split()))
#main part

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, K = MI()
uf = UnionFind(N)
        
for i in range(K):
    A, B = MI()
    uf.union(A-1, B-1)
 
print(uf.group_count()-1)

Submission status: Accepted

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

par=[i for i in range(n)]
# ro=dict()
#
# for i in range(n):
#     ro[i]=1

def root(i):
    if par[i]==i:
        return i
    else:
        a=root(par[i])
        par[i]=a
        return a

def unite(x,y):
    rx=root(x)
    ry=root(y)
    if rx!=ry:
        par[rx]=ry
        # ro[ry]+=ro[rx]
        # ro[rx]=0

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

ans=set()

for i in range(n):
    rt=root(i)
    ans.add(rt)

# from collections import Counter as cnt
#
# bb=ro.values()
# ans=dict(cnt(ro.values()))

print(len(ans)-1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
par = [i for i in range(n+1)]
root = [i for i in range(n+1)]
par[0] = 1
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    
for i in range(m):
    a,b = map(int,input().split())
    unite(a,b)
for i in range(n+1):
  root[i] = find(i)
print(len(set(root))-1)