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

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_dsu_code = """
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))
"""

atcoder.dsu = types.ModuleType('atcoder.dsu')
exec(_atcoder_dsu_code, atcoder.dsu.__dict__)
dsu = atcoder.dsu

# from atcoder import dsu
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ds = dsu.DSU(n)
for i in ab:
    ds.merge(i[0]-1,i[1]-1)
    
s = ds.groups()
ans = 0
for i in s:
    if len(i)==1:
        ans+=1
print(ans)

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)

print(uf.group_count())

Submission status: Wrong Answer

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

City_list = [[i] for i in range(N)]
ans = N - 1 - M

for i in range(M):
    Ai, Bi = map(int, input().split())

    if City_list[Ai - 1] == City_list[Bi - 1]:
        ans += 1
    else:
        City_list[Ai - 1] = City_list[Ai - 1] + City_list[Bi - 1]
        City_list[Bi - 1] = City_list[Ai - 1]

print(ans)

Submission status: Wrong Answer

Solution code:
import statistics
N,M=map(int,input().split())
A=[0]*M;B=[0]*M
par=[-1]*N
 
def find(x):
    if par[x] < 0:
        return x
    else:
        tank = []
        while par[x] >= 0:
            tank.append(x)
            x = par[x]
        for elt in tank:
            par[elt] = x
        return x
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        par[x] += par[y]
        par[y] = x
        return True
 
for i in range(M):
  A[i],B[i]=sorted(map(int,input().split()))
  unite(A[i]-1,B[i]-1)
 
print(min(par)*-1-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

list = set()

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

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
    if dp[i] > 1:
        ans += dp[i] -1

print(ans)

Submission status: Wrong Answer

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

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())
  r[a-1]+=1
  r[b-1]+=1
ma = max(r)
if ma>=n-1:
  print(0)
else:
  print(n-1-ma)

Submission status: Wrong Answer

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

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

for i in range(n):
    ro[i]=1
i
def root(i):
    if par[i]==i:
        return i
    else:
        a=root(par[i])
        par[i]=a
        return a

def unite(x,y):
    rx=root(x)
    ry=root(y)
    if rx!=ry:
        par[rx]=ry
        ro[ry]+=ro[rx]
        ro[rx]=0

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

from collections import Counter as cnt

ans=dict(cnt(ro.values()))

print(len(ans)-1)

Submission status: Wrong Answer

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

t = set(t)
#print(t)
print(max(n-len(t),n-m-1))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ans = (n - 1) - m
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
a,b = list(map(int,input().split()))
town = {a,b}
num = 1
for i in range(M-1):
    a,b = list(map(int,input().split()))
    if (a in town or b in town):
        town.add(a)
        town.add(b)
    else:
        town.add(a)
        town.add(b)
        num += 1
    
sorted(town)
print(N-len(town)+num-1)

Submission status: Wrong Answer

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

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

cities=set(path)
print(N-len(cities))

Submission status: Wrong Answer

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

t = set(t)
print(t)
print(max(n-len(t),n-m-1))

Submission status: Wrong Answer

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

for _ in range(m):
  a,b = map(int, input().split())
  roads.add(a)
  roads.add(b)
print(n - len(roads))

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]]):
		city[b[i]]=city[a[i]]
	else:
		city[a[i]]=city[b[i]]
print(ans+city.count(0)-2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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[y] = x
    
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:
N, M = map(int, input().split())
S = [[0]]*N

for i in range(N):
  S[i] = [i]

m = 0
for i in range(M):
  A, B = map(int,input().split())
  S[A-1]+=[*S[B-1]]
  S[B-1]+=[*S[A-1]]
  m = max(m,len(set(S[A-1])),len(set(S[B-1])))

print(N-m)

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:
        ans += 1
    a_list.add(x)
    for z in y:
        a_list.add(z)
        # print(a_list)
    # print(ans)
    # print("----")
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

l=[0]*(n+1)

for i in range(m):
    a,b=map(int,input().split())
    l[a]=1
    l[b]=1
counter=0
for i in range(1,n+1):
    if l[i]==0:
        counter+=1
print(counter)

Submission status: Wrong Answer

Solution code:
def solve(city_arr, road_arr):   
    road_set = set(road_arr)
    tmp_cities = list(road_set)
    tmp_cities.sort()
    counta = 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:
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 unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y

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

import collections
c = collections.Counter(par)
print(len(c)-2)

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    g = [-1]*(n+1)
    gidx = 0
    group = [-1]*(n+1)
    idx = 0
    for i in range(m):
        a, b = map(int, input().split())
        ak,bk = group[a], group[b]
        if ak>=0 and bk>=0:
            if ak != bk:
                g[bk] = g[ak]
        elif ak<0 and bk>=0:
            group[a] = bk
        elif ak>=0 and bk<0:
            group[b] = ak
        else:
            group[a] = group[b] = idx
            idx += 1
            g[idx] = gidx
            gidx += 1

    # print(g)
    # print(group)
    
    # 道でつながるグループの数 / -1があるのでのぞく
    ans = len(set(g))-1
    # -1は道がない
    ans += len([v for v in group[1:] if v==-1])-1
    print(ans)

main()

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




import math


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)

x=uf.group_count()

print(math.ceil(math.log(x,2)))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

ans = min(uf.parents)

print(-ans-1)

Submission status: Wrong Answer

Solution code:
#                               #
    # author : samars_diary #
    # 26-09-2020 │ 17:45:50 #
#                               #

import sys, os.path

#if(os.path.exists('input.txt')):
    #sys.stdin = open('input.txt',"r")
    #sys.stdout = open('output.txt',"w")

sys.setrecursionlimit(10 ** 5)

def mod(): return 10**9+7
def ii(): return int(sys.stdin.readline())
def si(): return sys.stdin.readline().strip()
def li(): return list(sys.stdin.readline().strip())
def mii(): return map(int, sys.stdin.readline().split())
def lii(): return list(map(int, sys.stdin.readline().strip().split()))

#print=sys.stdout.write

def solve():
    a, b = mii() ; e = []
    for _ in range(b):
        c,d = mii()
        e.append(c); e.append(d)
    print(a-len(set(e)))
         


for _ in range(1):
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:

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

def unite(x,y):
    x, y = find(x), find(y)
    if x == y:
        return False
    
    if par[x] > par[y]:
        x,y = y,x
    par[x] += par[y]
    par[y] = x
    return True

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

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

par = [-1]*n

for a, b in ab:
    unite(a, b)

nset=set()
for i in range(n):
    if not find(a) in nset:
        nset.add(i)
print(len(nset))

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [0] * 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

        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
        else:
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

uf = UnionFind(n)

for _ in range(m):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    uf.union(x, y)

print(len(set(uf.parents))-1)

Submission status: Wrong Answer

Solution code:
class union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

    def find_root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.find_root(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        x=self.find_root(x)
        y=self.find_root(y)
        

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1


N,M = map(int,input().split())
g = union_find(N)
group = 0
for i in range(M):
  A,B= map(int,input().split())
  g.unite(A,B)

print(g.root)

for j in g.root:
  if j < 0:
    group += 1

print(group - 2)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
D = [input().split() for l in range(M)]

max_line = N-1

print(N-1-M)

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.pop(0)
par=set(par)
print(len(par)-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 _ in range(m):
    a,b = map(int,input().split())
    uf.union(a-1,b-1)

ans = 0
for i in range(n):
    ans = max(ans,uf.size(i))

print(n-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((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:
        chk += 1
        cnt[a] = chk
        cnt[b] = chk
    elif cnt[a] > 0 or cnt[b] > 0:
        cnt[a] = max(cnt[a], cnt[b])
        cnt[b] = max(cnt[a], cnt[b])
print(len(set(cnt[1:]))-1)

Submission status: Wrong Answer

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

alone = [i for i, v in enumerate(town) if v == 0]
island += len(alone)

print(island-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 not in visited: cnt+=1
    visited.add(i)
    if i in a_s:
        lis=path[i]
        for j in lis: visited.add(j)
print(cnt-1)

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    g = [-1]*(n+1)
    gidx = 0
    group = [-1]*(n+1)
    idx = 0
    for i in range(m):
        a, b = map(int, input().split())
        ak,bk = group[a], group[b]
        if ak>=0 and bk>=0:
            if ak != bk:
                g[bk] = g[ak]
        elif ak<0 and bk>=0:
            group[a] = bk
        elif ak>=0 and bk<0:
            group[b] = ak
        else:
            group[a] = group[b] = idx
            idx += 1
            g[idx] = gidx
            gidx += 1

    print(g)
    print(group)
    
    # 道でつながるグループの数 / -1があるのでのぞく
    ans = len(set(g))-1
    # -1は道がない
    ans += len([v for v in group[1:] if v==-1])-1
    print(ans)

main()

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

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())
for i in range(M):
    listAB = [list(map(int, input().split()))]
ideal = N - 1
if ideal - M <= 0:
    print(0)
else:
    print(ideal - M)

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

ns = list(range(1,n+1))

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

count = 0

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

print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
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())
uni = UnionFind(n)
for i in range(m):
    a, b = ab[i]
    uni.union(a, b)
    print(uni.group_count() - 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
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)]

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

nodes = [i for i in range(n)]
for a, b in ab:
    nodes[b-1] = None

ans = n - nodes.count(None) - 1

print(ans)

Submission status: Wrong Answer

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

print((n-1)-m)

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)

Submission status: Wrong Answer

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

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

print(N - len(set(L)))

Submission status: Wrong Answer

Solution code:
def find(x):
    if par[x] < 0:
        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
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x


N, M = map(int, input().split())
par = [-1 for i in range(N)]

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

cnt = -1
num = {0}

for i in par:
  if i > 0:
    cnt += 1

print(cnt)