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

roads=[]

for _ in range(m):
  a,b=map(int, input().split())
  if a<b:
  	roads.append([a,b])
  
group=[i for i in range(n)]

group2=[]

while group2!=group:
  group2=group
  for road in roads:
    group[road[1]-1]=group[road[0]-1]

counter=1
for i in range(n-1):
  if group[i]!=group[i+1]:
    counter+=1

print(counter-1)

Submission status: Wrong Answer

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

roads=[]

for _ in range(m):
  a,b=map(int, input().split())
  if a<b:
  	roads.append([a,b])
  else:
    roads.append([b,a])
  
group=[i for i in range(n)]

group2=[]

while group2!=group:
  group2=group
  for road in roads:
    group[road[1]-1]=group[road[0]-1]

counter=1
for i in range(n-1):
  if group[i]!=group[i+1]:
    counter+=1

print(counter-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]
 
for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
ans = 10**18
check = [0]*(N+1)
for i in range(1,N+1):
  st = deque([i])
  check[i] = 1
  cnt = 0
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        check[t] = 1
        st.append(t)
    cnt += 1
  ans = min(ans,N-cnt)
print(ans)

Submission status: Wrong Answer

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

roads=[]

for _ in range(m):
  a,b=map(int, input().split())
  roads.append([a,b].sort())
  
group=[i for i in range(n)]

group2=[]

while group2==group:
  group2=group
  for road in roads:
    group[road[1]]=group[road[0]]

print(group[-1]-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]
 
for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
ans = 0
check = [0]*(N+1)
for i in range(1,N+1):
  st = deque([i])
  check[i] = 1
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        check[t] = 1
        st.append(t)
  ans = max(ans,N-sum(check))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]
 
for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)
ans = 0
check = [0]*(N+1)
for i in range(1,N+1):
  st = deque([i])
  check[i] = 1
  cnt = 0
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        check[t] = 1
        st.append(t)
        cnt += 1
  ans = max(ans,cnt)
print(ans)

Submission status: Wrong Answer

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

print(N-M-1)

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
expect=sum(range(1,N)) - 1
ans=max(0, expect-M)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
#AB=map(int, open(0).read().split())
expect=sum(range(1,N)) - 1
ans=expect-M
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): # どの集合に属しているか（根ノードの番号）
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j): # 二つの集合を併合
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): # 同じ集合に属するかを判定
        return self.find(i)==self.find(j)

    def get_parents(self): # 根ノードの一覧を取得
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

adj = []
N, M = map(int,input().split())
for m in range(M):
    a,b = map(int,input().split())
    adj.append([a-1,b-1])

ans = 0
for i in range(M): # 取り除く辺番号
    uf = UnionFind(N)
    uf.unite(*adj[i])
    
ans=len(set(uf.get_parents())) # 複数の集合にわかれているか確認
    
print (ans-1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): # どの集合に属しているか（根ノードの番号）
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j): # 二つの集合を併合
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): # 同じ集合に属するかを判定
        return self.find(i)==self.find(j)

    def get_parents(self): # 根ノードの一覧を取得
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

adj = []
N, M = map(int,input().split())
for m in range(M):
    a,b = map(int,input().split())
    adj.append([a-1,b-1])

ans = 0
for i in range(M): # 取り除く辺番号
    uf = UnionFind(N)
    for j in range(M):
        if (i==j): # 辺を追加しない（取り除く）
            continue
        uf.unite(*adj[j])
    
    if len(set(uf.get_parents()))!=1: # 複数の集合にわかれているか確認
        ans += 1
print (ans)

Submission status: Wrong Answer

Solution code:
tmp  = input()
tmp = tmp.split(' ')
n,m = [int(s) for s in tmp]
a = list()
b = list()
for i in range(m):
    tmp  = input()
    tmp = tmp.split(' ')
    tmp = [int(s) for s in tmp]
    a.append(tmp[0])
    b.append(tmp[1])
iscity_road = set(a+b)   
iscity = set(range(1,n+1,1))

n_road = iscity - iscity_road

print(len(n_road))

Submission status: Wrong Answer

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

L=[0]*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:
#!/usr/bin/env python

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

class UnionFind():
    def __init__(self, n): 
        self.n = n 
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def root(self, x): 
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 圧縮経路
            return self.par[x]
            # return root(par[x]) # 圧縮しない場合

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

    def unite(self, x, y): 
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: 
            return

        # par[rx] = ry # naiveな連結

        # 低い木を高い方にくっつける。
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.sizes[ry] += self.sizes[rx]
        else:
            self.par[ry] = rx
            self.sizes[rx] += self.sizes[ry]

        # rx木とry木の高さが同じならば、rx木を深くする。
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def size(self, x): 
        '''
        xが属するグループのサイズを返す
        (連結成分の大きさ)
        '''
        return self.sizes[self.root(x)]

    def connected(self):
        '''
        連結成分の数
        '''
        return len(set(self.par))

uf = UnionFind(n)
for i in range(m):
    uf.unite(a[i], b[i])
ans = uf.connected()-1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

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

class UnionFind():
    def __init__(self, n): 
        self.n = n 
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def root(self, x): 
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 圧縮経路
            return self.par[x]
            # return root(par[x]) # 圧縮しない場合

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

    def unite(self, x, y): 
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: 
            return

        # par[rx] = ry # naiveな連結

        # 低い木を高い方にくっつける。
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.sizes[ry] += self.sizes[rx]
        else:
            self.par[ry] = rx
            self.sizes[rx] += self.sizes[ry]

        # rx木とry木の高さが同じならば、rx木を深くする。
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def size(self, x): 
        '''
        xが属するグループのサイズを返す
        (連結成分の大きさ)
        '''
        return self.sizes[self.root(x)]

    def connected(self):
        '''
        連結成分の数
        '''
        return len(set(self.par))

uf = UnionFind(n)
for i in range(m):
    uf.unite(a[i], b[i])

ans = n-uf.connected()
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=input().split()
n=int(N)
m=int(M)
for i in range(1,m+1):
    Ai,Bi=input().split()
print(n-1-m)

Submission status: Wrong Answer

Solution code:
N,M=input().split()
n=int(N)
m=int(M)
for i in range(1,m+1):
    Ai,Bi=input().split()
print(n-2*m)

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

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

Submission status: Wrong Answer

Solution code:
#最も上にいる親をたどる
# xは自分自身の番号を示す。
# r[x]は自分の親を示す。親がいない場合は-1を示す。
def root(x):
  # case parent
  if r[x] < 0:
    return x
  # case child
  else:
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  city_a_par = root(city_a)
  city_b_par = root(city_b)
  #print("x1", x1, "x2", x2)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    if city_a_par == city_b_par:
      pass
    else:
      r[city_b] = city_a_par
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import random
J=998244353
from collections import deque
########################################################
n,m=INPUT()
A=[i for i in range(n+1)]
for i in range(m):
    a,b=INPUT()
    A[a]=min(A[a],A[b])
    A[b]=A[a]
#print(A)
ans=0
x=A[1:]
print(len(set(x))-1)

Submission status: Wrong Answer

Solution code:
#最も上にいる親をたどる
def root(x):
  if r[x] < 0:
    return x
  else:
    #r[x] = root(r[x])
    return root(r[x])

#from operator import itemgetter

n, m = map(int, input().split())
road = [list(map(int,input().split())) for i in range(m)]
#root -1は上がいない、そのほかは親をもちその数字を表す。
r = [-1]*(n+1)

#print(g)

road = sorted(road, key=lambda x:(x[0], x[1]))
#print(r)

group_num = 1;

for i, city in enumerate(road):
  city_a = city[0]
  city_b = city[1]
  #city_a_par = root(city_a)
  #city_b_par = root(city_b)
  #print("x1", x1, "x2", x2)
  
  # 親に子をつなげていく
  # cityに親がいない（自分が親である=-1可能性あるが問題ない）
  if r[city_a] == -1 and r[city_b] == -1:
    # city_bの親をcity_aにする
    r[city_b] = city_a
  # どちらか片方のみが子である
  elif r[city_a] == -1 or r[city_b] == -1:
    # aが子
    if r[city_a] > r[city_b]:
      r[city_b] = r[city_a]
    # bが子
    else:
      r[city_a] = r[city_b]
  # aもbも誰かの子である
  else:
    if r[city_a] > r[city_b]:
      r[city_a] = r[city_b]
    else:
      r[city_b] = r[city_a]
      
del r[0]
#print(group_num-1)
#print(r.count(-1))
#print(r)
print(group_num-1+r.count(-1)-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N, Q = map(int,input().split())
#N,Q=map(int,input().split())
#親のノードを格納　2の親が4のとき par[2]=4
par=[0]
#木の深さを格納　根が2の深さが3の時 rank[2]=3
rank=[0]

#初期化
for i in range(1,N+1):
    par.append(i)
    rank.append(0)

#xの根を探す、同時に通過したノードすべてを根に直接つける
def find(x):
    #xの親がxならば根なのでxを返す
    if par[x]==x:
        return x
    else:
        #違う場合は親の親を捜し自分の親にする
        par[x] = find(par[x])
        #再帰的に行うと根が見つかる
        return par[x]

#xが属する木とyが属する木を併合する
def unite(x,y):
    #根を探す
    root_x=find(x)
    root_y=find(y)

    #根が同じなら元からつながっているので終わり
    if root_x == root_y:
        return

    #ランクが大きい木の根の直下にランクが小さい木を結合
    if rank[root_x] < rank[root_y]:
        par[root_x] = root_y

    else:
        par[root_y] = root_x

    #ランクが等しいときのみランクが増える#なぜ#yにxが結合？
    if rank[root_x]==rank[root_y]:
        rank[root_x]+=1

#xとyが同じ木に存在するかを調べる
def same(x,y):
    return find(x)==find(y)

#main
for i in range(Q):
    a,b=map(int,input().split())
    unite(a, b)
#print(par)
print(len(set(par))-2)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict
class UnionFind:
    def __init__(self, n):
        class KeyDict(dict):
            # 辞書にないときの対応
            def __missing__(self,key):
                self[key] = key
                return key
        self.parent = KeyDict()
        self.rank = defaultdict(int)
        self.weight = defaultdict(int)

    # 根を探す
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            # 経路圧縮
            # 自分自身じゃない場合は、上にさかのぼって検索(再帰的に)
            y = self.find(self.parent[x])           
            self.weight[x] += self.weight[self.parent[x]]   #圧縮時にweightを更新(和)
            self.parent[x] = y      #親の置き換え(圧縮)
            return self.parent[x]

    # 結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    ### 重み付き
    def weighted_union(self, x, y, w):
        # print("unite",x,y,w,self.weight)
        px = self.find(x)
        py = self.find(y)
        # 低い方を高い方につなげる(親のランクによる)
        # if px == py: return 0
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
            self.weight[px] = - w - self.weight[x] + self.weight[y]
        else:
            self.parent[py] = px
            self.weight[py] =  w + self.weight[x] - self.weight[y]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return 0

    # 判定
    def judge(self, x, y):
        return self.find(x) == self.find(y)

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a,b = map(int, input().split())
    if not uf.judge(a,b):
        uf.union(a,b)

d = defaultdict(int)
for i in range(n):
    d[uf.find(i)] += 1
print(len(d)-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int, input().split())
root = [-1] * (1100000)
def find(x):
    return x

def unite(a, b):
    a = find(a)
    b = find(b)
    if a != b:
        root[a] += root[b]
        root[b] = a
        

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

ans = 0
for i in range(1, n+1):
    if root[i]  < 0:
        ans += 1
print(ans-1)

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 union(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())
  union(a,b)
  
print(n-len(set(par))+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)
    
#根を再更新
for i in range(1,N+1):
  if city[i]!=i:
    root=city[i]
    while city[root]!=root:
      root=city[root]
    city[i]=root
  
#木が何種類あるかチェック
ck=[0]*(N+10)
for i in range(1,N+1):
  if ck[city[i]]==0:
    ck[city[i]]=1
    
#print(city)
#print(ck)
Ans=sum(ck)-1 #木の数-1=必要な道路数

print(Ans)

Submission status: Wrong Answer

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点

n,m = map(int,input().split())
par = [-1]*n
for i in range(m):
  a,b = map(int,input().split())
  unite(a-1,b-1)
  
ans = 0

for i in range(n):
  if par[i] < 0:
    ans += 1 
print(par)
print(ans-1)

Submission status: Wrong Answer

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点

n,m = map(int,input().split())
par = [-1]*n
for i in range(m):
  a,b = map(int,input().split())
  unite(a-1,b-1)
  
ans = 0

for i in range(n):
  if par[i] != 0:
    ans += 1
    
print(ans-1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [[] for i in range(n)]
vis = [0]*n
ans = -1

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


for i in range(n):
    if len(l[i]) == 0: #追加の連結なしなら
        if vis[i] == 0:
            vis[i] = 1
            ans += 1
    else: #追加の連結がある場合
        for j in l[i]: #連結対象を読み出す
            vis[j] = 1 #訪問済みにする
        if vis[i] == 0: #初訪問なら
            vis[i] = 1 #訪問済みにする
            ans += 1

print(ans)

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

print(Ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split())
    M = {}
    for i in range(n):
        M[i+1] = []
    for i in range(m):
        a,b = map(int,input().split())
        M[a] += [b]
        M[b] += [a]
    G = [0 for i in range(n)]
    g = 0
    for i in range(n):
        if G[i] == 0:
            g+=1
            G[i] = g
            que = [i+1]
            while len(que)>0:
                q = que.pop(0)
                for nv in M[q]:
                    if G[nv-1] != 0:
                        continue
                    G[nv-1] = g
                    que.append(q)
    print(max(G)-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split())
    M = {}
    for i in range(n):
        M[i+1] = []
    for i in range(m):
        a,b = map(int,input().split())
        M[a] += [b]
        M[b] += [a]
    G = [0 for i in range(n)]
    g = 0
    for i in range(n):
        if G[i] == 0:
            g+=1
            G[i] = g
            que = [i+1]
            while len(que)>0:
                q = que.pop(0)
                for nv in M[q]:
                    if G[nv-1] == 0:
                        G[nv-1] = g
                        que.append(q)
    print(g-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split())
    M = {}
    for i in range(n):
        M[i+1] = []
    for i in range(m):
        a,b = map(int,input().split())
        M[a] += [b]
        M[b] += [a]
    G = [0] * n
    g = 1
    for i in range(n):
        if G[i] == 0:
            G[i] = g
            que = [i+1]
            while len(que)>0:
                q = que.pop(0)
                for nv in M[q]:
                    if G[nv-1] != 0:
                        continue
                    G[nv-1] = g
                    que.append(q)
            g += 1
    print(g-2)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split())
    M = {}
    for i in range(n):
        M[i+1] = []
    for i in range(m):
        a,b = map(int,input().split())
        M[a] += [b]
        M[b] += [a]
    G = [0] * n
    g = 1
    for i in range(n):
        if G[i] == 0:
            G[i] = g
            que = [i+1]
            while len(que)>0:
                q = que.pop(0)
                for nv in M[q]:
                    if G[nv-1] != 0:
                        continue
                    G[nv-1] = g
                    que.append(q)
            g += 1
    print(g-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int,input().split())
    M = {}
    for i in range(n):
        M[i+1] = []
    for i in range(m):
        a,b = map(int,input().split())
        M[a] += [b]
        M[b] += [a]
    G = [0] * n
    g = 1
    for i in range(n):
        if G[i] == 0:
            G[i] = g
            que = [i+1]
            while len(que)>0:
                q = que.pop(0)
                for nv in M[q]:
                    if G[nv-1] != 0:
                        continue
                    G[nv-1] = g
                    que.append(q)
            g += 1
    print(n-g+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
#a = [i+1 for i in range(n)]
d = Unionfind(n)

for i in range(m):
    a,b = map(int,input().split())
    d.union(a-1,b-1)
    
L = []
for i in range(n):
    c = d.size(i)
    L.append(c)
print(len(set(L))-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#　n個分の入力
N, M = map(int, input().split())

l = []
for loop in range(M):
    x, y = map(int, input().split())
    l.append([x,y])
#print(l)

l.sort()

#print(l)

mem = [0]*N
conn = 0
node = 0
count = 0
endflag = 0
allconnect = 0
while True:
    if allconnect == 0:
        startnode = l[conn][0]-1
        for i in range(conn, M):
            if l[i][0]-1 == startnode:
                mem[l[i][0]-1]=1
                mem[l[i][1]-1]=1
                #print ("conn{} is processed".format(i))
                if conn < M-1:
                    conn = i + 1
                else:
                    allconnect = 1
            else:
                break
    if allconnect == 1:
        end = N-1
    else:
        end = l[conn][0]-1
    #print ("node, end, mem, allconnect = {},{},{},{}".format(node, end, mem,allconnect))
    for i in range(node, end):
        #print(i)
        if i <= l[conn][0]-1 or allconnect == 1:
            #print ("node{} is procedded".format(i))
            node = node +1
            if mem[i] == 1 and mem[i+1] == 0:
                count = count + 1
        else:
            break
    if allconnect == 1:
        endflag = 1

    if endflag == 1:
        break

print (count)
#print(mem)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#　n個分の入力
N, M = map(int, input().split())

l = []
for loop in range(M):
    x, y = map(int, input().split())
    l.append([x,y])
#print(l)

l.sort()

#print(l)

mem = [0]*N
conn = 0
node = 0
count = 0
endflag = 0
allconnect = 0
while True:
    if allconnect == 0:
        startnode = l[conn][0]-1
        for i in range(conn, M):
            if l[i][0]-1 == startnode:
                mem[l[i][0]-1]=1
                mem[l[i][1]-1]=1
                #print ("conn{} is processed".format(i))
                if conn < M-1:
                    conn = i + 1
                else:
                    allconnect = 1
            else:
                break
    if allconnect == 1:
        end = N-1
    else:
        end = l[conn][0]-1
    #print ("node, end = {},{}".format(node, end))
    for i in range(node, end):
        #print(i)
        if i <= l[conn][0]-1 or allconnect == 1:
            #print ("node{} is procedded".format(i))
            node = node +1
            if mem[i] == 1 and mem[i+1] == 1:
                pass
            else:
                count = count + 1
        else:
            break
        if node >= N-1:
            endflag = 1

    if endflag == 1:
        break

print (count)
#print(mem)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#　n個分の入力
N, M = map(int, input().split())

l = []
for loop in range(M):
    x, y = map(int, input().split())
    l.append([x,y])
#print(l)

l.sort()

#print(l)

mem = [0]*N
conn = 0
node = 0
count = 0
endflag = 0
allconnect = 0
while True:
    if allconnect == 0:
        startnode = l[conn][0]-1
        for i in range(conn, M):
            if l[i][0]-1 == startnode:
                mem[l[i][0]-1]=1
                mem[l[i][1]-1]=1
                #print ("conn{} is processed".format(i))
                if conn < M-1:
                    conn = i + 1
                else:
                    allconnect = 1
            else:
                break
    for i in range(node, N-1):
        #print(i)
        if i <= startnode or allconnect == 1:
            #print ("node{} is procedded".format(i))
            node = node +1
            if mem[i] == 1 and mem[i+1] == 1:
                pass
            else:
                count = count + 1
        else:
            break
        if node >= N-1:
            endflag = 1

    if endflag == 1:
        break

print (count)
#print(mem)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#　n個分の入力
N, M = map(int, input().split())

l = []
for loop in range(M):
    x, y = map(int, input().split())
    l.append([x,y])
print(l)

l.sort()

print(l)

mem = [0]*N
conn = 0
node = 0
count = 0
endflag = 0
allconnect = 0
while True:
    if allconnect == 0:
        startnode = l[conn][0]-1
        for i in range(conn, M):
            if l[i][0]-1 == startnode:
                mem[l[i][0]-1]=1
                mem[l[i][1]-1]=1
                #print ("conn{} is processed".format(i))
                if conn < M-1:
                    conn = i + 1
                else:
                    allconnect = 1
            else:
                break
    for i in range(node, N-1):
        #print(i)
        if i <= startnode or allconnect == 1:
            #print ("node{} is procedded".format(i))
            node = node +1
            if mem[i] == 1 and mem[i+1] == 1:
                pass
            else:
                count = count + 1
        else:
            break
        if node >= N-1:
            endflag = 1

    if endflag == 1:
        break

print (count)
#print(mem)

Submission status: Wrong Answer

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

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

print(n*(n-1)//2-t)