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:
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())
    a -= 1
    b -= 1
    uf.union(a,b)

print(uf.group_count())

Submission status: Wrong Answer

Solution code:
import numpy as np
number=input().rstrip().split(' ')
N=int(number[0])
M=int(number[1])
judge=np.zeros([N-1])

for i in range(M):
    cities=input().rstrip().split(' ')
    A=int(cities[0])
    judge[A-1]=1

print(np.count_nonzero(judge==0))

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())
    un = UnionFind(n)
    ans = 0
    for i in range(m):
        a, b = map(int, input().split())
        un.union(a, b)
    for i in range(2, n + 1):
        if un.findroot(i) != 1:
            ans += 1
            un.union(i, 1)
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Wrong Answer

Solution code:
def solve():
    n, m = map(int, input().split())
    connected = {}
    if m:
        a, b = map(int, input().split())
        connected[0] = [a, b]
    for _ in range(m - 1):
        a, b = map(int, input().split())
        for x in range(len(connected)):
            if a or b in connected[x]:
                connected[x] = connected[x] + [a, b]
                break
            elif x == connected:
                connected[x + 1] = [a, b]
                break
    
    return len(connected)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
value = set()
certain = set()
for i in range(1,N+1):
  certain.add(i)
for i in range(M):
  a,b = map(int,input().split())
  value.add(a)
  value.add(b)
  
print(len(certain - value))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
l = [set() for _ in range(n)]
for i in range(n):
  l[i].add(i+1)
for i in range(m):
  a,b = map(int, input().split())
  l[a-1] = l[a-1] | l[b-1]
  l[b-1] = l[a-1] | l[b-1]
s = set()
for i in l:
  s.add(tuple(i))
print(len(s)-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
gr = 0
ch = [0]*n
for num in range(m):
  a,b = map(int,input().split())
  if ch[a-1] == 0 and ch[b-1] == 0:
    gr += 1
  ch[a-1] = 1
  ch[b-1] = 1

count = 0
for num in range(n):
  if ch[num] == 0:
    count += 1

print(gr - 1 + count)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
from collections import Counter
import networkx as nx
setrecursionlimit(1000000)
def l_in(type_): return list(map(type_, input().split()))
def i_in(): return int(input())
def m_in(type_): return map(type_, input().split())
def r_in(n, type_): return [type_(input()) for _ in range(n)]

def find_components(n, connectors):
    g = nx.Graph()
    g.add_edges_from(connectors)
    return len(list(nx.connected_components(g)))


n, m = m_in(int)
ab = [list(m_in(int)) for _ in range(m)]

ans = find_components(n, ab) - 1

print(ans)

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

m3 = list(connected_components(G))

count = 0

if len(max(connected_components(G), key=len)) == n:
    print(0)
    exit()
else:
    for i in m3:
        count += len(i)

sub = n - count

if sub != 0:
    print(sub)

else:
    print(len(m3)-1)

Submission status: Wrong Answer

Solution code:
date = input().split()
N = int(date[0])
city = list(range(1,N+1))
M = int(date[1])
for i in range(M):
  load = input().split()
  A = int(load[0])
  B = int(load[1])
  if A in city:
    city.remove(A)
  if B in city:
    city.remove(B)
print(len(city))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
cityList = set()
loadList = []
for i in range(M):
    loadList.append(set(list(map(int,input().split()))))
for i in range(N):
    cityList.add(i + 1)
print(loadList[0])
print(cityList)
j = 0
ans = 0
while(len(loadList) != 1):
    k = 1
    for k in range(len(loadList)):
        set_cap = loadList[0] & loadList[k]
        if(len(set_cap) != 0):
            loadList[0] = loadList[0] | loadList[k]
            ans += 1
gap = cityList - loadList[0]
ans += len(gap)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections
#sys.exit()
#sorted( ,reverse=True)
#N = int(input())
N,M = map(int, input().split())

A = [input().rstrip().split(" ") for i in range(M)]
X = list(range(1,N+1))
#print(A)
#print(X)
for i in range(M):
    if int(A[i][0]) in X:
        X[X.index(int(A[i][0]))] ="Z"
    if int(A[i][1]) in X:
        X[X.index(int(A[i][1]))] ="Z"
#print(X)        
#print(X.count("Z"))

print(N-X.count("Z"))
#cnt = 0
#cnt += 1


#print(N,M)



#print(S,T)
#print(A)
#print('Yes')
#print('No')
#print(cnt)

Submission status: Wrong Answer

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

count = 1

for i in range(N):
   
      
    if  count == A or B:
        count += 0
    else:
       count += 1 
    
print(count)

Submission status: Wrong Answer

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


for j in range(m):
  for k in range(1,m-j,1):
    if len(list(set(road[j]) & set(road[j+k])))>0  and (road[j][0] !=0):
      road[j] = road[j] + road[k]
      road[k] = [0,0]
def unique(some_value):
  a = []
  return[x for x in some_value if x not in a and not a.append(x)]
b = unique(road)

ask = []
for y in range(len(b)):
  ask +=b[y]
diff = list(set(town) ^ set(ask))
print(len(b)-3+len(diff))

Submission status: Wrong Answer

Solution code:
import itertools
N,M=map(int,input().split())
AB=[]
for i in range(M):
    AB.append(list(map(int,input().split())))
AB=list(itertools.chain.from_iterable(AB))
count=0
for i in range(1,N+1):
    if not i in AB:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:

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

    if M >= N:
        print ('0')
    else:
        print(N-1-M)


main()

Submission status: Wrong Answer

Solution code:
import itertools

n,m =  map(int,input().split())
l = [list(map(int,input().split()))]

for i in range(m-1):
    ab = list(map(int,input().split()))

    for j in range(len(l)):
        if ab[0] in l[j] or ab[1] in l[j]:
            l[j].extend(ab)
        else:
            l.append(ab)

cntList = list(itertools.chain.from_iterable(l))
cnt = 0
for i in range(1,n+1):
    if i not in cntList:
        cnt += 1

print(len(l)+cnt)

Submission status: Wrong Answer

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

roads = set()

for i in range(m):
    roads = roads | set([int(x) for x in input().split()])

print(n - len(roads))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = set(i for i in range(1, n+1))

for _ in range(m):
    a, b = map(int, input().split())
    try:
        s.remove(b)
    except:
        pass

print((len(s) * (len(s)-1))//2)

##N, Q = map(int, input().split())
##s = '1'*N
##for _ in range(Q):
##    l, r, d = map(int, input().split())
##    s = s[:l-1] + str(d)*(r-l+1) + s[r:]
##    print(int(s) % 998244353)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
group = [0 for i in range(N+1)]
tf = [0 for i in range(N+1)]
count = 1
ans = []
for i in range(M):
  A, B = map(int, input().split())
  if tf[A]==1 and tf[B]==1:
    if group[B] not in ans:
      ans.append(group[B])
    if group[A] not in ans:
      ans.append(group[A])
  elif tf[A]==0 and tf[B]==1:
    tf[A] = 1
    group[A] = group[B]
  elif tf[B]==0 and tf[A]==1:
    tf[B] = 1
    group[B] = group[A]
  else:
    tf[A] = 1
    tf[B] = 1
    group[A] = count
    group[B] = count
    count += 1

print(max(group)-1+tf.count(0)-1-len(ans)+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())
import copy
c=[]
c=copy.copy(a)
for i in range(M):
    c.append(b[i])
c.sort()
#print(c)
counter=1
for i in range(len(c)):
    if i>0 and c[i]!=c[i-1]:
        counter+=1
#print(counter)
ans=N-(M+1)+(M+1-counter)
print(ans)

Submission status: Wrong Answer

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-1] = 0
    n[B-1] = 0
m = set(n)
print(len(m)-1)

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])
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())
    
print((N-1)-M)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class numb:
  def __init__(self,n):
    self.n = n
  def __eq__(self, other):
    return self.n == other.n

n, m = map(int,input().split())
abs = [numb(0) for _ in range(n+1)]
zero =numb(0)
tmp = 0
tmp2 = n
ans = -1
for i in range(m):
  _a, _b = map(int,input().split())
  if abs[_a]==zero and abs[_b] ==zero:
    tmp2 = tmp2-2
    tmp = tmp+1
    ans = ans + 1
    n = numb(tmp)
    abs[_a] =n
    abs[_b] =n
  elif abs[_a]==zero:
    tmp2 = tmp2-1
    abs[_a] = abs[_b]
  elif abs[_b] ==zero:
    tmp2 = tmp2-1
    abs[_b] = abs[_a]
  else:
    if abs[_a] == abs[_b]:
      pass
    else:
      ans = ans -1
      abs[_a].n = abs[_b].n 
ans = ans + tmp2
print(ans)

Submission status: Wrong Answer

Solution code:
import queue
n, m = map(int, input().split())
a = [[] for _ in range(n)]
ans = 0
 
for _ in range(m):
    x, y = map(int, input().split())
    a[x-1].append(y-1)
    a[y-1].append(x-1)
 
route = set()
route.add(0)
q = queue.Queue()
q.put(0)

Submission status: Wrong Answer

Solution code:
def acquire_nums() :    
    return list(map(lambda x : int(x), input().split())) 

inputs = acquire_nums()
N = inputs[0]
ans = int((N+2-1)/2) - 1
print(ans)

Submission status: Wrong Answer

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

        for j in w[i]:
            if c[j] == 0:
                c[j] = 1
                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: Wrong Answer

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

Submission status: Wrong Answer

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


print(len(set(range(1, N + 1)).difference(A) & set(range(1, N + 1)).difference(B)))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((min(a, b), max(a, b)))
AB = sorted(AB, key = lambda x: x[0])

cnt = [0]*(N+1)
chk = 0
for a, b in AB:
    if cnt[a] == 0 and cnt[b] == 0:
        cnt[a] = a
        cnt[b] = a
    elif cnt[a] > 0:
        cnt[b] = cnt[a]
cnt0 = cnt[1:].count(0)
print(len(set(cnt[1:])) -1 + cnt0 -1)

Submission status: Wrong Answer

Solution code:
N, M=map(int, input().split(" "))
graph=[[] for i in range(N)]

for i in range(M):
  temp=list(map(lambda x: x-1, map(int, input().split(" "))))
  graph[temp[0]].append(temp[1])
  graph[temp[1]].append(temp[0])

count=0
for ar in graph:
  if len(ar)==0:
    count=count+1
print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ls = []
for i in range(m):
    x = 0
    a,b = map(int,input().split())
    for i in range(len(ls)):
        if a in ls[i]:
            ls[i].append(b)
            x = 1
            break
        elif b in ls[i]:
            ls[i].append(a)
            x = 1
            break
    if x == 0:
        ls.append([a,b])
ans = 0
temp = [i+1 for i in range(n)]
temp2 = sorted(ls[0])
print(n-len(set(temp)&set(temp2)))

Submission status: Wrong Answer

Solution code:
import itertools
N,M=map(int,input().split())
AB=[]
for i in range(M):
    AB.append(list(map(int,input().split())))
AB=list(itertools.chain.from_iterable(AB))
count=0
for i in range(N):
    if not i in AB:
        count+=1
print(count)

Submission status: Wrong Answer

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

num1=road.count(1)
num2=road.count(2)*2

print(int((num1+num2-2)/2))

Submission status: Wrong Answer

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

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

road = 0
c = []
for i in range(n):
  if i not in c:
    c.append(i)
    c.extend(gp[i])
    x = gp[i]
    for j in x:
      for k in gp[j]:
        if k not in c:
          c.append(k)
          x.append(k)
    road += 1
  else:
    pass
  
print(road)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = N
E = [i for i in range(N)]
inp = []
for _ in range(M):
    a,b = map(int,input().split())
    if a>b:
        tmp = a
        a = b
        b = tmp
    inp.append([a,b])

inp.sort()
count = 0
for i in inp:
    a,b = i
    if E[b-1] == E[a-1]:
        count += 1
    E[b-1] = E[a-1]


print((N-1)-(M-count))

Submission status: Wrong Answer

Solution code:
X = input().split()
N = int(X[0])
M = int(X[1])
R = []
for i in range(M):
    Y = input().split()
    A = Y[0]
    R.append(A)
    B = Y[1]
    R.append(B)
RX = list(set(R))
print(N - len(RX))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
roads = set()
dic = {x:set([x]) for x in range(1, n + 1)}

for _ in range(m):
  a,b = map(int, input().split())
  dic[a].add(b)
  dic[b].add(a)

  roads.add(a)
  roads.add(b)

count = 0
for i in range(1, n + 1):
    if i not in dic[1]:
        count += 1
        dic[1] = set(list(dic[1]) + [i] + list(dic[i]))

print(count)

Submission status: Wrong Answer

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

if n-1-m >=0:
    print(n-1-m)

Submission status: Wrong Answer

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

route = set()
for ab in AB:
    route.add(ab[0])
    route.add(ab[1])
    if(len(route) == N):
        break
print(N - len(route))

Submission status: Wrong Answer

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

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

for i in a_b:
    a, b = map(int, i.split())
    ans[a-1].append("*")
    ans[b-1].append("*")
    

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

Submission status: Wrong Answer

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

if  n==3:
  ans=n-1-m
  print(ans)
else:
  ans=n-2-m
  print(ans)

Submission status: Wrong Answer

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

num1=road.count(1)
num2=road.count(2)*2

print((num1+num2-2)/2)

Submission status: Wrong Answer

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


group = [-1] * n
groups = []
nmerges = 0
for e in edges:
    if group[e[0]] == -1 and group[e[1]] == -1:
        gid = len(groups)
        group[e[0]] = group[e[1]] = gid
        groups.append(set([e[0],e[1]]))
    elif group[e[0]] == -1 and group[e[1]] != -1:
        g = group[e[1]]
        group[e[0]] = g
        groups[g].add(e[0])
    elif group[e[0]] != -1 and group[e[1]] == -1:
        g = group[e[0]]
        group[e[1]] = g
        groups[g].add(e[1])
    else:
        if group[e[0]] != group[e[1]]:
            nmerges += 1

cnt = len(groups) - nmerges
cnt += sum(map(lambda gid: gid == -1, group))
cnt -= 1
print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
root = [0] * (N + 1)
for _ in range(M):
    a,b= map(int,input().split())
    root[a] = 1
    root[b] = 1
print(root.count(0)-1)

Submission status: Wrong Answer

Solution code:
N, M=map(int, input().split())
miti = [[] for i in range(N)]
for _ in range(M):
  a, b=map(int, input().split())
  miti[a-1].append(b-1)
  miti[b-1].append(a-1)
visited = set([0])
ans=0
for idx, c in enumerate(miti):
  if idx not in visited:
    ans+=1
  [visited.add(i) for i in c]
print(ans)

Submission status: Wrong Answer

Solution code:
x,y=map(int,input().split())
a=[list(map(int,input().split())) for l in range(y)]
b=list(range(x))
M=0

while M<y:
    if a[M][0] in b:
        b.remove(a[M][0])

    M=M+1

M=0

while M<y:
    if a[M][1] in b:
        b.remove(a[M][1])

    M=M+1

print(len(b))

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

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

Submission status: Wrong Answer

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

d = list(filter(lambda x:x not in c, b))

print(len(d)//2 + 1)

Submission status: Wrong Answer

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

print(len(set(range(1, N + 1)).difference(A | B)))

Submission status: Wrong Answer

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

   
print(max(group)+ans-1+tf.count(0)-1)

Submission status: Wrong Answer

Solution code:
def dfs(city,tmpList):
  global memo,ans
  if memo[city]!=0:
    return
  ans += 1
  memo[city]=1
  for c in myList[city]:
    dfs(c,tmpList + [city])
  return

n,m = map(int,input().split())
memo = [0 for i in range(n+1)]
myList = [[] for i in range(n+1)]
for i in range(m):
  a,b = map(int,input().split())
  myList[a].append(b)
#print(memo,myList)
cnt = 0
for i in range(1,n+1):
  ans = 0
  dfs(i,[])
  if ans > 0:
    cnt += 1
  #print(i,ans)
#print(memo,myList)
print(cnt-1)

Submission status: Wrong Answer

Solution code:
class numb:
  def __init__(self,n):
    self.n = n
  def __eq__(self, other):
    return not other == 0 and self.n == other.n

n, m = map(int,input().split())
abs = [0]*(n+1)
tmp = 0
tmp2 = n
ans = -1
for i in range(m):
  _a, _b = map(int,input().split())
  if abs[_a]==0 and abs[_b] ==0:
    tmp2 = tmp2-2
    tmp = tmp+1
    ans = ans + 1
    n = numb(tmp)
    abs[_a] =n
    abs[_b] =n
  elif abs[_a]==0:
    tmp2 = tmp2-1
    abs[_a] = abs[_b]
  elif abs[_b] ==0:
    tmp2 = tmp2-1
    abs[_b] = abs[_a]
  else:
    if abs[_b] == abs[_a]:
      pass
    else:
      ans = ans -1
      abs[_a].n = abs[_b].n 
ans = ans + tmp2
print(ans)

Submission status: Wrong Answer

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

# 都市分のリストを作成
res = [0] * N

# 道路の数だけ入力する
for i in range(M):
    x, y = map(int, input().split())
    res[x-1] += 1
    res[y-1] += 1

if (N-1)*2 <= sum(res):
    print(0)
else:
    result = ((N-1)*2 - sum(res)) / 2
    print(int(result))

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:
        if wk_a < wk_b:
            pl[in_b] = wk_a
        else:
            pl[in_a] = wk_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())
    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())
u = set()
for _ in range(m):
    a, b = map(int, input().split())
    u.add(a)
    u.add(b)
print(n - len(u))

Submission status: Wrong Answer

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

for i in range(m):
  a, b = map(int, input().split())
  al, bl = linked[a][0], linked[b][0]
  if al == bl: continue

  al.extend(bl)
  linked[b][0] = al
  
print(linked)


n_connected = 0
n_group = 0
for s in linked.values():
  s = s[0]
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))

Submission status: Wrong Answer

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# a_list = [0] * a
sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    n, m = get_int_multi()

    aa = [0] * (n+1)
    ans = n-1

    for i in range(0,m):
        a, b = get_int_multi()
        if aa[a] == 0 and aa[b] == 0:  # 独立してたらつなげる
            aa[a] = a
            aa[b] = a
            ans -= 1
        elif aa[a] != 0 and aa[b] == 0:
            aa[b] = aa[a]
            ans -= 1
        elif aa[a] == 0 and aa[b] != 0:
            aa[a] = aa[b]
            ans -= 1
        elif aa[a] != aa[b]:
            ans -= 1
            wk = aa[b]
            for ii in range(wk, n):
                if aa[ii] == wk:
                    aa[ii] = aa[a]


    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def acquire_nums() :    
    return list(map(lambda x : int(x), input().split())) 

inputs = []
try:
    while True :
        a = acquire_nums()
        if (len(a) <= 0):
            break
        else:
            inputs.append(a)
except EOFError:
	pass

N, M = inputs[0][0], inputs[0][1]
ans = int((N+2-1)/2) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
towns = [0] * n
cnt = 1

def rewr(x, y, z):
    if x == y:
        return z
    else:
        return x

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if towns[a] == 0 and towns[b] == 0:
        towns[a] = cnt
        towns[b] = cnt
        cnt += 1
    elif towns[a] > 0 and towns[b] == 0:
        towns[b] = towns[a]
    elif towns[b] > 0 and towns[a] == 0:
        towns[a] = towns[b]
    elif towns[a] > 0 and towns[b] > 0:
        if towns[a] != towns[b]:
            min_no = min(towns[a], towns[b])
            max_no = max(towns[a], towns[b])
            towns = [rewr(twn, max_no, min_no) for twn in towns]
    else:
        pass
        #print('pass')

rslt = 0
#print(towns)
rslt += max(towns) - 1
rslt += towns.count(0)
print(rslt)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
cnt = []
for _ in range(M):
    a, b = map(int, input().split())
    cnt.append(a)
    cnt.append(b)
    
cnt = len(list(set(cnt)))
print(N-cnt)

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [list(map(int,input().split())) for _ in range(W)]

ans=[]

for i in range(W):
  for j in range(0,2):
    ans.append(S[i][j])

ans=sorted(set(ans))

print(H-len(ans))

Submission status: Wrong Answer

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

        for j in w[i]:
            if c[j] == 0:
                c[j] = 1
                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: Wrong Answer

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

visited = dict()
count = -1

for i in range(m):

  x,y = list(map(int, input().split()))

  if x not in visited and y not in visited:
    count += 1

  visited[x] = 0
  visited[y] = 0

count += n - len(visited)
print(count)