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:
from collections import deque
n,m=map(int,input().split())
data=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  data[a-1].append(b-1)
  data[b-1].append(a-1)
flag=[0]*n
cnt=[0]*n
for i in range(n):
  if flag[i]==0:
    cnt[i]+=1
    flag[i]=1
    que=deque([i])
    while que:
      h=que.popleft()
      for u in data[h]:
        if flag[u]==0:
          cnt[i]+=1
          flag[u]=1
          que.append(u)
print(n-max(cnt))

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
a_list = set()
for i in range(M):
    a_list.add(tuple(map(int, input().split())))

print(N-(len(a_list)+3))

Submission status: Wrong Answer

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

roads = []
checkpoints = [0] * n
countMakeRoads = -1

for i in range(m):
    aiBi = list(map(int, input().strip().split()))
    roads.append(aiBi)

for i in range(n):
    if checkpoints[i] == i+1:
        continue
    else:
        canBreak = False
        for j in range(m):
            if roads[j][0] == i+1:
                if roads[j][1] == checkpoints[roads[j][1]-1]:
                    canBreak = True
                    break;
        if canBreak == True:
            break;
        countMakeRoads += 1
        checkpoints[i] = i+1
        for k in range(m):
            if roads[k][0] == i+1:
                checkpoints[roads[k][1] - 1] = roads[k][1]
print(countMakeRoads)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m = (int(i) for i in input().split(" "))
l=np.array([], dtype="int64")
root=np.arange(1,n+1)
for i in range(m):
    k=[int(i) for i in input().split(" ")]
    l=np.append(l,k)

l=np.unique(l)
j = n-sum(np.in1d(root,l))
print(j)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
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

   
print(max(group)+ans)

Submission status: Wrong Answer

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

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

cities = [[0]*N]*N
# print(cities)

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

n, labels = connected_components(csr_matrix(cities))
print(n-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
a_list = set()
for i in range(M):
    a_list.add(tuple(map(int, input().split())))

print(N-len(a_list)-1)

Submission status: Wrong Answer

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

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

set_a_b = set(a_b)
len_set = len(set_a_b)

if (n-len_set)%2 == 0:
    ans = (n-len_set)//2
else:
    ans = (n-len_set)//2 + 1

print(ans)

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]

print(len(set(map(id, G.values())))-1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=set()
for i in range(m):
    x,y=map(int,input().split())
    l.add(x-1)
    l.add(y-1)
out=0
for i in range(n):
    if i not in l:
        out+=1
print(out)

Submission status: Wrong Answer

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

#都市情報を初期化
for i in range(1,N+1):
  city[i]=i
  
#都市番号の小さい方を根としてUnionFind木を作成(大きい方を書き換える)
for i in range(M):
  A,B=map(int,input().split())
  
#ルートチェック
  if city[A]!=A:
    root=city[A]
    while city[root]!=root:
      root=city[root]
    city[A]=root
  
  if city[B]!=B:
    root=city[B]
    while city[root]!=root:
      root=city[root]
    city[B]=root

#結合
  if city[A]!=city[B]:
    city[max(A,B)]=city[min(A,B)]

#木が何種類あるかチェック
ck=[0]*(N+10)
for i in range(1,N+1):
  if ck[city[i]]==0:
    ck[city[i]]=1
    
Ans=sum(ck)-1 #木の数-1=必要な道路数

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(y))
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:
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:
        mini = min(island[a],island[b])
        maxa = max(island[a],island[b])
        for x in island:
            if x == maxa:
                x = mini
        land_num -= 1
print(land_num-1)

Submission status: Wrong Answer

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

list = set()
com = 0
for i in range(m):
  a,b = map(int,input().split())
  list.add(a)
  list.add(b)
  if a not in list and b not in list:
    com +=1
    
  
    list.add(a)
    list.add(b)
print(n-len(list)+com)

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[''.join(input().split())] = True

c = 0
for i in range(1, N):
  d = False
  if str(i)+str(i+1) not in AB:
    c += 1
print(c)

Submission status: Wrong Answer

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

list = set()
com = 0
for i in range(m):
  a,b = map(int,input().split())
  list.add(a)
  list.add(b)
  if a not in list and b not in list:
    com +=1
    
  
    list.add(a)
    list.add(b)
print(n-len(list))

Submission status: Wrong Answer

Solution code:
"""
N：都市の数
M:双方向道路の数
"""
import copy


class DisjointSet:
    def __init__(self, size):
        self.rank = [0] * size  # rank[x]：ノードxを木の親としたときの木の高さ
        self.p = [0] * size  # p[x]：ノードxの親

        for i in range(N):
            self.p[i] = i  # 自分自身を親
            self.rank[i] = 0  # 最初は自分だけなので木の高さは0

    def unite(self, x, y):  # 結合
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x_root, y_root):  # x_root(y_root):x(y)が属する集合の親
        if (self.rank[x_root] > self.rank[y_root]):
            self.p[y_root] = x_root
        else:
            self.p[x_root] = y_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[y_root] += 1

    def findSet(self, x):  # xが属する集合の親を返す
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])

        return self.p[x]


N, M = map(int, input().split())
ds = DisjointSet(N)
parents = []

for _ in range(M):
    A, B = map(int, input().split())
    ds.unite(A-1, B-1)  # 都市Aと要素Bを結合

parents = copy.copy(ds.p)

print(len(list(set(parents))) - 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]
        
zero_count = 0
for i in range(N):
    if table[i] == 0:
        zero_count += 1

if zero_count != 0:
    ans = (len(set(table))-1) + zero_count - 1 
else:
    ans = len(set(table))-1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(n) for n in input().split()]
V = {}
for n in range(1, N+1):
    V[n] = 1
for m in range(M):
    a, b = [int(n) for n in input().split()]
    V[a] = 0
    V[b] = 0
print(sum(V.values()))

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split())
s = [list(map(int,input().split()))for i in range(b)]
w = []
for i in range(b):
    if s[i][0] != w:
        w.append(s[i][0])
    if s[i][1] != w:
        w.append(s[i][1])
num = a-len(w)
if num != 1:
    print(num-1)
else:
    print(1)

Submission status: Wrong Answer

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


L = []
for i in range(1, N+1):
  L.append(i)


for i in range(M):
  if A[i] in L:
    L.remove(A[i])
for i in range(M):
  if B[i] in L:
    L.remove(B[i])
print(len(L))

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)
    
A = len(list(set(A)))
B = len(list(set(B)))
cnt = max(A, B)
print((N-1)-cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
a_list = set()
for i in range(M):
    a_list.add(tuple(map(int, input().split())))

print(N-(len(a_list)+1))

Submission status: Wrong Answer

Solution code:
def s(way):
    global w
    w2 =[]
    for i in way:
        c[i] =1
        for j in w[i]:
            if c[j] == 0:
                c[j] = 1
                w2.append(i)
            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:
#!/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]

print(1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
town = [0] * n
island = n

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

print(island - 1)

Submission status: Wrong Answer

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

ans += a.count(0)
b = a.count(1)
ans += b//2 -1
print(ans)

Submission status: Wrong Answer

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


x = [ 1 ] * n

for i in range( m ):
    ai, bi =  map( int, input().split() )
    if x[ ai-1 ] == 1 and x[ bi-1 ] == 1:
        x[ bi-1 ] = 0
    elif x[ ai-1 ] == 1 and x[ bi-1 ] == 0:
        x[ ai-1 ] = 0
    elif x[ ai-1 ] == 0 and x[ bi-1 ] == 1:
        x[ bi-1 ] = 0


print( x.count( 1 ) - 1 )

Submission status: Wrong Answer

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

cityGroupList = []
cityGroup = []
cityGroup.append(loadList[0][0])
cityGroup.append(loadList[0][1])
cityGroupList.append(cityGroup)

for oneLoad in loadList:
  isAdded = False
  for oneCityGroup in cityGroupList:
      if oneLoad[0] in oneCityGroup or oneLoad[1] in oneCityGroup:
        oneCityGroup.append(oneLoad[0])
        oneCityGroup.append(oneLoad[1])
        isAdded = True
        break
  if not isAdded:  
    newCityyGroup = []
    newCityyGroup.append(loadList[0][0])
    newCityyGroup.append(loadList[0][1])
    cityGroupList.append(newCityyGroup)
    isAdded = False

print(len(cityGroupList))

Submission status: Wrong Answer

Solution code:
N, M = [int(n) for n in input().split()]
V = {}
for n in range(1, N+1):
    V[n] = 1 if n!=1 else 0
for m in range(M):
    a, b = [int(n) for n in input().split()]
    V[a] = 0
    V[b] = 0
print(sum(V.values()))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
_ = [map(int, input().split()) for _ in range(M)]
print(N - M * 2)

Submission status: Wrong Answer

Solution code:

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

    print(N-1-M)


main()

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(i) for i in input().split()])

print(n - len(roads))

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
if N - M > 1:
    for p in range(N):
        if p+1 not in C:
            counts += 1

if counts < N-1:
    print(N-1-counts)
else:
    print(counts)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
xy = [map(int, input().split()) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]
list_diff = list(set(range(1,N+1)) ^ set(x+y))
print(len(list_diff))

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)]
if N-M-1>=0:
    print(N-M-1)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
#https://note.nkmk.me/python-union-find/
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())


def main():
    N, M = [int(i) for i in input().split()]
    uf = UnionFind(N)
    for i in range(M):
        A,B = [int(i) for i in input().split()]
        uf.union(A-1,B-1)
    print(N-uf.group_count())

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

print(n-m-1)

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(''.join(input().split()))

c = 0
for i in range(1, N):
  d = False
  if str(i)+str(i+1) not in AB:
    c += 1
print(c)

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)
    
for x in list(set(A)):
    na.remove(x)
for y in list(set(B)):
    nb.remove(y)
print(min(len(na), len(nb)))

Submission status: Wrong Answer

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

check = []
for ab in AB:
  check += ab
check = list(set(check))

print(N - len(check))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
road = [0]*m
town = range(n)
ask = []

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

for y in range(m):
  ask +=road[y]
diff = list(set(town) ^ set(ask))
print(diff)

for j in range(m):
  for k in range(m):
    if len(list(set(road[j]) & set(road[k])))>0 and (j!=k) 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)

print(len(b)-2+len(diff))

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] = 0
    for _ in range(m):
        first, second = map(int, input().split())
        d[first] +=1
        d[second] +=1
    for city in d:
        if d[city]==0:
            cnt +=1
    return cnt



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

Submission status: Wrong Answer

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

if N - M >=2:
	print(A)
else:
	print("0")

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)-2
num2=road.count(2)

if num1>0:
    print(num1+num2-1)
else:
    print(num2)

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] = 0
    for _ in range(m):
        first, second = map(int, input().split())
        d[first] +=1
        d[second] +=1
    for city in d:
        print(d[city])
        if d[city]==0:
            cnt +=1
    return cnt



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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = [list(map(int, input().split())) for l in range(M)]
sl = sorted(l)
flag = [0 for i in range(N)]
ans = 0
i = 1
for s in sl:
    if s[0] == i:
        flag[i - 1] = 1
        flag[s[1] - 1] = 1
    else:
        if flag[s[0] - 1] != 1 and flag[s[1] - 1] != 1:
            ans += 1
        flag[s[0] - 1] = 1
        flag[s[1] - 1] = 1
        i = s[0]

print(ans + flag.count(0))

Submission status: Wrong Answer

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

ans = n -m -1

if ans < 0:
  print(0)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
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
    abs[_a] =tmp
    abs[_b] =tmp
  elif abs[_a]==0 and not abs[_b] ==0:
    tmp2 = tmp2-1
    abs[_a] = abs[_b]
  elif not abs[_a]==0 and abs[_b] ==0:
    tmp2 = tmp2-1
    abs[_b] = abs[_a]
  else:
    ans = ans -1
ans = ans + tmp2
print(ans)

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()))
town = set()
num = 0
for i in range(M):
    a,b = list(map(int,input().split()))
    town.add(a)
    town.add(b)
    if a in town or b in town:
        continue
    else:
        num +=1 
        
sorted(town)
town = list(town)    




if N == 2:
    print(0)

else:
    p = N-len(town)+num-1
    print(int(p*(p-1)/2)+1)

Submission status: Wrong Answer

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

ans = n-1-m
if ans < 0:
    ans = 0

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    edge = [[] for _ in range(N+1)]
    for a, b in AB:
        edge[a].append(b)
        edge[b].append(a)
    visited = {0}
    count = 0
    print(edge)
    for i in range(len(edge)):
        if not i in visited:
            count+=1
            visited.add(i)
            print(i)
        for j in edge[i]:
            if not j in visited:
                #count += 1
                visited.add(j)
                print(i,j,visited)

    return count-1

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

Submission status: Wrong Answer

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

ans = []

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

ans = set(ans)

print(n - 1 - len(ans))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(m):
    x,y=map(int,input().split())
    l.append(x-1)
    l.append(y-1)
out=0
for i in range(n):
    if i not in l:
        out+=1
print(out)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = list(range(1, N + 1))
for i in range(M):
  a, b = map(int, input().split())
  if a in l:
    l.remove(a)
  if b in l:
    l.remove(b)

print(len(l))

Submission status: Wrong Answer

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

acc = []
count = 0

for i in range(m):
  x,y = list(map(int,input().split()))
  acc.append(x)
  acc.append(y)

acc = set(acc)

count += (m-1) - (2*m - len(acc))

whole = {x for x in range(1,n+1)}

missed = whole.difference(acc)

count += len(missed)

print(count)

Submission status: Wrong Answer

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

if N%2 == 1:
  print (int((N-1)/2))
else:
  print(int(N/2))

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(a)
    ans[b-1].append(b)
    

count = 0
for i in range(n):
    if len(ans[i]) < 2:
        count += 2 - len(ans[i])
        
print(int((count/2)-1))

Submission status: Wrong Answer

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

for _ in range(m):
    a = map(str, input().split())
    tmp.append(''.join(a))

tmp_set = set(tmp)
ans = n - len(tmp_set) - 1
print(ans)

Submission status: Wrong Answer

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

print((N - 1) - M)

Submission status: Wrong Answer

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

print(N-(M+1))

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().strip().split()))
cnt = 0
for i in range(m):
	a, b = list(map(int, input().strip().split()))
	cnt += 1

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

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



uf=UnionFind(a+1)

for i in range(b):
    uf.union(n[i][0],n[i][1])
print(a-uf.group_count()+1)

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(a)
    ans[b-1].append(b)
    

count = 0
for i in range(n):
    if len(ans[i]) != 2:
        count += 2 - len(ans[i])
        
print(int((count/2)-1))

Submission status: Wrong Answer

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

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
  elif town[a-1] == 1 and town[b-1] == 1:
    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:
N, M = (int(i) for i in input().split())
AB = [input().split() for i in range(M)]

city = set(map(str, list(range(1, N+1))))
route = set(sum(AB, []))
print(len(city - route))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m = list(map(int,input().split()))

d = {}
for i in range(m):
    fr, to = list(map(int,input().split()))
    d[fr] = d.get(fr, []) + [to]
    d[to] = d.get(to, []) + [fr]
    
visited = [0 for i in range(n+1)]

def connect(node, i):
    visited[node] = i
    
    if node in d:
        for neig in d[node]:
            if visited[neig] == 0:
                connect(neig, i)
ans = 1
for key in range(1,n+1):
    if visited[key] == 0:
        connect(key, ans)
        ans += 1

print(ans-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
n = list(i+1 for i in range(N))
count = 0

for _ in range(M):
    A, B = map(int, input().split())
    if A in n:
        n.remove(A)
    if B in n:
        n.remove(B)

print(len(n))

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
if N - M > 1:
    for p in range(N):
        if p+1 not in C:
            counts += 1
print(counts)

Submission status: Wrong Answer

Solution code:
import math

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

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

set_a_b = set(a_b)
len_set = len(set_a_b)
ans = math.ceil((n - len_set)/2)

print(ans)

Submission status: Wrong Answer

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

num = 1
for i in range(len(town)-1):
    if town[i] + 1 != town[i+1]:
        num += 1


if N == 2:
    print(0)

else:
    p = N-len(town)+num-1
    print(int(p*(p-1)/2)+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:
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)
print(n+1-count)