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: Wrong Answer

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

conditions = []
cities = [0] * N

for i in range(M):
    a, b = list(map(int, input().split()))
    cities[a - 1] = 1
    cities[b - 1] = 1

print(len(list(filter(lambda x: x == 0, cities))))

Submission status: Wrong Answer

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

roop=[[]]*(N+1)
roop_con=[0]*(N+1)
check=[-1]*(N+1)
for i in range(M):
    if(check[A[i]] and check[B[i]]):
        if(A[i]<B[i]):
            check[A[i]]=A[i]
            check[B[i]]=A[i]
            roop[A[i]].append(B[i])
            #print(check[A[i]])
            roop_con[check[A[i]]]=1
        else:
            check[A[i]]=B[i]
            check[B[i]]=B[i]
            roop[B[i]].append(A[i])
            roop_con[check[B[i]]]=1

    elif(check[A[i]]!=-1):
        roop[check[A[i]]].append(roop[check[B[i]]])
        roop_con[check[A[i]]]=1
    elif(check[B[i]]!=-1):
        roop[check[B[i]]].append(roop[check[A[i]]])
        roop_con[check[A[i]]]=1
print(sum(roop_con))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())

par = [i for i in range(N+1)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    
for i in range(M):
  a,b=map(int, input().split())
  unite(max(a,b),min(a,b))

par=set(par)

print(len(par)-2)

Submission status: Wrong Answer

Solution code:
import collections

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

N_list = list(range(1,N+1))

for i in range(M):
  A,B=map(int,input().split())
  if(A in N_list):
    N_list[A-1]=0
  if(B in N_list):
    N_list[B-1]=0

c=collections.Counter(N_list)
print(len(c)-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    A[i], B[i] = map(int, input().split())
print(N-M-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

adjacency_list = [[] for i in range(N)]
for i in range(M):
    tmp = list(map(int, input().split()))
    adjacency_list[tmp[0] - 1].append(tmp[1] - 1)
    adjacency_list[tmp[1] - 1].append(tmp[0] - 1)
con_component = 0
# 接続確認
visited_set = set(range(N))

while visited_set:
    con_component += 1
    ind = visited_set.pop()
    # print(ind)
    for adjacency in adjacency_list[ind]:
        # print("aa",adjacency)
        if adjacency in visited_set:
            visited_set.remove(adjacency)

print(con_component-1)

Submission status: Wrong Answer

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

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

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

print(UF.r)
print(ans-1)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

n,m = ip()
graph = {i:[] for i in range(1,n+1)}
for i in range(m):
    a,b = ip()
    graph[a].append(b)
    graph[b].append(a)
print((n-1)-m)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
for i in range(M):
  A,B = map(int, input().split())
print(N-M*2)

Submission status: Wrong Answer

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

    root = []
    for i in range(n):
        root.append(uf.root(i))

    single_root = set(root)

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

Submission status: Wrong Answer

Solution code:
def search_list_road(list_road, list_search_point):
    index = [-1]

    for i in list_search_point:
        for j, road in enumerate(list_road):
            if i in road:
                if index[0] == -1:
                    index[0] = j
                else:
                    index.append(j)
                    return index

    return index

def main():
    N, M = map(int, input().split())
    list_road = []

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

        if index[0] == -1:
            add_set = set()
            add_set.add(A)
            add_set.add(B)
            list_road.append(add_set)
        elif len(index) == 1:
            list_road[index[0]].add(A)
            list_road[index[0]].add(B)
        else:
            list_road[index[0]] = list_road[index[0]] | list_road[index[1]]
            list_road.pop(index[1])

    answer = 0
    for i, road in enumerate(list_road):
        if i != 0:
            answer = answer + 1
            list_road[0] = list_road[0] | road
            list_road.pop(i)
    
    num_cover_city = len(list_road[0])
    print(answer + N - num_cover_city)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

graph = [[] for _ in range(N)]
for i in range(M):
  graph[x[i]-1].append(y[i]-1)
seen = [0 for _ in range(N)]

def dfs(i):
  stack = []
  stack.append(i)
  while stack:
    tmp = stack.pop()
    seen[tmp] = 1
    stack.extend(graph[tmp])

count = -1
for i in range(N):
  if not seen[i]:
    dfs(i)
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
v, e = map(int,input().split())
par = [i for i in range(v+1)]

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y

for i in range(e):
  a, b = map(int, input().split())
  unite(b, a)
  
print(len(set(par))-2)

Submission status: Wrong Answer

Solution code:
# cook your dish here
s=[int(i) for i in input().strip().split()]
n=s[0]
m=s[1]
l=[]
for i in range(0,m):
    s=[int(i) for i in input().strip().split()]
    l.append(s[0])
    l.append(s[1])
p=set(l)
print(n-len(p))

Submission status: Wrong Answer

Solution code:
from scipy.special import comb

N, M = [int(i) for i in input().split()]
AB = []

for i in range(M):
  AB.append([int(i) for i in input().split()])

print(int(comb(N, 2)) - M)

Submission status: Wrong Answer

Solution code:
nums = input().split(" ")
N = int(nums[0])
M = int(nums[1])

a = input().split(" ")
towns = [set(a)]

for i in range(M-1):
  a = input().split(" ")

  for i in range(len(towns)):
    if a[0] in towns[i] or a[1] in towns[i]:
      towns[i] = towns[i]|set(a)
    else:
      towns.append(set(a))
      
ans = len(towns)

for i in range(len(towns)-1):
  for j in range(i+1, len(towns)):
    b = towns[i]&towns[j]
    if len(b) != 0:
      ans -= 1
print(ans-1)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
def pow_k(x, n):
 
    if n == 0:
        return 1
 
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
 
    return K * x
def main():  #startline-------------------------------------------
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    un = UnionFind(n)
    ans = 0
    for i in range(m):
        un.union(ab[i][0], ab[i][1])
    for i in range(2, n + 1):
        if un.findroot(i) != 1:
            ans += 1
            un.union(1,i)
    print(ans)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
n = list(map(int, input().split()))
x = [list(map(int, input().split())) for i in range(n[1])]
s = n[0]-1
l = len(x)
print(s - l)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

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

print(N-1-M)

Submission status: Wrong Answer

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

cnt = [0]*n

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

ans = 0
for i in range(n):
    if cnt[i] == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())

A = [-1 for _ in range(N + 1)]

def search(ls, n):
  while ls[n] > 0:
    n = ls[n]
  return n

for i in range(M):
  a, b = map(int, input().split())
  aa = search(A, a)
  bb = search(A, b)
  if aa != bb:
    A[b] = aa
    
group = -1
for i in range(1, N + 1):
  if A[i] == -1:
    group += 1
    
print(group)

Submission status: Wrong Answer

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

c = len(set(l))


print(n-1 - c)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from networkx import *

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

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

m2 = len(max(connected_components(G), key=len))

print(n - m2)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
ans = 0
for i in range(m):
  x,y = map(int,input().split())
  a.append(x)
  a.append(y)
a = list(set(a))
for i in range(len(a)):
  if i == 0:
    if a[i] != 1:
      ans += 1
  else:
    if a[i] != a[i-1]+1:
      ans += 1
ans += n - a[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n,m=map(int,input().split())
r=[0]*n
c=0
for i in range (m):
  a,b=map(int,input().split())
  r[a-1]+=1
  r[b-1]+=1
ma = max(r)
if ma>=n-1:
  print(0)
elif all(i>=2 for i in r):
  print(0)
else:
  for i in r:
    if i<2:
      c+=2-i
  print(min(n-1-ma,2*n-c))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n,m=map(int,input().split())
path=defaultdict(list)
for i in range(m):
    a,b=map(int,input().split())
    path[a].append(b)
visited=set()
cnt=0
for i in range(1,n+1):
    if i not in visited: cnt+=1
    visited.add(i)
    lis=path[i]
    for j in lis: visited.add(j)
print(max(cnt-1,0))

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
list = []
for i in range(1,n+1):
  list.append(i)
for i in range(m):
  a, b = map(int,input().split())
  list[a-1] = min(list[a-1],list[b-1])
  list[b-1] = min(list[a-1],list[b-1])
ans = len(set(list))-1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
count=0
for i in range(M):
  A[i], B[i] = map(int, input().split())
for i in range(1,N+1):
  if (i in A) or (i in B):
    count+=1
Ans = N-count
print(Ans)

Submission status: Wrong Answer

Solution code:

def main():
    N, M = map(int, input().split())
    for i in range(M):
        A, B = map(int, input().split())

    print(N-1-M)


main()

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
a = [0]*m
b = [0]*m
for i in range(m):
    a[i], b[i] = map(int, input().split())
#島の数引く1
print(n-m-1)
# ns = list(range(1,n+1))

# for i in range(m):
#     ns[a[i]-1] = 0
#     ns[b[i]-1] = 0

# count = 0

# for i in range(n):
#     if ns[i] != 0:
#         count += 1

# print(count)

Submission status: Wrong Answer

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

    if n - 1 <= m:
        print(0)
    else:
        print(n - 1 - m)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
  par = None
  
  def __init__(self, n):
    self.par = [0] * n
    
  def root(self, x):
    if(self.par[x] == 0):
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    if(self.root(x) != self.root(y)):
      self.par[x] = self.root(y)
      
  def same(self, x, y):
    return self.root(x) == self.root(y)
  
N, M = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(M):
  A, B = list(map(int, input().split()))
  UF.unite(A - 1, B - 1) 
ans = 0
for i in range(N):
  ans += (UF.par[i] == 0)
print(ans - 1)

Submission status: Wrong Answer

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


print(n-m-1)

Submission status: Wrong Answer

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

roads = 0
if N == 2:
    if M == 1:
        print("0")
    else:
        print("1")

if N >= 3:
    roads = N - (M+1)
    print(roads)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


set_count = 0
bubun = []
bubun.append(ab[0])
while True:
'''

print(n - m - 1)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
nums = [list(map(int, input().split())) for x in range(M)]

if len (nums) == N:
    print(0)
elif len(nums) < N:
    print(N-M-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

R = [list(map(int, input().split())) for i in range(m)]

print(n-m-1)

Submission status: Wrong Answer

Solution code:
def run(n_m, an_bn):
    '''

    '''
    if n_m[0] - 1 <= len(an_bn):
        print(0)
    else:
        print(n_m[0] - 1 - len(an_bn))






if __name__ == '__main__':
    n_m = list(map(int, input().split()))
    an_bn = list(map(int, input().split()) for _ in range(n_m[1]))

    run(n_m, an_bn)

Submission status: Wrong Answer

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

city = []
for i in range(m):
    a, b = map(int, input().split())
    city.append(a)
    city.append(b)
city = list(set(city))
print(n-(len(city)))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
L=[0]*N

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

num = L.count(1)
print(N-num)

Submission status: Wrong Answer

Solution code:
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    numbers=[]
    n,m = map(int,input().split())
    numbers=[list(map(int,input().split())) for _ in range(m)]
    print(n-m-1)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
A, B = map(int, input().split())
print(A - B - 1)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
i=0
while i < m:
    i += 1
    a, b = map(int, input().split())

print(n-1-m)

Submission status: Wrong Answer

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

a,b=map(int,input().split())
n=[list(map(int,input().split())) for i in range(b)]


q=[i for i in range(1,a+1)]

uf=UnionFind(a+1)
for i in range(b):
    uf.union(n[i][0],n[i][1])

ans=0
for i in q:
    if uf.same(1,i):
        continue
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
# 2020/09/26
# ACL Beginner Contest - C

# Union Find
# Define List
pl = list()

def root(in_root):
    if pl[in_root] == in_root:
        return in_root
    else:
        pl[in_root] = root(pl[in_root])
        return pl[in_root]

def isSame(in_a, in_b):
    if root(pl[in_a]) == root(pl[in_b]):
        return True
    else:
        return False

def unite(in_a, in_b):
    wk_a = root(in_a)
    wk_b = root(in_b)
    if wk_a == wk_b:
        return False
    else:
        pl[in_b] = in_a

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

# Init List
for i in range(n+1):
    pl.append(i)

# Input a, b
for i in range(m):
    a, b = map(int,input().split())
    wa = min(a, b)
    wb = max(a, b)
    unite(wa, wb)

# Count
ans = 0
for i in range(1, n+1):
    if pl[i] == i:
        ans = ans + 1

# Output
print(ans-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = []
for i in range(M):
    A.append(list(map(int, input().split())))
    
R = (N - 1) - M
if R < 0:
  R = 0
  
print(R)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
na = list(range(1, N))
nb = list(range(2, N+1))
A = []
B = []
for _ in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ans_a = len(set(na)^set(A))
ans_b = len(set(nb)^set(B))
print(min(ans_a, ans_b))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for j in range(m):
    a, b = map(int, input().split())
    list[b] = list[a]
l = set(list)
print(len(l)-2)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
from sys import stdin


def makeConnected(n, connections):
    l = list(zip(*connections))
    d = [1] * len(connections)
    a = csr_matrix((d, (l[0], l[1])), (n, n))
    return connected_components(a, return_labels=0)


def main():
    input = lambda: stdin.readline()[:-1]
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]

    ab = [[a - 1, b - 1] for a, b in AB]
    ans = makeConnected(N, ab)
    print(ans)


main()

Submission status: Wrong Answer

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

print(n-1-m)

Submission status: Wrong Answer

Solution code:
# スペース区切りの整数の入力
N, M = map(int, input().split())
C = []
for i in range(M):
    #内包表記
    A = [int(i) for i in input().split()]
    C.append(A)
counts = 0
for p in range(M):
   if p not in C:
    counts += 1
    C.append(p)
print(counts)

Submission status: Wrong Answer

Solution code:
def run(n_m, an_bn):
    '''

    '''
    # print(n_m)
    # print([list(i) for i in an_bn])
    # print(len(an_bn))
    if n_m[0] <= len(an_bn):
        print(0)
    else:
        print(n_m[0] - 1 - len(an_bn))






if __name__ == '__main__':
    n_m = list(map(int, input().split()))
    an_bn = list(map(int, input().split()) for _ in range(n_m[1]))

    run(n_m, an_bn)

Submission status: Wrong Answer

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res
 
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
def pow_k(x, n):
 
    if n == 0:
        return 1
 
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
 
    return K * x
def main():  #startline-------------------------------------------
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(m)]
    un = UnionFind(n)
    ans = 0
    for i in range(m):
        un.union(ab[i][0], ab[i][1])
    for i in range(2,n+1):
        if not (un.same_group_or_no(n, i)):
            ans += 1
            un.union(n,i)
    print(ans)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
print(N - (M + 1))

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
x=[]
for i in range(m):
    x.append(list(map(int, input().split())))
print(n-m-1 if n-m-1>=0 else 0)

Submission status: Wrong Answer

Solution code:
n,m=[int(_) for _ in input().split()]
ab=[[int(_)-1 for _ in input().split()] for i in range(m)]
oya = [-1 for i in range(n)]
ko=[[]for i in range(n)]
for a,b in ab:
    if oya[b]==-1:
        oya[b]=a
        ko[a].append(b)
    else:
        c=oya[b]
        for d in ko[b]:
            oya[d]=a
        ko[a]=ko[a]+ko[b]
        ko[b]=[]
        oya[b]=a
# print(oya,ko)
print(oya.count(-1)-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ans = {}
cnt = 0
for i in range(m):
  a,b = map(int,input().split())
  if int(a) not in ans:
    ans[a] = 1
    cnt += 1
  if int(b) not in ans:
    ans[b] = 1
    cnt += 1
print(n-len(ans))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
alls = [i for i in range(N)]
con_cities = [[]]
for i in range(M):
    flag = 0
    a, b = map(int, input().split())
    if a in alls:
        alls.remove(a)
    if b in alls:
        alls.remove(b)
    for j in range(len(con_cities)):
        if a in con_cities[j]:
            con_cities[j].append(b)
            flag = 1
            break
        elif b in con_cities[j]:
            con_cities[j].append(a)
            flag = 1
            break
    if not flag:
        con_cities.append([a,b])
if alls:
    for n in alls:
        con_cities.append([n])

print(len(con_cities)-1)