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())
island = [0] * (n+1)
land_num = n
bridge = 1

for i in range(m):
    a,b = map(int, input().split())
    if island[a] == 0 and island[b] == 0:
        land_num -= 1
        island[a]+= bridge
        bridge += 1
    elif island[a] == 0 and island[b] != 0:
        island[a] = island[b]
        land_num -= 1
    elif island[a] != 0 and island[b] == 0:
        island[b] = island[a]
        land_num -= 1
    elif island[a] != 0 and island[b] != 0:
        island[a] = min(island[a],island[b])
        island[b] = min(island[a],island[b])
        land_num -= 1
print(land_num-1)

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)

ans = len(set(UF.parent))-1
print(ans)
print(UF.parent)

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
    
print(N - sum(res))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import networkx as nx
n,m=map(int, input().split())
uf=nx.utils.UnionFind()
for _ in range(m):
    a,b=map(int, input().split())
    uf.union(a, b)
ans=1
for i in uf.to_sets():
    ans=max(ans,len(i))
print(ans-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
na = list(range(1, N))
nb = list(range(2, N+1))
cnt_a = [0 for _ in range(N)]
cnt_b = [0 for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    cnt_a[a-1] += 1
    cnt_b[b-1] += 1
    if cnt_a[a-1] == 1:
        na.remove(a)
    if cnt_b[b-1] == 1:
        nb.remove(b)
print(min(len(na), len(nb)))

Submission status: Wrong Answer

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

print(len(lis)-sum(lis))

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:
        if j in visited: cnt-=1
        visited.add(j)
print(max(cnt-1,0))

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(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(m):
            if aa[ii] == wk:
                aa[ii] = aa[a]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

c = 0
for i in range(1, N):
  d = False
  for j in AB:
    if i == j[0] and i+1 == j[1]:
      d = True
      break
  if not d:
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import copy
import collections

N, M = map(int, input().split())
c = [[] for _ in range(N)]
m = [-1] * N

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

for i in range(N):
  if m[i] != -1: continue
  l = copy.copy(c[i])
  while len(l) > 0:
    t = l.pop()
    if m[t] == -1:
      m[t] = i
      l = l + c[t]
        
ans = len(collections.Counter(m)) - 1

print(ans)

Submission status: Wrong Answer

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

def main():
    roads=[]
    n,m = map(int,input().split())
    roads=[list(map(int,input().split())) for _ in range(m)]
    count=0

    if n-m==1:
        print(0)
        exit()
    else:
        for road in roads:
            if 1 in road or 2 in road:
                count+=1
    print(count)

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
t=[]
tmp = 1
for q in range(m):
    a,b=map(int,input().split())
    t.append(a)
    t.append(b)
for i in range(n):
    num=t.count(i+1)
    if(tmp < num):
        tmp = num
if(n > 4):
    if(tmp==1):
        l = len(set(t))
        ans = n - l + 1
        print(ans)
    else:
        l = len(set(t))
        ans  = n-l
        print(ans)
else:
    l = len(set(t))
    ans  = n-l
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ans = n-1-m

if ans > 0:
  print(ans)
else:
  print("0")

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list()
b=list()
for i in range(m):
	c,d=map(int,input().split())
	a.append(c)
	b.append(d)
ans=int(0)
city=[0]*(n+1)
for i in range(m):
	if (city[a[i]] == 0) and (city[b[i]] == 0):
		ans=ans+1
		city[a[i]]=ans
		city[b[i]]=ans

	elif (city[a[i]] != 0) and (city[b[i]] == 0):
		city[b[i]]=city[a[i]]

	elif (city[a[i]] == 0) and (city[b[i]] != 0):
		city[a[i]]=city[b[i]]

	elif (city[a[i]] <= city[b[i]]):
		x=city[b[i]]
		y=city[a[i]]
		for j in range(n+1):
			if city[j] == x:
				city[j]=y

	else:
		y=city[b[i]]
		x=city[a[i]]
		for j in range(n+1):
			if city[j] == x:
				city[j]=y

print(max(city)+city.count(0)-2)

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
ns = [0]*n
sima = n
for i in range(m):
    if ns[a[i]-1] == 0 or ns[b[i]-1] == 0:
        ns[a[i]-1] = 1
        ns[b[i]-1] = 1
        sima -= 1

print(sima-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 N <= 2 or N-1-M <=0:
    print(0)
elif N-1-M >0:
    print(N-1-M)

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())

for i in range(M):
    A, B = (int(x) for x in input().split())
    
print("{}".format(N-M-1))

Submission status: Wrong Answer

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

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())
ABs = [tuple(map(int, input().split())) for _ in range(M)]

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

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:
        par[x] = y

for a, b in ABs:
    unite(a-1, b-1)

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
road = 0
for i in range(m):
    a, b = list(map(int, input().split()))
    if n%2 != 0:
        road +=1
print(road)

Submission status: Wrong Answer

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


print (N - M -1)

Submission status: Wrong Answer

Solution code:
#!/usr/local/bin/python3

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

G = {i: [i] for i in range(N)}

for a, b in AB:
    a, b = a-1, b-1
    if len(G[a]) > len(G[b]):
        G[a].append(b)
        G[b] = G[a]
    else:
        G[b].append(a)
        G[a] = G[b]

groups = []
for g in G.values():
    if g not in groups:
        groups.append(g)

print(len(groups)-1)

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int, input().split())
    d = dict()
    cnt = 0
    for i in range(1,n+1):
        d[i] = []
    for _ in range(m):
        first, second = map(int, input().split())
        d[first].append(second)
        d[second].append(first)
    for city in d:
        if len(d[city])==0:
            cnt +=1
    return cnt



if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
N,Q = 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(Q):
    a,b = map(int,input().split())
    unite(a,b)
for i in range(N):
  find(i)
print(len(set(par))-2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

h=[-1]*n

c=[]*n

cnt=n

for i in range(m):
  a,b=map(int,input().split())
  if h[a-1]==-1 and h[b-1]==-1:
    cnt-=1
    h[a-1]=cnt
    h[b-1]=cnt
  elif h[a-1]!=-1 and h[b-1]==-1:
    h[b-1]=h[a-1]
  elif h[a-1]==-1 and h[b-1]!=-1:
    h[a-1]=h[b-1]
  else:
    cnt-=1
    for j in range(n):
      
      if h[j]==h[b-1]:
        h[b-1]=h[a-1]
print(cnt-1)

Submission status: Wrong Answer

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

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

x = N-1-M

if x < 0:
    print(0)

else:
    print(x)

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
field=[list(map(int,input().split())) for i in range(M)]
ans=(N-1)-M
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
cities = [0]*N
for i in range(M):
    a, b = map(int, input().split())
    if cities[a-1] and cities[b-1]:
        temp_a = cities[a-1]
        temp_b = cities[b-1]
        for j in range(N):
            if cities[j]==temp_b:
                cities[j]=temp_a
    elif cities[a-1]:
        cities[b-1]=cities[a-1]
    elif cities[b-1]:
        cities[a-1] = cities[b-1]
    else:
        count=max(cities)
        cities[a-1] = count+1
        cities[b-1] = count+1
print(cities.count(0)+max(cities)-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:
#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,k = ip()
x = [inp() for i in range(n)]
"""

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)
ct = 0
for i in range(1,n+1):
    if graph[i] == []:
        ct += 1
print(ct)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import deque

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=[[] for _ in range(100001)]
    sys.setrecursionlimit(100001)
    mark=[0]*N
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A-1].append(B-1)
        dic[B-1].append(A-1)


    i=0
    count=0
    while True:
        if not mark[i]:
            count+=1
            d=deque()
            d.appendleft(i)
            while d:
                a=d.popleft()
                mark[a]=1
                for a in dic[i]:
                    if mark[a]:
                        break
                    else:
                        d.appendleft(a)


        i+=1
        if i==N:
            break
    
    print(count-1)
main()

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

size = 0
for i in range(n):
    print(uf.parents[i])
    if uf.parents[i] == i:
        size += 1
print(size-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = []
c = 0
for i in range(M):
  a, b = map(int, input().split())
  l += [a, b]

for i in range(1, N + 1):
  if l.count(i) == 0:
    c += 1
print(c)

Submission status: Wrong Answer

Solution code:

n,m = map(int, input().split())
s = []
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())

print(n-m-1)

Submission status: Wrong Answer

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

*p, = range(n)
rank = [1]*n
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1
 
for a,b in ab:
    unite(a-1,b-1)

print( len(set(p)) - 1 )

Submission status: Wrong Answer

Solution code:
import sys
import math,bisect
sys.setrecursionlimit(10 ** 5)
from itertools import groupby,accumulate
from heapq import heapify,heappop,heappush
from collections import deque,Counter,defaultdict
def I(): return int(sys.stdin.readline())
def neo(): return map(int, sys.stdin.readline().split())
def Neo(): return list(map(int, sys.stdin.readline().split()))
class Graph(object):
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def addEdge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def connectedComponents(self):
        unvisited = set(range(self.V))
        queue = deque()

        count = 0
        while len(unvisited) > 0:
            count += 1
            v = next(iter(unvisited))
            unvisited.remove(v)
            queue.append(v)
            while len(queue) > 0:
                v = queue.popleft()
                for w in self.graph[v]:
                    if w in unvisited:
                        unvisited.remove(w)
                        queue.append(w)

        return count

N,M = neo()
graph = Graph(N)
for i in range(M):
    e = Neo()
    graph.addEdge(e[0], e[1])
print(graph.connectedComponents()-1)

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())

for i in range(M):
    A, B = (int(x) for x in input().split())

if N < M:
    print("0")

else:
    print("{}".format(N-M-1))

Submission status: Wrong Answer

Solution code:
N,M = list(map(int, input().split()))
table = [0]*N
count = 1
for i in range(M):
    A, B = list(map(int, input().split()))
    if (table[A-1] == 0)&(table[B-1] == 0):
        table[A-1] = count
        table[B-1] = count
        count += 1
    elif (table[A-1] != 0)&(table[B-1] == 0):
        table[B-1] = table[A-1]
    elif (table[A-1] == 0)&(table[B-1] != 0):
        table[A-1] = table[B-1]
        
print(len(set(table))-1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]
 
    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size
 
    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x
 
    def is_connected(self, x: int, y: int) -> bool:
        return self[x] == self[y]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x
 
 
import sys
 
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())
tree = UnionFind(N)
res = []
ans=0
for _ in range(Q):
  u, v = map(int, readline().split())
  tree.unite(u-1, v-1)
for u in range(1,N):
  #print(tree.is_connected(u, 0),u)
  if not tree.is_connected(u, 0):
      ans+=1
      tree.unite(u-1, 0)
print(ans)

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

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 a, b in ab:
    unite(a, b)

par = par[1:]

se = set()

for i in par:
    se.add(i)

print(len(par)-len(se))

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.append(a)
  B.append(b)
  
if (N - 1) == M:
  print(0)
else:
  print(N - 1 - M)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]
 
    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size
 
    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x
 
    def is_connected(self, x: int, y: int) -> bool:
        return self[x] == self[y]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x
 
 
import sys
 
readline = sys.stdin.readline
 
N, Q = map(int, readline().split())
tree = UnionFind(N)
res = []
ans=0
for _ in range(Q):
  u, v = map(int, readline().split())
  tree.unite(u-1, v-1)
for u in range(1,N):
  print(tree.is_connected(u, 0),u)
  if not tree.is_connected(u, 0):
      ans+=1
      tree.unite(u-1, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = (int(i) for i in input().split(" "))
for i in range(m):
    input()
print(n-m-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())
if N > M:
  print(N-M-1)
else:
  print(0)

Submission status: Wrong Answer

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

max_num = N - 1

# 全てのグループが和集合になるか
counts = {i: 0 for i in range(1, N+1)}
for group in bridge:
  counts[group[0]] += 1
  counts[group[1]] += 1

if max_num > max(counts.values()):
  print(max_num - max(counts.values()))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(idx):
    for x in arr[idx]:
        if not vis[x]:
            vis[x] = True
            dfs(x)


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

arr = [[] * (n + 1) for _ in range(n + 1)]
vis = [False] * (n + 1)

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

ans = 0

if m == 0:
    print(n-1)
    sys.exit()

dfs(1)
for i in range(2, n + 1):
    if not vis[i]:
        vis[i] = True
        dfs(i)
        ans += 1
for i in range(1, n + 1):
    if not vis[i]:
        ans += 1
print(ans)

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

Submission status: Wrong Answer

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

roads = []

for i in range(m):
    roads.append([int(i) for i in input().split()])

print(n - m)

Submission status: Wrong Answer

Solution code:
import sys

#UnionFindTreeクラスの定義
class UnionFind():
    #クラスコンストラクタ
    #selfはインスタンス自身
    def __init__(self, n):
        #親ノードを-1に初期化する
        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]

    #xとyの木を併合する
    def union(self, x, y):
        #x,yの根をX,Yとする
        X = self.find(x)
        Y = self.find(y)

        #根が同じなら結合済み
        if X == Y:
            return

        #ノード数が多い方をXとする
        if self.parents[X] > self.parents[Y]:
            X, Y = Y, X

        #XにYのノード数を足す
        self.parents[X] += self.parents[Y]
        #Yの根を X>0 とする
        self.parents[Y] = X


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

#UnionFindインスタンスの生成
uf = UnionFind(N)
for a, b in info:
    #インデックスを調整し、a,bの木を結合
    a -= 1; b -= 1
    uf.union(a, b)

c = 0
for i in range(N):
  if uf.parents[i] < 0:
    c += 1

print(c)

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)
if(len(p)==len(l)):
    print(n-len(p)+1)
else:
    print(n-len(p))

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

Z = A + B

ALL = 2 * (N - 1)

c = collections.Counter(Z)

V = list(c.values())
SUM = 0

for i in range(len(V)):
    SUM = SUM + V[i]


ANS = (ALL - SUM) // 2

print(ANS)

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:
import copy

N, M = map(int, input().split())
c = [[] for _ in range(N)]
m = [-1] * N

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

for i in range(N):
  l = copy.copy(c[i])
  while len(l) > 0:
    t = l.pop()
    if m[t] == -1:
      m[t] = i
      l = l + c[t]
        
print(m.count(-1))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N,M = map(int, input().split())
A, B = [0]*M, [0]*M
C = [[] for _ in range(N+1)]

for i in range(M):
  A[i], B[i] = sorted(list(map(int,input().split())))
  C[A[i]].append(B[i])
  C[B[i]].append(A[i])
ans=0
for i in range(1, N+1):
    if C[i]:
        continue
    else:
        ans += 1
print(ans)

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)
      break
    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:
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()
for i in inp:
    a,b = i
    E[b-1] = E[a-1]
count = 0
for i,e in enumerate(E):
    if i == e:
        count += 1

print(count-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
import statistics
import itertools
# a,b=map(int,input().split())
# b=int(input())
# c=[]
# for i in a:
#     c.append(int(i))
N,M= map(int,input().split())
# f = list(map(int,input().split()))
#g = [list(map(lambda x: '{}'.format(x), list(input()))) for _ in range(a)]
# h = []
# for i in range(a):
#     h.append(list(map(int,input().split())))
# a = [[0] for _ in range(H)]#nizigen
lis=[list(map(int,input().split())) for i in range(M)]

print(N-M-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)


def dfs(idx):
    for x in arr[idx]:
        if not vis[x]:
            vis[x] = True
            dfs(x)


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

arr = [[] * (n + 1) for _ in range(n + 1)]
vis = [False] * (n + 1)

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

ans = 0

dfs(1)
for i in range(2, n + 1):
    if not vis[i]:
        vis[i] = True
        dfs(i)
        ans += 1
for i in range(1, n + 1):
    if not vis[i]:
        ans += 1
print(ans)