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())
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())
#  print(A,B)

#ルートチェック
  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]:
    wk=min(city[A],city[B])
    city[A]=wk
    city[B]=wk
#    print(city[max(A,B)])
#    print(city[min(A,B)])
    
#print(city)
    
#木が何種類あるかチェック
ck=[0]*(N+10)
for i in range(1,N+1):
  if ck[city[i]]==0:
    ck[city[i]]=1
    
#print(ck)
Ans=sum(ck)-1 #木の数-1=必要な道路数

print(Ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0 for i in range(M)]
B = [0 for i in range(M)]
for i in range(M):
  A[i], B[i] = map(int, input().split())
A_s = set(A)
B_s = set(B)
city = A_s.union(B_s)

rem = N - len(city)
print(rem//2 + 1)

Submission status: Wrong Answer

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

visited = dict()
count = -1
total = []

for i in range(m):

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

  total.append(x)

total.sort()

for z in total:

  x,y = z

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

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

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

Submission status: Wrong Answer

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

A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
S = set()
for i in range(M):
    A[i] , B[i] = map(int, input().split())
    S.add(A[i])
    S.add(B[i])
S = list(S)
Connected = [1 for i in range(0,N)]
for i in S:
    Connected[i-1] = 0
result = 0
for i in range(len(Connected)):
    result += Connected[i]

print(result)

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

ans = 0

for i in range(n):
  if i not in a and i not in b:
    ans += 1
  i += 1

print(ans)

Submission status: Wrong Answer

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


test = sorted(list(set(C)))

ans = N - len(test)

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
def run(n_m, an_bn):
    '''

    '''
    # if n_m[0] - 1 <= len(an_bn):
    #     print(0)
    # else:
    #     print(n_m[0] - 1 - len(an_bn))

    # print(set(list(itertools.chain.from_iterable(an_bn))))
    cities = set(list(itertools.chain.from_iterable(an_bn)))
    if n_m[0] - len(cities) <= 0:
        print(0)
    else:
        print(n_m[0] - len(cities))




    







if __name__ == '__main__':
    n_m = list(map(int, input().split()))
    an_bn = list(map(int, input().split()) for _ in range(n_m[1]))

    run(n_m, an_bn)

Submission status: Wrong Answer

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

road = [[0 for j in range(N)] for i in range(N)]
count = 0

print(road)

for n in AB:
    road[n[0]-1][n[1]-1] = 1
    road[n[1]-1][n[0]-1] = 1

print(road)
for n in road:
    if sum(n) == 0:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
import collections
B=[]
C=[]
for i in range(M):
    B.append(A[i][0])
    C.append(A[i][1])
tmp1=len(collections.Counter(B))
tmp2=len(collections.Counter(C))
if tmp1>=tmp2:
    print(N-tmp1-1)
else:
    print(N-tmp2-1)

Submission status: Wrong Answer

Solution code:
from scipy.special import comb

N, M = [int(i) for i in input().split()]
A = {}
B = {}

for i in range(M):
  e = input().split()
  A[e[0]] = True
  B[e[1]] = True

c = 0
for i in range(1, N):
  d = False
  if not (str(i) in A and str(i+1) in B) or (str(i) not in B or str(i+1) not in B):
    c += 1
    A[str(i)] = True
    B[str(i+1)] = True
print(c)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
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:
        return 0
    par[x] = y
for i in range(M):
    a,b = map(int,input().split())
    a-=1
    b-=1
    unite(a,b)
#print(par)
print(len(set(par))-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.append(A)
  b.append(B)

print(n-1-m)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
import collections
B=[]
C=[]
for i in range(M):
    B.append(A[i][0])
    C.append(A[i][1])
tmp1=len(collections.Counter(B))
tmp2=len(collections.Counter(C))
if tmp1>=tmp2:
    print(N-tmp1+1)
else:
    print(N-tmp2+1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
L=[]
s=N-1
for i in range(M):
    A,B=map(int,input().split())
    if A not in L or B not in L:
        s-=1
    L.append(B)
print(s)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from scipy.special import comb

N, M = [int(i) for i in input().split()]
A = {}
B = {}

for i in range(M):
  e = input().split()
  A[e[0]] = True
  B[e[1]] = True

c = 0
for i in range(1, N):
  d = False
  if not (str(i) in A and str(i+1) in B) and (str(i) not in B or str(i+1) not in B):
    c += 1
    A[str(i)] = True
    B[str(i+1)] = True
print(c)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
d=defaultdict(list)
for i in range(m):
    start,end=map(int,input().split())
    if(start not in d.keys()):
        d[start]=[end]
    else:
        d[start].append(end)
visited=[0]*n
visited[0]=1
for key,value in d.items():
    if(visited[key-1]>0):
        for v in value:
            visited[v-1]+=1
print(visited.count(0))

Submission status: Wrong Answer

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

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())
A=[list(map(int,input().split())) for i in range(M)]
import collections
B=[]
C=[]
for i in range(M):
    B.append(A[i][0])
    C.append(A[i][1])
tmp1=len(collections.Counter(B))
tmp2=len(collections.Counter(C))
if tmp1>=tmp2:
    print(N-tmp1)
else:
    print(N-tmp2)

Submission status: Wrong Answer

Solution code:
n, m = input().split()
a_set = set()
b_set = set()

for _ in range(0,int(m)):
	a, b = input().split()
	a_set.add(int(a))
	b_set.add(int(b))

all_set = a_set.union(b_set)

print(int(n)-len(all_set))

Submission status: Wrong Answer

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, 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
        
n,m=input2()
AB=[input_array() for _ in range(m)]
D=[[0]*n for _ in range(n)]

uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0

print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(100000)

import numpy as np


def main():
    n_num, m_num = map(int, input().split())
    # road = np.zeros((n_num, n_num), dtype='int32')
    c_map = []
    for _ in range(n_num):
        c_map.append([])
    # print(c_map)

    for _ in range(m_num):
        a, b = map(int, input().split())
        if a > b:
            a, b = b, a
        # road[a-1][b-1] = 1
    c_map[a-1].append(b-1)
    c_map[b-1].append(a-1)
    # print(c_map)

    city_info = np.zeros(n_num, dtype='int32')
    land_city = 0

    def move(a, b):
        if a in c_map[b]:
            return 1
        else:
            return 0

    def recr(c):
        city_info[c] = 1
        for n in c_map[c]:
            if city_info[n] == 0:
                if move(c, n) == 1:
                    recr(n)

    for n in range(n_num):
        if city_info[n] == 0:
            land_city += 1
            recr(n)

    print(land_city - 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

ab = [set(map(int, input().split())) for _ in range(m)]

n_set = {n for n in range(1,n)}

bubun = []
bubun.append(ab[0])
n_set -= ab[0]

for i in range(1,m-1):
    n_set -= ab[i]
    for j in range(len(bubun)):
        if not ab[i].isdisjoint(bubun[j]):
            bubun[j] |= ab[i]
        else:
            bubun.append(ab[i])

size_old = len(bubun)
while True:
    for i in range(len(bubun)):
        for j in range(i+1, len(bubun)):
            if not bubun[i].isdisjoint(bubun[j]):
                bubun[i] |= bubun[j]
                del bubun[j]

    if len(bubun) != size_old:
        size_old = len(bubun)
        countinue
    else:
        break

print(len(n_set) + len(bubun) - 1)

Submission status: Wrong Answer

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

roads = []

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

print(n - len(set(roads)))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
n, m =  map(int, input().split()) # nは頂点の数、mは辺の数
pic = [[] for _ in range(n+1)] # 隣接リスト_初期化 ※※※
 
for _ in range(m): # 隣接リスト_取り込み
    a, b = map(int, input().split())
    pic[a].append(b) # ※※※
    pic[b].append(a) # ※※※
#print(pic)
 
from collections import deque
 
def BFS(u): # 'u'を開始位置として各頂点までの距離を探索する関数_dis → 親ノードを探索して'ans'に記録
    queue = deque([u]) # dequeオブジェクトとして初期化、初期値は開始位置の'u'のみ
    dis = [None] * (n+1) # uからの距離を全ノード分初期化 ※※※
    dis[u] = 0 # 開始位置'u'の距離は'0'
 
    while queue:
        v = queue.popleft() # 'v'に探索候補のノードを popleft
        for i in pic[v]: # pic[v]: 探索候補のノードに隣接するノードのリスト
            if dis[i] is None:
                dis[i] = dis[v] + 1 # 'u'からの距離を記録
                queue.append(i)
    return dis[1:]

tmp=BFS(1)
ans=tmp.count(None)

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
L=[]
s=N-1
for i in range(M):
    A,B=map(int,input().split())
    if A not in L :
        if B not in L:
            s-=1
    L.append(B)
print(s)

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())
#  print(A,B)

#ルートチェック
  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)]
#    print(city[max(A,B)])
#    print(city[min(A,B)])
    
#print(city)
    
#木が何種類あるかチェック
ck=[0]*(N+10)
for i in range(1,N+1):
  if ck[city[i]]==0:
    ck[city[i]]=1
    
#print(ck)
Ans=sum(ck)-1 #木の数-1=必要な道路数

print(Ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    connect_str = "0" * N

    max_road_num = 0
    for i in range(M):
        A, B = map(int, input().split())
        A = A - 1
        B = B - 1
        
        A_road_num = connect_str[A]
        B_road_num = connect_str[B]

        if A_road_num == "0" and B_road_num == "0":
            max_road_num = max_road_num + 1
            connect_str = connect_str[:A] + str(max_road_num) + connect_str[A+1:]
            connect_str = connect_str[:B] + str(max_road_num) + connect_str[B+1:]
        elif A_road_num != "0" and B_road_num == "0":
            connect_str = connect_str[:B] + connect_str[A] + connect_str[B+1:]
        elif A_road_num == "0" and B_road_num != "0":
            connect_str = connect_str[:A] + connect_str[B] + connect_str[A+1:]
        else:
            connect_str = connect_str.replace(str(B_road_num), str(A_road_num))

    answer = 0
    set_connect_str = set(connect_str)
    set_connect_str.discard("0")
    if len(set_connect_str) != 1:
        answer = len(set_connect_str) - 1

    print(answer + connect_str.count("0"))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
prev = [-1] * n
cnt = 0
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)
Max = 0
for i in range(n):
    if len(edges[i]) > Max:
        ind = i
for i in range(n):
    if len(edges[i]) == 0:
        edges[i].append(ind)
        edges[ind].append(i)
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

def find_components(n, connectors):
    g = nx.Graph()
    for i in range(n): g.add_node(i+1)
    g.add_edges_from(connectors)
    print([i for i in nx.connected_components(g)])
    return len(list(nx.connected_components(g)))


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

ans = find_components(n, ab) - 1

print(ans)

Submission status: Wrong Answer

Solution code:
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:
        oneCityGroup.append(oneLoad[1])
        isAdded = True
        break
      if oneLoad[1] in oneCityGroup:
        oneCityGroup.append(oneLoad[0])
        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:
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)
print(num)

Submission status: Wrong Answer

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

count = 0
for v in itertools.combinations(range(1, n+1), 2):
    print(v)
    a, b = v[0], v[1]
    if [a, b] in r:
        continue
    else:
        count += 1
        r.append([a, b])
        r.append([b, a])
        
# print(r)
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
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 group_count(self):
      return len(self.roots())
  def roots(self):
      return [i for i, x in enumerate(self.parents) if x < 0]
              
uf = UnionFind(m)
print(uf.group_count())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class UnionFind:
    pairs = {}
    def __init__(self, n):
        for i in range(n):
            self.pairs[i] = i

    def set(self, s, t):
        if s in self.pairs and self.pairs[s] != s:
            self.pairs[t] = s
        else:
            self.pairs[s] = t

    def root(self, x):
        if self.pairs[x] == x:
            return x
        self.pairs[x] = self.root(self.pairs[x])
        return self.pairs[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry :
            return
        self.pairs[rx] = ry
def main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    for i in range(m):
        s, t = map(int,input().split())
        uf.unite(s-1, t-1)
        #uf.set(s - 1, t - 1)
    print(uf.pairs)
    root = []
    for i in range(n):
        root.append(uf.root(i))
 #       print(i, uf.root(i))
    single_root = set(root)

    print(len(single_root)-1)
main()

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

if __name__=="__main__":
    main()

Submission status: Wrong Answer

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

l = []
for i in range(M):
  a, b = map(int,input().split())
  if a not in l:
    l.append(a)
  if b not in l:
    l.append(b)

print(N - len(l))

Submission status: Wrong Answer

Solution code:
import collections  # すごく便利なモジュール
 
 
# 該当する頂点がないことを示す値
INVALID = -1
 
 
# 幅優先探索用クラス
class BreadthFirstSearch(object):
 
    def __init__(self, max_v, max_e, adj_vertices):
        self.max_v = max_v
        self.max_e = max_e
        self.adj_vertices = adj_vertices
        # 各頂点が訪問済みかを記録するdefaultdict
        # 既定の値はFalse
        self.visited = collections.defaultdict(bool)
        # 各頂点のひとつ前に訪問した頂点を記録するdefaultdict
        # 既定の値はINVALID
        self.pred = collections.defaultdict(lambda: INVALID)
 
    # 与えられた頂点から幅優先探索を開始し、
    # それが属する連結成分が木であるか判定する
    def in_tree(self, start_v):
        self.visited[start_v] = True
        # 両端キューをキューとして使う
        q = collections.deque()
        q.append(start_v)
        while q:
            u = q.popleft()
            for v in self.adj_vertices[u]:
                if self.visited[v]:  # 条件1
                    if self.pred[u] != v:  # 条件2
                        return False
                    else:
                        continue
                self.visited[v] = True
                self.pred[v] = u
                q.append(v)
        return True
 
    # すべての頂点を順に調べ、木を数える
    # 未訪問の頂点についてin_treeによる判定を行う
    def count_trees(self):
        counter = 0
        for u in range(self.max_v):
            if self.visited[u]:
                continue
            if self.in_tree(u):
                counter += 1
        return counter
 
 
def main():
    # 頂点および辺の最大値
    max_v, max_e = map(int, input().split())
    # 隣接リスト
    adj_vertices = collections.defaultdict(list)
    for _ in range(max_e):
        # 入力は1始まりであるので、これを0始まりに変換する
        u, v = map(lambda x: int(x) - 1, input().split())
        adj_vertices[u].append(v)
        adj_vertices[v].append(u)
    bfs = BreadthFirstSearch(max_v, max_e, adj_vertices)
    print(bfs.count_trees()-1)
 
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from scipy.special import comb

N, M = [int(i) for i in input().split()]
A = {}
B = {}

for i in range(M):
  e = input().split()
  A[e[0]] = True
  B[e[1]] = True

c = 0
for i in range(1, N):
  d = False
  if str(i) not in A and str(i+1) not in B:
    c += 1
    A[str(i)] = True
    B[str(i+1)] = True
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)
print(n-len(p)-1-1)

Submission status: Wrong Answer

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

print(str(n - 1 - m))

Submission status: Wrong Answer

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

n, m = map(int,input().split())
abs = [numb(i) for i in range(n+1)]
ans = n-1
for i in range(m):
  _a, _b = map(int,input().split())
  if abs[_a] == abs[_b]:
    pass
  else:
    ans = ans - 1
    abs[_a].n = abs[_b].n 
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((min(a, b), max(a, b)))
AB = sorted(AB, key = lambda x: x[0])

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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

print(count)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
n, m = map(int, input().split())

uf = UnionFind(n)

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

print(n - uf.group_count())