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:
n,m = map(int, input().split())
loadList = []
loadList.append(load)
for i in range(m):
  loadList.append(list(map(int,input().split())))

cityGroupList = []
cityGroup = []
cityGroup.append(loadList[0][0])
cityGroup.append(loadList[0][1])
cityGroupList.append(cityGroup)

for oneLoad in loadList:
  isAdded = False
  for oneCityGroup in cityGroupList:
      if oneLoad[0] in oneCityGroup:
        oneCityGroup.append(oneLoad[1])
        isAdded = True
        break
      if oneLoad[1] in oneCityGroup:
        oneCityGroup.append(oneLoad[0])
        isAdded = True
        break
  if not isAdded:  
    newCityyGroup = []
    newCityyGroup.append(loadList[0][0])
    newCityyGroup.append(loadList[0][1])
    cityGroupList.append(newCityyGroup)
    isAdded = False

print(len(cityGroupList))

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=[]
for i in range(N):
    a=int(input())
    A.append(a)

def segfunc(x, y):
    return max(x,y)
ide_ele =0

class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
Ma=max(A)
Tree=[0]*(Ma+1)
seg = SegTree(Tree, segfunc, ide_ele)
ans=0
for i in range(N):
    a=A[i]
    l=max(0,a-K)
    r=min(a+K,Ma)
    Ans=seg.query(l,r+1)
    seg.update(a, Ans+1)
    ans=max(ans,Ans+1)
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
ans = N
V = [i for i in range(N)]
inp = []
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

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

cities = np.zeros((N, N))

for i in range(M):
    i1, i2 = map(int, input().split())
    cities[i1-1][i2-1] = 1
    cities[i2-1][i1-1] = 1
#     print(cities)
    
# print(cities)

n, lasbel = connected_components(cities)
print(n-1)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M= map(int, input().split())
listA=np.zeros((N,N))
for _ in range(M):
  a, b=map(int, input().split())
  listA[a-1][b-1]+=1
#print(listA)
a = np.sum(listA, axis=0)
#print(a)
sum=-1
for i in a:
  if i == 0:
    sum+=1
print(sum)

Submission status: Runtime Error

Solution code:
def s(way):
    global w
    w2 =[]
    for i in way:
        c[i] = 1
        for j in w[i]:
            if c[j] == 0:
                w2.append(i)
            if not w2 ==[]:
                s(w2)


n,m = map(int,input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
w = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    w[a[i]-1].append(b[i]-1)
    w[b[i]-1].append(a[i]-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        s(w[i])

print(ans)

Submission status: Runtime Error

Solution code:
import copy
def check_root(root,num):

  if(root[num-1]==num):
    return num
  else:
    return check_root(root,root[num-1])
  
def reset_root(root):
  new_root = copy.copy(root)
  for i in range(len(root)):
    new_root[i] = check_root(root,i)
  return new_root

def connect_root(root,A,B):
  if root.count(A) < root.count(B):
    root[A] = B
  else:
    root[B] = A
  #reset_root(root)
  return root

def count_root(root):
  root_num = []
  for i in range(len(root)):
    flag = 0
    for j in range(len(root_num)):
      if ( root[i]==root_num[j]):
        flag=1
    if(flag==0):
      root_num.append(root[i])

  return len(root_num)
  

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

load = [list(map(int,input().split())) for _ in range(M)]

root =[]
for i in range(N):
  root.append(i+1)
  

for i in range(M):
  root_A =check_root(root,load[i][0])
  root_B =check_root(root,load[i][1])
  if not (root_A==root_B):
    connect_root(root,root_A,root_B)

root = reset_root(root)
print(count_root(root)-1)

Submission status: Runtime Error

Solution code:
NM = list(map(int, input().split()))
N = NM[0]
M = NM[1]

xy = [map(int, input().split()) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

group = []
for i in range(M):
    index = -1
    bo = True
    for j in range(len(group)):
        if x[i] in group[j] or y[i] in group[j]:
            if my_index(group[j], x[i]) != -1:
                index = group.index(x[i])
            else:
                index = group.index(y[i])
            bo = False
    if bo:
        group.append([x[i], y[i]])
    else:
        group[index].append(x[i])
        group[index].append(y[i])

NOs = []
for i in range(N):
    bo = True
    for j in range(len(group)):
        if i in group[j]:
            bo = False
    if bo:
        NOs.append(i)

print(len(group)-1 + len(NOs))

Submission status: Runtime Error

Solution code:
def inclusive_index(lst, purpose):
    for i, e in enumerate(lst):
        if purpose in e: return i

N, M = map(int,input().split())
lst = [str(i+1) for i in range(N)]

for _ in range(M):
    A, B =  input().split()
    a = inclusive_index(lst, A)
    b = inclusive_index(lst, B)
    lst[a] = lst[a] + lst[b]
    del lst[b]

print(len(lst)-1)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

import numpy as np


def main():
    n_num, m_num = map(int, input().split())
    road = np.zeros((n_num, n_num), dtype='int32')

    for _ in range(m_num):
        a, b = map(int, input().split())
        if a > b:
            a, b = b, a
        road[a-1][b-1] = 1

    city_info = np.zeros(n_num, dtype='int32')
    land_city = 0

    def move(a, b):
        if a > b:
            a, b = b, a
        if road[a-1][b-1] == 1:
            return 1
        else:
            return 0

    def recr(c):
        city_info[c] = 1
        for n in range(n_num):
            if city_info[n] == 0:
                if move(c, n) == 1:
                    recr(n)

    for n in range(n_num):
        if city_info[n] == 0:
            land_city += 1
            recr(n)

    print(land_city - 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math

n, M= map(int,input().split())
#AB=[]
#N = int(input())
#C = input()
parents = [-1] * n

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

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

    if x == y:
        return

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

    parents[x] += parents[y]
    parents[y] = x

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

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

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

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

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

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

def __str__():
    return '\n'.join('{}: {}'.format(r, members(r)) for r in roots())
 
C = []
for i in range(M):
    A, B = map(int,input().split())
    union(A,B)
    '''
    c = 0
    for p in C:
        if A in p:
            c = 1
            p.add(B)
        elif B in p:
            c = 1
            p.add(A)
    if c != 1:
        C.append(set([A,B]))
    '''
print(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())

    
from sys import stdin
imput = stdin.readline
n,m = map(int, input().split())  # 3個の数字の入力を受け取る
uf = UnionFind(n)
#print(uf.parents)

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

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:
#   The road data needs to be completely sorted so we don't get two disparate groups
#   suddenly being joined.
#   Each road either creates a new group or extends an existing one.
#   Use array GROUP for this purpose, all initialized to None.
#   After processing all roads, do a linear scan to count the Nones. We will already
#   know how many groups there are.
#   If there are 6 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

import sys
IN = sys.stdin

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in IN.readline().split()]
# Read A (details of roads) and sort each pair and then the whole list.
A = []
for line in IN.readlines():
    a, b = line.split()
    a, b = int(a), int(b)
    a, b = sorted([a,b])
    A.append((a,b))
A.sort()
# Initialise G (the group to which each ciy belongs). We use indices 1..N.
GROUP = [None for _ in range(N+1)]
# G is the most recent group number. Increment before assigning a new group.
G = 0

# Process each road.
for a,b in A:
    if GROUP[a] and GROUP[b]:
        # I believe this should not logically happen.
        print("Logical error")
        exit(1)
    elif GROUP[a]:
        GROUP[b] = GROUP[a]
    elif GROUP[b]:
        GROUP[a] = GROUP[b]
    else:
        # Neither has a group; we start a new one.
        G += 1
        GROUP[a] = G
        GROUP[b] = G

# Linear scan to count what we have. Ignore index 1.
num_nones = 0
for i in range(1,N+1):
    if GROUP[i] == None:
        num_nones += 1

# Get the answer.
answer = (G-1) + num_nones

print(answer)

Submission status: Runtime Error

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

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

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

    def groups(self):
        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 [r for r in result if r != []]# N = int(input())

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

dsu = DSU(N)

for _ in range(M):
    A_M, B_M = tuple(map(int, input().split()))
    leader_A_M = dsu.leader(A_M)
    leader_B_M = dsu.leader(B_M)
    dsu.merge(leader_A_M, leader_B_M)


# print(dsu.groups())
print(len(dsu.groups()) - 1)

Submission status: Runtime Error

Solution code:
class UnionFind:
    pairs = {}
    def __init__(self, n):
        for i in range(n):
            self.pairs[i] = i

    def set(self, s, t):
        if s in self.pairs and self.pairs[s] != s:
            self.pairs[t] = s
        else:
            self.pairs[s] = t

    def root(self, x):
        if self.pairs[x] == x:
            return x
        self.pairs[x] = self.root(self.pairs[x])
        return self.pairs[x]

def main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    for i in range(m):
        s, t = map(int,input().split())
        uf.set(s - 1, t - 1)
#    print(uf.pairs)
    root = []
    for i in range(n):
        root.append(uf.root(i))
 #       print(i, uf.root(i))
    single_root = set(root)

    print(len(single_root)-1)
main()

Submission status: Runtime Error

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

N = a[0]
M = a[1]

cities = [0] * N
roads = []

lands = {}
for i in range(M):
    a = list(map(int,input().split()))
    roads.append([a[0], a[1]])

for r in roads:
    if cities[r[0]-1] == 0:
        cities[r[0]-1] = r[0]
        lands[r[0]-1] = [r[0]]
    
    if cities[r[1]-1] == 0:
        cities[r[1]-1] = r[0]
        lands[r[0]-1].append(r[1])
    else:
        for i in range(len(lands[r[1]-1])):
            cities[i] = r[0]
        lands[r[0]-1].extend(lands[r[1]-1])


#print(cities)
#print(cities)
#print(lands)
found = {}
zero_count = 0
for i in range(N):
    if cities[i] != 0:
        found[cities[i]] = 1
    else:
        zero_count += 1

print(len(found) - 1 + zero_count)

Submission status: Runtime Error

Solution code:
def s(way):
    global w
    w2 =[]
    for i in way:

        for j in w[i]:
            if c[j] == 0:

                w2.append(i)
        c[i] = 1
        if not w2 ==[]:
            s(w2)


n,m = map(int,input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
w = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    w[a[i]-1].append(b[i]-1)
    w[b[i]-1].append(a[i]-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        s(w[i])

print(ans)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit

def Search(n):
  L[n-1] = 1
  for i in R[n]:
    if L[i-1] == 0:
      Search(i)

setrecursionlimit(200000)
N, M = map(int, input().split())
L = [1] * N
R = {}
ans = -1
for i in range(M):
  A, B = map(int, input().split())
  if A not in R:
    R[A] = set()
  if B not in R:
    R[B] = set()
  R[A].add(B)
  R[B].add(A)
  L[A-1] = 0
  L[B-1] = 0
for i in range(N):
  if L[i] == 1:
    ans += 1
    R[i+1] = set()
    if i == 0:
      R[i+1].add(2)
      R[2].add(i+1)
    else:
      R[i+1].add(1)
      R[1].add(i+1)
    L[i] = 0
while sum(L) != N:
  ans += 1
  Search(L.index(0) + 1)
print(ans)

Submission status: Runtime Error

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

N = a[0]
M = a[1]

cities = [0] * N
roads = []

lands = {}
for i in range(M):
    a = list(map(int,input().split()))
    roads.append([a[0], a[1]])

for r in roads:
    if cities[r[0]-1] == 0:
        cities[r[0]-1] = r[0]
        lands[r[0]-1] = [r[0]]
    
    if cities[r[1]-1] == 0:
        cities[r[1]-1] = r[0]
        lands[r[0]-1].append(r[1])
    else:
        for i in range(len(lands[r[1]-1])):
            cities[i] = r[0]
        lands[r[0]-1].extend(lands[r[1]-1])


#print(cities)
print(cities)
print(lands)
found = {}
zero_count = 0
for i in range(N):
    if cities[i] != 0:
        found[cities[i]] = 1
    else:
        zero_count += 1

print(len(found) - 1 + zero_count)

Submission status: Runtime Error

Solution code:
def Search(n):
  L[n-1] = 1
  for i in R[n]:
    if L[i-1] == 0:
      Search(i)

N, M = map(int, input().split())
L = [1] * N
R = {}
ans = -1
for i in range(M):
  A, B = map(int, input().split())
  if A not in R:
    R[A] = set()
  if B not in R:
    R[B] = set()
  R[A].add(B)
  R[B].add(A)
  L[A-1] = 0
  L[B-1] = 0
for i in range(N):
  if L[i] == 1:
    ans += 1
    R[i+1] = set()
    if i == 0:
      R[i+1].add(2)
      R[2].add(i+1)
    else:
      R[i+1].add(1)
      R[1].add(i+1)
    L[i] = 0
while sum(L) != N:
  ans += 1
  Search(L.index(0) + 1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    n_num, m_num = map(int, input().split())
    road = np.zeros((n_num, n_num), dtype='int32')

    for _ in range(m_num):
        a, b = map(int, input().split())
        if a > b:
            a, b = b, a
        road[a-1][b-1] = 1

    city_info = np.zeros(n_num, dtype='int32')
    land_city = 0

    def move(a, b):
        if a > b:
            a, b = b, a
        if road[a-1][b-1] == 1:
            return 1
        else:
            return 0

    def recr(c):
        city_info[c] = 1
        for n in range(n_num):
            if city_info[n] == 0:
                if move(c, n) == 1:
                    recr(n)

    for n in range(n_num):
        if city_info[n] == 0:
            land_city += 1
            recr(n)

    print(land_city - 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # x の根を返す
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
            return self.parent[x]

    def unite(self, x, y):  # x, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

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

    def group_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.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()}

#a = [i+1 for i in range(n)]
d = UnionFind(n)

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

print(d.group_count()-1)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
cnt = [1]*n
for i in range(m):
    a,b = map(int, input().split())
    cnt[a] = 0
    cnt[b] = 0
print(sum(cnt))

Submission status: Runtime Error

Solution code:

def MII(): return map(int, input().split())
def MSI(): return map(str, input().split())

n,m=MII()
groups=[["1"]]
group_set=set(["1"])

for i in range(m):
    a,b=MSI()
    a_place=0
    b_place=0
    tmp=[]
    if a in group_set:
        if b in group_set:
            for j in range(len(groups)):
                if a in groups[j]:
                    a_place=j
                elif b in groups[j]:
                    b_place=j
            tmp=groups[b_place]
            groups[a_place]+=tmp
            del groups[b_place]
        else:
            for group in groups:
                if a in group:
                    group+=[b]
                    group_set.add(b)
                    continue
    elif b in group_set:
        for group in groups:
            if b in group:
                group+=[a]
                group_set.add(a)
                continue
    else:
        groups+=[[a,b]]
        group_set.add(a)
        group_set.add(b)

print(len(groups)+(n-len(group_set))-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−1, b−1)
print(uf.group_count() - 1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
n = list(i+1 for i in range(N))
for _ in range(M):
    A, B = map(int, input().split())
    n[A] = 0
    n[B] = 0
n = set(n)
print(len(n)-1)

Submission status: Runtime Error

Solution code:
""" C
"""
import sys
import math
from functools import reduce
from bisect import bisect_left

def readString():
    return sys.stdin.readline()

def readInteger():
    return int(readString())

def readStringSet(n):
    return sys.stdin.readline().split(" ")[:n]

def readIntegerSet(n):
    return list(map(int, readStringSet(n)))

def readIntegerMatrix(n, m):
    return reduce(lambda acc, _: acc + [readIntegerSet(m)], range(0, n), [])

def _break(AB):
    result = [1]
    n = 2
    while n < AB+1:
        while (AB / n).is_integer():
            AB = int(AB/n)
            result.append(n)

        if AB == 1:
            break

        n += 1

    return result

def main(N, M, AB):
    groups = []
    vs = {}

    for A, B in AB:
        g_has_A = [i for i in range(len(groups)) if A in groups[i]]
        g_has_B = [i for i in range(len(groups)) if B in groups[i]]

        # AもBも持つgroupがあったら、なにもしない
        if len(g_has_A) == 1 and len(g_has_B) == 1 \
            and g_has_A[0] == g_has_B[0]:
            pass
        # Aを持つgroupとBを持つグループが分かれていたら、連結する
        elif len(g_has_A) == 1 and len(g_has_B) == 1 \
            and g_has_A[0] != g_has_B[0]:
            groups[g_has_A[0]] += groups[g_has_B[0]]
            groups.pop(g_has_B[0])
        # 片方を持つgroupだけがあった場合は、そこにもう一方を加える
        elif len(g_has_A) == 1:
            groups[g_has_A[0]][B] = B
        elif len(g_has_B) == 1:
            groups[g_has_B[0]][A] = A
        # どちらも既存groupになければ、groupを加える
        else:
            groups.append({A:A, B:B})

        vs[A] = A
        vs[B] = B

    return len(groups) + (N-len(vs.keys())) -1

if __name__ == "__main__":
    _N, _M = readIntegerSet(2)
    _AB = readIntegerMatrix(_M, 2)

    print(main(_N, _M, _AB))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)

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(a[i],b[i])

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:
def s(way):
    global w
    w2 =[]
    for i in way:

        for j in w[i]:
            if c[j] == 0:

                w2.append(i)
            if not w2 ==[]:
                s(w2)
        c[i] = 1

n,m = map(int,input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
w = [[] for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    w[a[i]-1].append(b[i]-1)
    w[b[i]-1].append(a[i]-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        ans += 1
        s(w[i])

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
AB=list()
memo=[False]*N
G=defaultdict(list)
def dfs(G,i):
    memo[i]=True
    for j in G[i]:
        if memo[j]==False:
            dfs(G,j)
count=0
for i in range(M):
    AB=list(map(int,input().split()))
    G[AB[1]-1].append(AB[0]-1)
    G[AB[0]-1].append(AB[1]-1)
for i in range(N):
    if memo[i]==False:
        dfs(G,i)
        count+=1
print(count-1)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
for i in range(n):
    a, b = map(int, input().split())

print(n - m - 1)

Submission status: Runtime Error

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

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

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

for i in range(n-1,-1,-1):
    flg = True
    change_list = []
    idx = i
    while(flg):
        if par[idx] == idx:
            flg = False
            cur_p = idx
        else:
            p = par[idx]
            change_list.append(p)
            idx = par[p]
    for j in range(len(change_list)):
        idx = change_list[j]
        par[idx] = cur_p

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

Submission status: Runtime Error

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

tree = {}
for i in range(M):
  a, b = list(map(int, input().split()))

  if a not in tree:
    for t in tree:
      if a in tree[t]:
        tree[t].append(b)
      else:
        tree[a] = [a,b]
        break
    if len(tree) == 0:
      tree[a] = [a,b]
  else:
      tree[a].append(b)
#print(tree)

sum_ = 0
for t in tree:
  sum_ += len(tree[t])

print(N -sum_ + len(tree) - 1)