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:
#!/usr/bin/env python

n, m = map(int, input().split())
a = [0 for _ in range(m)]
b = [0 for _ in range(m)]
for i in range(m):
    a[i], b[i] = map(int, input().split())

class UnionFind():
    def __init__(self, n): 
        self.n = n 
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def root(self, x): 
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 圧縮経路
            return self.par[x]
            # return root(par[x]) # 圧縮しない場合

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

    def unite(self, x, y): 
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: 
            return

        # par[rx] = ry # naiveな連結

        # 低い木を高い方にくっつける。
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.sizes[ry] += self.sizes[rx]
        else:
            self.par[ry] = rx
            self.sizes[rx] += self.sizes[ry]

        # rx木とry木の高さが同じならば、rx木を深くする。
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def size(self, x): 
        '''
        xが属するグループのサイズを返す
        (連結成分の大きさ)
        '''
        return self.sizes[self.root(x)]

    def connected(self):
        '''
        連結成分の数
        '''
        return len(set(self.par))

uf = UnionFind(n)
for i in range(m):
    uf.unite(a[i], b[i])

ans = n-uf.connected()
print(ans)

Submission status: Runtime Error

Solution code:
# 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?

# Solution:
#   Each road either: creates a new group; extends an existing one; or merges two
#     existing groups.
#   Use array GROUP to track the group of each city, all set to None initially.
#   Each group has a PARENT. A new group is created when two groups are merged, and
#     each group points to the new one as its parent. The new group has no parent (None).
#   After processing all roads: count the unique groups (i.e. groups with no parent) and
#     the cities with no group (i.e. they have no road).
#   If there are 6 unique groups, then 5 roads will ensure they are all connected.
#   If there are 4 Nones, then 4 roads are needed to connect them to groups.
#   Answer = (#groups - 1) + #Nones

def count(gen):
    n = 0
    for x in gen:
        if x:
            n += 1
    return n

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in input().split()]
# Initialize GROUP and PARENT.
GROUP = [None for _ in range(N+1)]
PARENT = dict()
# G is the most recent group number. Increment before assigning a new group.
G = 0

# Process each road.
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    #print(f"road: {a} {b}")
    if GROUP[a] and GROUP[b]:
        # We have a merger.
        assert GROUP[a] != GROUP[b]
        G += 1
        ##print(f"  merger - groups {GROUP[a]} and {GROUP[b]} --> {G}")
        PARENT[G] = None
        PARENT[GROUP[a]] = G
        PARENT[GROUP[b]] = G
        GROUP[a] = G
        GROUP[b] = G
    elif GROUP[a]:
        # Extend existing group.
        GROUP[b] = GROUP[a]
        ##print(f"  extend group {GROUP[a]}")
    elif GROUP[b]:
        # Extend existing group.
        GROUP[a] = GROUP[b]
        ##print(f"  extend group {GROUP[b]}")
    else:
        # Neither has a group; we start a new one.
        G += 1
        ##print(f"  new group {G}")
        PARENT[G] = None
        GROUP[a] = G
        GROUP[b] = G

##print()
##print(GROUP)
##print(PARENT)

# Count the unique groups and the isolated cities.
num_groups   = count(PARENT[x] is None for x in range(1, G+1))
num_isolated = count(GROUP[x]  is None for x in range(1, N+1))

##print(num_groups, num_isolated)

# Get the answer.
answer = (num_groups - 1) + num_isolated

print(answer)

Submission status: Runtime Error

Solution code:
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.co = n

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

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.r[x] > self.r[y]:
      x, y = y, x
    self.n[y] += self.n[x]
    self.n[x] = y
    if self.r[x] == self.r[y]:
      self.r[y] += 1
    self.co -= 1

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

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

  def set_count(self):
    return self.co
  
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)
print(uf.set_count()-1)

Submission status: Runtime Error

Solution code:
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  
  #print(r)
  #print("city_a", city_a, "city_b", city_b)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    if city_a_par == city_b_par:
      pass
    else:
      r[city_b_par] = city_a
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-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())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
print(len(uf.roots())-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())
    uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)
print(len(uf.roots())-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)

n,m=map(int,input().split())
g=[[] for i in range(10**5+10)]
for i in range(m):
  a,b=map(lambda x:int(x)-1, input().split())
  g[a].append(b)
  g[b].append(a)
chk=[-1]*n

def dfs(s,v,cnt):
  for u in g[s]:
    if u==v: continue;
    chk[u]=cnt
    dfs(u,s,cnt)

cnt=0
for i in range(n):
  if chk[i]==-1:
    chk[i]=cnt
    dfs(i,-1,cnt)
    cnt+=1
    
print(max(chk))

Submission status: Runtime Error

Solution code:
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  #print("x1", x1, "x2", x2)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    r[city_b_par] = r[city_a]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
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 Kruskal(G, V):
    """
    Gは辺と重みVは頂点の数
    """
    Uni = UnionFind(V)
    res = 0
    for x, y, cost in G:
        if not Uni.same(x, y):
            Uni.union(x, y)
            res += cost
        if Uni.size(x) == V:
            break
    print(res)
    
def main():
    V, M = MI()
    G = [LI()+[1] for i in range(M)]
    Kruskal(G, V)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * n
def find(x):
    if root[x] < 0:
        return x
    else:
        x = find(x)
        return x
    

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x
        

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

ans = len([i for i in root if i < 0]) - 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * n
def find(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find(x)
        return root[x]
    

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x
        

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

ans = len([i for i in root if i < 0]) - 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (110000)
def find(x):
    if root[x] < 0:
        return x
    else:
        root[x] = find(x)
        return root[x]
    

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

ans = 0
for i in range(1, n+1):
    if root[i]  < 0:
        ans += 1
print(ans-1)
print(root)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (110000)
def find(x):
    if root[x] >= 0:
        root[x] = find(x)
        return root[x]
    else:
        return x

def unite(x, y):
    x = find(x)
    y = find(y)
    if x != y:
        root[x] += root[y]
        root[y] = x
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

ans = 0
for i in range(1, n+1):
    if root[i]  < 0:
        ans += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.p = list(range(n))
    
    def find(self, x):
        if self.p[x] == x:  return x
        self.p[x] = self.find(self.p[x])
        return self.p[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:  self.p[x] = y

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

ans = 0
for i in range(1, N):
    if uf.find(0) != uf.find(i):
        uf.unite(0, i)
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (110000)
def find(x):
    if root[x] >= 0:
        root[x] = find(x)
        return root[x]
    else:
        return x

def unite(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        root[a] += root[b]
        root[b] = a
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

ans = 0
for i in range(1, n+1):
    if root[i]  < 0:
        ans += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (1100000)
def find(x):
    if root[x] >= 0:
        root[x] = find(x)
        return root[x]
    else:
        return x

def unite(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        root[a] += root[b]
        root[b] = a
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

ans = 0
for i in range(1, n+1):
    if root[i]  < 0:
        ans += 1
print(ans-1)
print(root)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (110000)
def find(x):
    if root[x] >= 0:
        r = find(x)
    root[x] = r
    return r

def unite(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        root[a] += root[b]
        root[b] = a
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

ans = 0
for i in range(1, n+1):
    if root[i]  < 0:
        ans += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (110000)
def find(x):
    if root[x] >= 0:
        r = find(x)
    root[x] = r
    return r

def unite(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        root[a] += root[b]
        root[b] = a
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

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
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x


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

ans = 0
for i in uf.parents:
    if i  < 0:
        ans += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

root = [-1] * (110000)
def find(x):
    if root[x] > 0:
        x = find(x)
    return x

def unite(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        root[a] += root[b]
        root[b] = a
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

ans = 0
for i in range(1, n+1):
    if root[i]  < 0:
        ans += 1
print(ans-1)

Submission status: Runtime Error

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

root = [-1] * (110000)
def find(x):
    if root[x] > 0:
        x = find(x)
    return x

def unite(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        root[a] += root[b]
        root[b] = a
        

for _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)

ans = 0
for i in range(1, n+1):
    if root[i]  < 0:
        ans += 1
print(ans-1)

Submission status: Runtime Error

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

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

def dfs(v):
    visited[v] = 1
    for i in AB[v]:
        if visited[i]:
            continue
        dfs(i)

visited = [0]*N
cnt = 0
for i in range(N):
    if visited[i]:
        continue
    dfs(i)
    cnt += 1
print(cnt-1)

Submission status: Runtime Error

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

for i in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    L[a].append(b)
    L[b].append(a)
    
def dfs(i):
    if visited[i]:
        return
    visited[i] = True
    for j in L[i]:
        if visited[j]:
            continue
        dfs(j)
        
visited = [False]*n
cnt = 0

for i in range(n):
    if visited[i]:
        continue
    dfs(i)
    cnt +=1
    
print(cnt-1)

Submission status: Runtime Error

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

for i in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    L[a].append(b)
    L[b].append(a)
    
def dfs(i):
    visited[i] = True
    for j in L[i]:
        if visited[j]:
            continue
        dfs(j)
        
visited = [False]*n
cnt = 0

for i in range(n):
    if visited[i]:
        continue
    dfs(i)
    cnt +=1
    
print(cnt-1)

Submission status: Runtime Error

Solution code:
def dfs(v):
    visited[v] = 1
    for i in AB[v]:
        if visited[i]:
            continue
        dfs(i)

def main():
    N, M = map(int, input().split())
    AB = [[] for _ in range(N)]

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

    visited = [0]*N
    cnt = 0
    for i in range(N):
        if visited[i]:
            continue
        dfs(i)
        cnt += 1
    print(cnt-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    AB = [[] for _ in range(N)]

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

    def dfs(v):
        visited[v] = 1
        for i in AB[v]:
            if visited[i]:
                continue
            dfs(i)

    visited = [0]*N
    cnt = 0
    for i in range(N):
        if visited[i]:
            continue
        dfs(i)
        cnt += 1
    print(cnt-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, M = map(int, input().split())
    AB = [[] for _ in range(N)]

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

    def dfs(v):
        if visited[v]:
            return
        visited[v] = 1
        for i in AB[v]:
            dfs(i)

    visited = [0]*N
    cnt = 0
    for i in range(N):
        if visited[i]:
            continue
        dfs(i)
        cnt += 1
    print(N-cnt)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
m,n=map(int,input().split())
par=[i for i in range(m)]
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(n):
    a,b=map(int,input().split())
    unite(a,b)

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

Submission status: Runtime Error

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

    def find(self, x) -> int:
        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) -> None:
        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) -> int:
        return -self.parents[self.find(x)]

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

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

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

    def group_count(self) -> int:
        return len(self.roots())

    def all_group_members(self) -> dict:
        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())
a=UnionFind(n)
for i in range(m):
    b,c=map(int,input().split())
    a.union(b,c)
print(a.group_count()-1)

Submission status: Runtime Error

Solution code:

n,m = map(int, raw_input())

def g(u,parent):
    if parent[u]!= u:
        parent[u] = g(parent[u], parent)
    return parent[u]
parent = {u:u for u in range(1, n+1)}
for _ in range(m):
    u,v = map(int, raw_input().split())
    pu,pv = g(u,parent), g(v,parent)
    if pu!= pv:
        parent[pu] = pv

ans = 0
for u in parent:
    if g(u,parent) == u:
        ans+=1
print ans -1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


n,m = (int(x) for x in input().split())
visited = [False for _ in xrange(n)]

graph = dict(((i,[]) for i in xrange(n)))

def dfs(node):
    if visited[node]:
        return None
    visited[node] = True
    for next_node in graph[node]:
        dfs(next_node)
    return None

for _ in xrange(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in xrange(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
visited=[0]*n
d=defaultdict(list)
def dfs(n):
    visited[n]=1
    #print(visited)
    for i in d[n]:
        if visited[i]==0:
            dfs(i)

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

r=-1
for i in range (n):
    if visited[i]==0:
        dfs(i)
        r+=1
print(r)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n, m=map(int,input().split())
visited=[False for _ in range(n)]
graph = defaultdict(list)


def dfs(node):
    visited[node]=1
    for next_node in graph[node]:
        if visited[next_node]==0:
            dfs(next_node)

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

ans = -1
for i in range(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n,m = (int(x) for x in input().split())
visited = [False for _ in range(n)]
graph = defaultdict(list)



for _ in range(m):
    u,v = (int(x)-1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(node):
    if not visited[node]:
        visited[node] = True
        for next_node in graph[node]:
            dfs(next_node)

ans = -1
for i in range(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n,m = (int(x) for x in input().split())
visited = [False for _ in range(n)]
graph = dict(((i,[]) for i in range(n)))

def dfs(node):
    if visited[node]:
        return None
    visited[node] = True
    for next_node in graph[node]:
        dfs(next_node)
    return None

for _ in range(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in range(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')


n,m = (int(x) for x in input().split())
visited = [False for _ in xrange(n)]

graph = dict(((i,[]) for i in xrange(n)))

def dfs(node):
    if visited[node]:
        return None
    visited[node] = True
    for next_node in graph[node]:
        dfs(next_node)
    return None

for _ in xrange(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in xrange(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')


n,m = (int(x) for x in input().split())
visited = [False for _ in xrange(n)]

graph = dict(((i,[]) for i in xrange(n)))

def dfs(node):
    # global visited
    if visited[node]:
        return
    visited[node] = True
    for next_node in graph[node]:
        dfs(next_node)

for i in xrange(n):
    graph[i] = []
for _ in xrange(m):
    u,v = (int(x) - 1 for x in input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = -1
for i in xrange(n):
    if not visited[i]:
        dfs(i)
        ans += 1
print(ans)