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: Runtime Error

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

uf = DSU(N)
merge = uf.merge
same = uf.same

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


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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
G = [[] for _ in range(N)]
seen = [False] * N

for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    G[A].append(B)
    G[B].append(A)


def dfs(x, G, seen, before):
    seen[x] = True
    for next in G[x]:
        if next == before:
            continue
        if seen[next]:
            continue
        dfs(next, G, seen, x)

ans = 0
for i in range(N):
    if seen[i]:
        continue
    dfs(i, G, seen, -1)
    ans += 1
    for j in range(N):
        seen[i] = False

print(ans-1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ab = [0] * M
for i in range(M):
    ab[i] = list(map(int, input().split()))

import sys
sys.setrecursionlimit(100500)

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):
    uf.union(ab[i][0], ab[i][1])

print(uf.group_count() - 1)

Submission status: Runtime Error

Solution code:
N, M = map(int,input().split())
for x in range(1, M - 1):
  print('{0:2d} {1:3d} {2:4d}'.format(int(input()), int(input())))
print(N - (M + 1))

Submission status: Runtime Error

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 False

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

  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):
  x,y=map(int,input().split())
  uf.union(x,y)
print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
import numpy as np

l = input().split()
N = int(l[0])
M = int(l[1])
arr = [0]*N
for i in range(M):
  l = input().split()
  #A[i] = l[0]
  #B[i] = l[1]
  arr[int(l[0])] = 1
  arr[int(l[1])] = 1

print(N-np.sum(arr))

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit

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

    def union(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.find(a), self.find(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, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.find(a) == self.find(b)

    def find(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.find(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.find(a)]

    def groups(self):
        find_buf = [self.find(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[find_buf[i]].append(i)
        return [r for r in result if r != []]

N, M = map(int,input().split())
uf = UnionFind(N)
setrecursionlimit(10**9+7)

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

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

Submission status: Runtime Error

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy as np
import sys
import math
import collections
par = []
def init(n):
    for i in range(n):
        par.append(i)

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

def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False

def unite(x,y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    par[x] = y
n,m = L()
ab = NL(m)
init(n)
#print(ab)
#print(par)
for a,b in ab:
    unite(a,b)
#print(par)
count = collections.Counter(par)
print(len(count)-1)

Submission status: Runtime Error

Solution code:
def resolve():
    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,b)
    grp = UF.group_count()
    if grp == 1:
        print(0)
    else:
        print(grp-1)

resolve()

Submission status: Runtime Error

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 _ in range(m):
  a,b = map(int,input().split())
  uf.union(a,b)
print(len(uf.all_group_members())-1)

Submission status: Runtime Error

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

input = sys.stdin.readline
N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a, b)

print(uf.group_count() - 1)

Submission status: Runtime Error

Solution code:
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):#ｘの根（親）を返す
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.find(self.parent[x])#経路圧縮
            return self.parent[x]

    def unite(self,x,y):#ｘ、ｙの集合の統合
        x=self.find(x)
        y=self.find(y)
        if x!=y:
            if self.rank[x]<self.rank[y]:#ランクの比較
                self.parent[x]=y
                self.size[y]+=self.size[x]
            else:
                self.parent[y]=x
                self.size[x]+=self.size[y]
                if self.rank[x]==self.rank[y]:
                    self.rank[x]+=1

    def is_same(self,x,y):#ｘ、ｙが同じ集合に属するかを判定する
        return self.find(x)==self.find(y)

    def group_size(self,x):#ｘが属する集合の大きさ
        return self.size[self.find(x)]

    def group_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.parent) if i==x]

    def group_count(self):#木の数を返す
        return len(self.roots())

    def all_group_members(self):#すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

n,m=map(int,input().split())
un=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    un.unite(a,b)
ans=un.group_count()-1
print(ans)

Submission status: Runtime Error

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)

#H = list(map(int, input().split()))

#AB = [tuple(map(int, input().split())) for i in range(M)]

#丸暗記。隣接リストの初期化
graph = [[] for _ in range(N)]

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

print(uf.group_count()-1)

Submission status: Runtime Error

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 same(self, x, y):
        return self.find(x) == self.find(y)
    
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=sum([1 for i in uf.parents if i==-1])
print(ans)

Submission status: Runtime Error

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())
AB=[list(map(int,input().split())) for i in range(M)]

uf = UnionFind(N)
for a,b in AB:
    uf.union(a,b)

print(uf.group_count() - 1)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def union(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.find(a), self.find(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, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.find(a) == self.find(b)

    def find(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.find(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.find(a)]

    def groups(self):
        find_buf = [self.find(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[find_buf[i]].append(i)
        return [r for r in result if r != []]

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

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

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

Submission status: Runtime Error

Solution code:
'''
Created on 2020/09/26

@author: harurun
'''
#UnionFind(要素数)で初期化
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        #parents 各要素の親番号を格納するリストを返す

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

    #要素xが属するグループのサイズ
    def size(self, x):
        return -self.parents[self.find(x)]

    #要素xとyが同じグループに属するかどうか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    #要素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 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():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N,M=map(int,pin().split())
  ans=0
  uf=UnionFind(N)
  for i in range(M):
    A,B=map(int,pin().split())
    uf.union(A, B)
  print(uf.group_count()-1)
  return 
main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
ab = [0] * M
for i in range(M):
    ab[i] = list(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):
    uf.union(ab[i][0], ab[i][1])

print(uf.group_count() - 1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import connected_components
N,M = map(int, input().split())
A = [-1 for i in range(M)]
B = [-1 for i in range(M)]

mat = np.zeros((N,N),dtype=np.uint8)

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

for i in range(M):
    mat[A[i]-1][B[i]-1] = 1
    mat[B[i]-1][A[i]-1] = 1


n, labels = connected_components(mat)
print(n-1)

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
def go(v):
    global used, g
    used[v] = True
    for i in range(len(g[v])):
        if used[g[v][i]] == False:
            go(g[v][i])
def solve():
    n, m = map(int, input().split())
    ans = 0
    global g, used
    g = [[] for i in range(n + 1)]
    used = [False for i in range(n + 1)]
    for i in range(m):
        x, y = map(int, input().split())
        g[x].append(y)
        g[y].append(x)
    for i in range(1, n + 1):
        if used[i] == False:
            ans += 1
            go(i)
    print(ans - 1)
t = 1
while t > 0:
    solve()
    t -= 1

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# from typing import *

import atcoder.dsu


# def solve(N: int, M: int, A: List[int], B: List[int]) -> int:
def solve(N, M, A, B):
    dsu = atcoder.dsu.DSU(N)
    for i in range(M):
        dsu.merge(A[i] - 1, B[i] - 1)
    num_groups = len(dsu.groups())
    return num_groups - 1


# generated by online-judge-template-generator v4.7.1 (https://github.com/online-judge-tools/template-generator)
def main():
    N, M = map(int, input().split())
    A = [None for _ in range(M)]
    B = [None for _ in range(M)]
    for i in range(M):
        A[i], B[i] = map(int, input().split())
    b = solve(N, M, A, B)
    print(b)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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 _ in range(M):
  a,b = map(int,input().split())
  uf.union(a,b)
  
print(uf.group_count() - 1)

Submission status: Runtime Error

Solution code:
class unionfind():
    def __init__(self, n):
        self.parents = [-1 for i in range(n)]
    
    def find(self, a):
        if self.parents[a] < 0:
            return a
        self.parents[a] = self.find(a)
        return self.parents[a]

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self):
        return len(list(filter(lambda x: x < 0, self.parents))) - 1

n, m = map(int, input().split())
uf = unionfind(n)
for i in range(m):
    tmp = list(map(int, input().split()))
    uf.union(tmp[0] - 1, tmp[1] - 1)

print(uf.size())

Submission status: Runtime Error

Solution code:
import math
import collections
import itertools
import copy

def YesNo(Bool):
    if(Bool):
        print("YES")
    else:
        print("NO")
    return

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

    N,M=map(int,input().split())
    A=[0]*M
    B=[0]*M

    uf = UnionFind(N)
    for i in range(M):
        A[i],B[i]=map(int,input().split())
        uf.union(A[i], B[i])
        
    for i in range(N):
        uf.find(i)
        
    cnt=uf.group_count()

    print(cnt-1)

resolve()

Submission status: Runtime Error

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 _ in range(m):
  a,b = map(int,input().split())
  uf.union(a,b)
print(uf.group_count()-1)