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=map(int,input().split())
lst=[]
for i in range(m):
    a,b=map(int,input().split())
    lst.append(a)
    lst.append(b)
print(n-len(set(lst)))

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

num = (a * (a-1)) //2
print(abs(num-b)-1)

Submission status: Wrong Answer

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

ans = n-m-1

print(ans)

Submission status: Wrong Answer

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

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

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



Z = A + B



c = collections.Counter(Z)

L = list(c.keys())



cn = 0

for i in range(len(O)):
    if O[i] not in L:
        cn = cn + 1
        
print(cn)

Submission status: Wrong Answer

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

par = [i for i in range(n)]
rank = [0]*n

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 False
    if rank[x]<rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

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

num=set()
for i in range(n):
    if par[i] not in num:
        num.add(par[i]) 

print(len(num)-1)

Submission status: Wrong Answer

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

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

b=list(itertools.chain.from_iterable(a))

c=set(b)
d=list(c)

print(n-len(d))

Submission status: Wrong Answer

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

a_list = []
b_list = []

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

    a_list.append(a)
    b_list.append(b)

print(n-1-m)

Submission status: Wrong Answer

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

isolated = N
for i in range(M):
  A, B = list(map(int, input().split()))
  if c[A - 1] == 0 or c[B - 1] == 0:
    isolated -= 1
  c[A-1] = 1
  c[B-1] = 1

print(isolated - 1)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
def solve(city_arr, road_arr):
    # counta = 0
    road_set = set(road_arr)
    # tmp_cities = list(road_set)
    # tmp_cities.sort()
    return len(city_arr) - len(road_set)
    # for city, road in zip(city_arr, tmp_cities):
    #     if city != road:
    #         counta += 1
    # return counta

    
if __name__ == '__main__':
    num_cities, num_roads = [int(i) for i in input().split()]
    roads = [int(i) for j in range(num_roads) for i in input().split()]
    cities = range(1, num_cities + 1)
    ans = solve(cities, roads)
    print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
    def find(self, x):
        if self.parents[x] == x:
            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
        self.parents[y] = x
N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    a,b=map(int,input().split())
    a-=1;b-=1
    uf.union(min(a,b),max(a,b))
print(len(set(uf.parents))-1)

Submission status: Wrong Answer

Solution code:
import sys,io,os
z=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
y=lambda:map(int,z().split())
n,m=y()
s={}
k={}
r=0
e=0
for i in range(m):
    a,b=y();a-=1;b-=1
    if a in k:
        if b in k:
            if k[a]!=k[b]:
                if len(s[k[a]])<len(s[k[b]]):
                    for j in s[k[a]]:k[j]=k[b]
                    s[k[b]]=s[k[b]].union(s[k[a]])
                else:
                    for j in s[k[b]]:k[j]=k[a]
                    s[k[a]]=s[k[a]].union(s[k[b]])
                e+=1
        else:
            k[b]=k[a]
            s[k[a]].add(b)
            e+=1
    else:
        if b in k:
            k[a]=k[b]
            s[k[b]].add(a)
            e+=1
        else:
            k[a]=r
            k[b]=r
            s[r]={a,b}
            r+=1
            e+=1
print(n-1-e)

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)

Submission status: Wrong Answer

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

road.sort()
d=[0]*n
d[road[0][0]]=1
count=2
for i in road:
    if d[i[0]]==0:
        d[i[0]]=count
        d[i[1]]=count
        count+=1
    else:
        d[i[1]]=d[i[0]]

p=set()
for i in range(n):
    p.add(d[i])
print(len(p)-1)

Submission status: Wrong Answer

Solution code:
def f():
    n, m = map(int,input().split())
    d = [[] for i in range(n)]
    for i in range(m):
        a, b = map(int,input().split())
        d[a-1].append(b)
        d[b-1].append(a)
    cnt = 0
    for i in range(n):
        if len(d[i]) == 0:
            cnt += 1
    
    print(cnt)
    
if __name__ == '__main__':
    f()

Submission status: Wrong Answer

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

# Union Find(From AtCoder Typical Contest 001 - B)
# 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_a] = in_b

# 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())
    unite(a, b)

# 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:
def rl():
    return [int(x) for x in input().split()]
n,m = rl()

ans = set()
for _ in range(m):
    l,r = map(int,input().split())
    ans.add(l)
    ans.add(r)
print(n-len(ans))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
con_cities = [[]]
for i in range(M):
    flag = 0
    a, b = map(int, input().split())
    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])
print(len(con_cities)-1)

Submission status: Wrong Answer

Solution code:
date = input().split()
N = int(date[0])
M = int(date[1])
c = []
for i in range(M):
  l = input().split()
  for i in l:
    if i not in c:
      c.append(i)
print(N-len(c))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
        self._size = [1]*N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_sama(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self._size[rb] += self._size[ra]
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]:
                self.rank[ra] += 1
            self._size[ra] += self._size[rb]
        self.count += 1
    def print_info(self):
        print("parent", self.parent)
        print("rank", self.rank)
        print("count", self.count)
        print("size", self._size)
    def size(self,a):
        return self._size[self.root(a)]

import sys
input = sys.stdin.readline
from collections import Counter
count = 0
N,M = map(int,input().split())
UF = UnionFind(N)
memo = []
for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    UF.unite(A,B)

c = Counter(UF.parent)
ans = len(c)-1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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

A = []
B = []

for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    A.append(a)
    B.append(b)

root = [i for i in range(N)]

def find(x):
    if root[x] != x:
        root[x] = find(root[x])
    return root[x]

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

for i in range(M):
    unite(A[i], B[i])

roots = set(root)

print(len(roots) - 1)

Submission status: Wrong Answer

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

for i in range(M):
    A_i = list(map(int, input().split()))

print(N-M-1)

Submission status: Wrong Answer

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

if m >= n or n == m+1:
    print(0)
else:
    print(n-m-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-cnt)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
town = set()
for i in range(M):
    a,b = list(map(int,input().split()))
    town.add(a)
    town.add(b)
    
sorted(town)
print(N-len(town))

Submission status: Wrong Answer

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

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


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

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

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.siz=[1]*n

    def root(self,x):
        while self.par[x]!=x:
            self.par[x]=self.par[self.par[x]]
            x=self.par[x]
        return x

    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.siz[x]<self.siz[y]:
            x,y=y,x
        self.siz[x]+=self.siz[y]
        self.par[y]=x
        return True

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

    def size(self,x):
        return self.siz[self.root(x)]

uni = UnionFind(n)

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

cnt = [0]*(n)
for aa in uni.par:
    cnt[aa] = 1

#print(uni.par)
print(sum(cnt)-1)

Submission status: Wrong Answer

Solution code:
import sys

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

arr = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    arr[a] += 1
    arr[b] += 1

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, os, io
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math,datetime,functools,itertools,operator,bisect,fractions
from collections import deque,defaultdict,OrderedDict,Counter
from fractions import Fraction
from decimal import Decimal
N = 300005
 
# array to store inverse of 1 to N 
factorialNumInverse = [None] * (N + 1) 
 
# array to precompute inverse of 1! to N! 
naturalNumInverse = factorialNumInverse.copy() 
 
# array to store factorial of  
# first N numbers 
fact = factorialNumInverse.copy() 
 
# Function to precompute inverse of numbers 
def InverseofNumber(p): 
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1): 
        naturalNumInverse[i] = (naturalNumInverse[p % i] * 
                                (p - int(p / i)) % p) 
# Function to precompute inverse  
# of factorials 
def InverseofFactorial(p): 
    factorialNumInverse[0] = factorialNumInverse[1] = 1
  
    # precompute inverse of natural numbers 
    for i in range(2, N + 1, 1): 
        factorialNumInverse[i] = (naturalNumInverse[i] * 
                                  factorialNumInverse[i - 1]) % p 
  
# Function to calculate factorial of 1 to N 
def factorial(p): 
    fact[0] = 1
  
    # precompute factorials 
    for i in range(1, N + 1): 
        fact[i] = (fact[i - 1] * i) % p 
  
# Function to return nCr % p in O(1) time 
def Binomial(N, R, p): 
    
      
    # n C r = n!*inverse(r!)*inverse((n-r)!) 
    ans = ((fact[N] * factorialNumInverse[R])% p * 
                      factorialNumInverse[N - R])% p 
    return ans 


def main():
    starttime=datetime.datetime.now()
    if(os.path.exists('input.txt')):
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    
    
    for _ in range(1):
        n,m=ria()
        d={}
        for i in range(m):
            a,b=ria()
            if a in d:
                d[a]+=1
            else:
                d[a]=1
            if b in d:
                d[b]+=1
            else:
                d[b]=1
        print(max(0,n-len(d)))        
        
        
        
        
        
        
                    
        
    #<--Solving Area Ends
    endtime=datetime.datetime.now()
    time=(endtime-starttime).total_seconds()*1000
    if(os.path.exists('input.txt')):
        print("Time:",time,"ms")  
    
                
class FastReader(io.IOBase):
    newlines = 0

    def __init__(self, fd, chunk_size=1024 * 8):
        self._fd = fd
        self._chunk_size = chunk_size
        self.buffer = io.BytesIO()

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, size=-1):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()


class FastWriter(io.IOBase):

    def __init__(self, fd):
        self._fd = fd
        self.buffer = io.BytesIO()
        self.write = self.buffer.write

    def flush(self):
        os.write(self._fd, self.buffer.getvalue())
        self.buffer.truncate(0), self.buffer.seek(0)


class FastStdin(io.IOBase):
    def __init__(self, fd=0):
        self.buffer = FastReader(fd)
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


class FastStdout(io.IOBase):
    def __init__(self, fd=1):
        self.buffer = FastWriter(fd)
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.flush = self.buffer.flush


if __name__ == '__main__':
    sys.stdin = FastStdin()
    sys.stdout = FastStdout()
    main()

Submission status: Wrong Answer

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

cities = [0]*n

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

print(n - sum(cities))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
list = [[]]
for i in range(m):
    a, b  = map(int, input().split())
    for l in list:
        if a not in l:
            if b not in l:
                list.append([a,b])
            else:
                l.append(a)
        else:
            l.append(b)

print(len(list)-2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

cities = {}

for a in range(N):
    cities[a+1] = []

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

a_list = set()
ans = -1
for x,y in cities.items():
    # print(x,y)
    if x not in a_list:
        a_list.add(x)
        for z in y:
            a_list.add(z)
            # print(a_list)
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
r=[]
t=[]
for i in range(m):
    a,b=map(int,input().split())
    t.append(a)
    t.append(b)
    l = set(t)
    p = len(l)
    ans = n-p
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
List=[]
for i in range(m):
  lst=list(map(int,input().split()))
  List.append(lst[0])
  List.append(lst[1])
town = len(list(range(1,n+1)))
road = len(list(set(List)))
print(town-road)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
pair = [i for i in range(n + 1)]
def find(x):
    if pair[x] == x:
        return x
    else:
        pair[x] = find(pair[x]) 
        return pair[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
    pair[x] = y
    
for i in range(m):
    a, b = map(int, input().split())
    unite(a,b)

print(len(set(pair[1:])) - 1)

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 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(e):
  a, b = map(int, input().split())
  unite(a, b)
  
print(len(set(par))-2)

Submission status: Wrong Answer

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

dp = [0] * n
ans = 0

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import collections
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
B=list(itertools.chain.from_iterable(A))
C=len(collections.Counter(B))
print(N-C)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import string
import math
import sys
def array_int():
    return [int(i) for i in sys.stdin.readline().split()]
def vary(number_of_variables):
    if number_of_variables==1:
        return int(sys.stdin.readline())
    if number_of_variables>=2:
        return map(int,sys.stdin.readline().split()) 
def makedict(var):
    return dict(Counter(var))
mod=100000007
import math
fact=[1]
MAX=100001
mod=998244353
for i in range(1,MAX):
	fact.append((fact[-1]*i)%mod)
def ncr(n , k): 
    global mod,fact
    num=fact[n]
    den=((fact[n-k])*(fact[k]))%mod
    return (num*pow(den,mod-2,mod))%mod
n,m=vary(2)
dict={}
for i in range(m):
    u,v=vary(2)
    dict[u]=1
    dict[v]=1
np=[i for i in range(1,n+1)]
nt=set(np)
count=0
for i in dict:
    if i in nt:
        count+=1
print(n-count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ways=(n-1)
checked= [False] * n

for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  if checked[a] and checked[b]:
    continue
  ways-=1
  checked[a]=True
  checked[b]=True

print(ways)

Submission status: Wrong Answer

Solution code:
N, M=map(int, input().split(" "))
path=[]

for i in range(M):
  path.append(list(map(int, input().split(" "))))

print(N-1-M)

Submission status: Wrong Answer

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
from itertools import permutations
class DSU:
    def __init__(self,n):
        self.par=list(range(n))
        self.sz=[1]*(n)
    def find(self,x):
        if x!=self.par[x]:
            self.par[x]=self.find(self.par[x])
        return self.par[x]
    def union(self,x,y):
        x,y=self.find(x),self.find(y)
        if x!=y:
            if self.sz[y]>self.sz[x]:
                x,y=y,x
            self.par[y]=x
            self.sz[x]+=self.sz[y]
            self.sz[y]=self.sz[x]
            return True
        return False

def solve(N,A):
    dsu=DSU(N)
    for a,b in A:
        dsu.union(a-1,b-1)
    sets=set(dsu.par)
    return len(sets)-1



N,M=readMap()
A=[]
for _ in range(M):
    a,b=readMap()
    A.append((a,b))
print(solve(N,A))

Submission status: Wrong Answer

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

ans = n-1-m
print(ans)

Submission status: Wrong Answer

Solution code:
# @oj: atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-09-26 20:17
# @url:
import sys,os
from io import BytesIO, IOBase
import collections,itertools,bisect,heapq,math,string
from decimal import *
# region fastio

BUFSIZE = 8192

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# ------------------------------
## 注意嵌套括号!!!!!!
## 先有思路,再写代码,别着急!!!
## 先有朴素解法,不要有思维定式,试着换思路解决
def main():
    n,m=map(int,input().split())
    s=set()
    for i in range(m):
        a=list(map(int,input().split()))
        s.add(a[0])
        s.add(a[1])
    print (n-len(s))
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
n,m=map(int,input().split())
r=[0]*n
for i in range (m):
  a,b=map(int,input().split())
ans=n-2*m
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    #xとyが同じ集合に属するかを判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
n,m=map(int,input().split())
ans=0
U = UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  U.unite(a,b)
print(len(set(U.par))-1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    #xとyが同じ集合に属するかを判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
n,m=map(int,input().split())
ans=0
U = UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  U.unite(a,b)
print(U.par)
print(len(set(U.par))-1)

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)
a_s=set(path.keys())
visited=set()
cnt=0
for i in range(1,n+1):
    if i in visited: continue
    visited.add(i)
    cnt+=1
    if i in a_s:
        lis=path[i]
        for j in lis: visited.add(j)
print(cnt-1)

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

par=set(par)

print(len(par)-2)

Submission status: Wrong Answer

Solution code:
import numpy as np
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)

parents = np.array(uf.parents)
idx = np.count_nonzero(parents)
print(idx-1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

l = []
for i in range(1,N+1):
    l.append(i)
ans = 0
for i in range(M):
    A,B = map(int,input().split())
    if A in l:
        l.remove(A)
    if B in l:
        l.remove(B)

print(len(l))