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=list(map(int,input().split()))

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

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

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

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

from collections import Counter as cnt

ans=cnt(par)

print(len(ans)-1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# スペース区切りの整数の入力
N, M = map(int, input().split())

for i in range(M):
    #内包表記
    A,B = [int(i) for i in input().split()]
if N-1-M > 0:
    print(N-1-M)
else:
    print(0)

Submission status: Wrong Answer

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

ans = []

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

ans = set(ans)


print(n - len(ans))

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

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

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

        if x == y:
            return

        self.parents[y] = x

N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    a,b=map(int,input().split())
    a-=1;b-=1
    uf.union(a,b)
print(len(set(uf.parents))-M)

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

Submission status: Wrong Answer

Solution code:
# Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n + 1)]
 
    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return 0
        elif x < y:
            self.parents[y] = x
        else:
            self.parents[x] = y
        return 1
 
from collections import Counter
n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)
roots = []
for num in uf.parents:
    roots.append(uf.find(num))

count_roots = Counter(roots)
print(max(count_roots.values())-1)

Submission status: Wrong Answer

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

for i in range(M):
    A,B=map(int,input().split())
    A,B=A-1,B-1
    d[A]=1
    d[B]=1
print(d.count(0))

Submission status: Wrong Answer

Solution code:
import math

N, M= map(int,input().split())
#AB=[]
#N = int(input())
#C = input()
C = []
for i in range(M):
    A, B = map(int,input().split())
    c = 0
    for p in C:
        if A in p:
            c = 1
            p.add(B)
        elif B in p:
            c = 1
            p.add(A)
    if c != 1:
        C.append(set([A,B]))
print(len(C)-1)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

uf = UnionFind(N)
for ab in AB:
    uf.union(ab[0]-1,ab[1]-1)
print(N-uf.group_count())

Submission status: Wrong Answer

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

pool = set()
cnt = 0
for i in range(m):
    a, b = map(int, input().split())
    if a in pool and b in pool:
        cnt += 1
    pool.add(a)
    pool.add(b)

print(n-1-m+cnt)

Submission status: Wrong Answer

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

l = [1 for i in range(0, n + 1)]
l[0] = 0
# print(l)

for _ in range(m):
    a, b = map(int, input().split())
    # print(a, b)
    l[a] = 0
    l[b] = 0
    

print(sum(l))

Submission status: Wrong Answer

Solution code:
import collections
n,m=map(int,input().split())
par=[i for i in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    par[b-1]=a-1
def find(x):
    if par[x]==x:
        return x
    else:
        while par[x]!=x:
            x=par[x]
        return x

for i in range(n):
    par[i]=find(i)

print(len(collections.Counter(par))-1)

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

city = []
for i in range(m):
    a, b = map(int, input().split())
    if not a in city:
        city.append(a)
    if not b in city:
        city.append(b)
print(n-(len(city)))

Submission status: Wrong Answer

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

import sys, os.path

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

sys.setrecursionlimit(10 ** 5)

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

#print=sys.stdout.write

def solve():
    a, b = mii()
    for i in range(b):
        c,d = mii()
    if a-1-b<=0:
        print(0)
    else: 
        print(a-1-b)

for _ in range(1):
    solve()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] #親
        self.rank = [0 for _ in range(n)] #根の深さ

    #xの属する木の根を求める
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    #xとyの属する集合のマージ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    #xとyが同じ集合に属するかを判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
n,m=map(int,input().split())
ans=0
U = UnionFind(n)
for i in range(m):
  a,b=map(int,input().split())
  a-=1
  b-=1
  U.unite(a,b)
print(n-len(set(U.par)))

Submission status: Wrong Answer

Solution code:
n,m = [int(x) for x in input().split()]
print(max(0,n-m-1))

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):
        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 main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    for i in range(m):
        s, t = map(int,input().split())
        uf.set(s-1, t-1)

    root = []
    for i in range(n):
        root.append(uf.root(i))

    single_root = set(root)

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

Submission status: Wrong Answer

Solution code:
import collections
n,m=map(int,input().split())
par=[i for i in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    par[b-1]=a-1
def find(x):
    if par[x]==x:
        return x
    else:
        while par[x]!=x:
            x=par[x]
        return x
print(par)
for i in range(n):
    par[i]=find(i)
print(par)
print(len(collections.Counter(par))-1)

Submission status: Wrong Answer

Solution code:
def N():
    return int(input())
def L():
    return list(map(int,input().split()))
def NL(n):
    return [list(map(int,input().split())) for i in range(n)]
mod = pow(10,9)+7
#import numpy as np
import sys
import math
import collections
par = []
def init(n):
    for i in range(n):
        par.append(i)

def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

def same(x,y):
    if root(x) == root(y):
        return True
    else:
        return False

def unite(x,y):
    x = root(x)
    y = root(y)
    if x==y:
        return
    par[x] = y
n,m = L()
ab = NL(m)
init(n)
#print(ab)
#print(par)
for a,b in ab:
    unite(a-1,b-1)
#print(par)
count = collections.Counter(par)
print(len(count)-1)

Submission status: Wrong Answer

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

par = [i for i in range(n)]
rank = [0]*n

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if rank[x]<rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

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

num=[]
for i in range(n):
    if par[i] not in num:
        num.append(par[i]) 

print(len(num)-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

n,m = map(int,sys.stdin.readline().split())
for i in range(m):
    a,b = map(int,sys.stdin.readline().split())
print(n-1-m)

Submission status: Wrong Answer

Solution code:
n,m=[int(x) for x in input().split()]
for i in range(m):
    p,q=[int(x) for x in input().split()]
if(m<n):
    print((n-1)-m)
else:
    print('0')

Submission status: Wrong Answer

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

for A,B in AB:
  if C[A-1]==0 and C[B-1]==0:
    C[A-1]+=1
    C[B-1]+=1
    ans-=2
  elif C[A-1]==0 and C[B-1]==1:
    C[A-1]+=1
    ans-=1
  elif C[A-1]==1 and C[B-1]==0:
    C[B-1]+=1
    ans-=1

print(ans)

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(max_v-bfs.count_trees())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
  par = None
  
  def __init__(self, n):
    self.par = list(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]
  
  def unite(self, x, y):
    if(self.root(x) != self.root(y)):
      self.par[x] = self.root(y)
      
  def same(self, x, y):
    return self.root(x) == self.root(y)
  
N, M = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(M):
  A, B = list(map(int, input().split()))
  UF.unite(A - 1, B - 1) 
ans = 0
for i in range(N):
  ans += (UF.par[i] == i)
print(ans - 1)

Submission status: Wrong Answer

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

h=[-1]*n

cnt=0

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

Submission status: Wrong Answer

Solution code:
class path_compressed_quick_union:
    def __init__(self, n):
        self.n = n
        self.data = [i for i in range(n)]
        self.size = [1 for i in range(n)]

    def root(self, p):
        while p != self.data[p]:
            self.data[p] = self.data[self.data[p]]
            p = self.data[p]
        return p

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def union(self, p, q):
        proot = self.root(p)
        qroot = self.root(q)
        if self.size[proot] < self.size[qroot]:
            self.data[qroot] = proot
            self.size[qroot] += self.size[proot]
        else:
            self.data[proot] = qroot
            self.size[proot] += self.size[qroot]



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

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

Submission status: Wrong Answer

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

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

for a, b in zip(A, B):
  if a not in C:
    C.add(a)
  if b not in C:
    C.add(b)

c = len(C)
print(c // 2 + c % 2)

Submission status: Wrong Answer

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

print(n-m)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
for _ 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())
ab=[list(map(int,input().split()))for i in range(m)]
def tie(n,m,ab):
    k=[-1for i in range(n)]
    l=0
    p,q=[],[]
    for i in range(m):
        a,b=ab[i]
        if k[a-1]>0 and k[b-1]>0:
            if k[a-1]==k[b-1]:
                continue
            else:
                p+=[k[a-1],k[b-1]]
                q+=[[k[a-1],k[b-1]]]
        elif k[a-1]>0:
            k[b-1]=k[a-1]
        elif k[b-1]>0:
            k[a-1]=k[b-1]
        else:
            k[a-1]=l
            k[b-1]=l
            l+=1
    for i in k:
        if i<0:
            l+=1
    if len(p)>0:
        return l-1-tie(len(set(k)),len(q),q)
    else:
        return l-1
print(tie(n,m,ab))

Submission status: Wrong Answer

Solution code:
import math

class UnionFind:
    def __init__(self, size):
        self.parent_indexes = [-1] * size
        
    def find(self, n):
        if self.parent_indexes[n] < 0:
            return n
        # 探しているnodeが指し示しているのが現在の親ではない場合、
        # 現在の親に書き換え(メモ化) した上で返す
        self.parent_indexes[n] = self.find(self.parent_indexes[n])
        return self.parent_indexes[n] 
    
    def union(self, n1, n2):
        if self.same_group(n1, n2):
            return False
        
        # サイズの大きい方の集団の親が親であり続ける
        if self.size(n1) >= self.size(n2):
            tmp = self.size(n2)
            self.parent_indexes[self.find(n2)] = self.find(n1)
            self.parent_indexes[self.find(n1)] -= tmp
            return True
        
        # サイズが小さい方の集団の親は親を引退する
        tmp = self.size(n1)
        self.parent_indexes[self.find(n1)] = self.find(n2)
        self.parent_indexes[self.find(n2)] -= tmp
        return True
        
    # その要素が所属する集団の要素数
    def size(self, n):
        return -self.parent_indexes[self.find(n)]
    
    def same_group(self, n1, n2):
        return self.find(n1) == self.find(n2)

n, m = map(lambda x: int(x), input().split())


uf = UnionFind(n)

for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    uf.union(a-1, b-1)
    
num_parents = 0
    
for p_index in uf.parent_indexes:
    if p_index < 0:
        num_parents += 1
print(math.ceil((math.log2(num_parents))))

Submission status: Wrong Answer

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

list = []
count = 0
for i in range(m):
  a,b = map(int,input().split())
  if a not in list:
    list.append(a)
  if b not in list:
    list.append(b)
    
print(len(list)-m)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class UnionFind:
  par = None
  
  def __init__(self, n):
    self.par = list(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]
  
  def unite(self, x, y):
    if(self.root(x) != self.root(y)):
      self.par[x] = self.root(y)
      
  def same(self, x, y):
    return self.root(x) == self.root(y)
  
N, M = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(M):
  A, B = list(map(int, input().split()))
  UF.unite(A - 1, B - 1) 
ans = 0
for i in range(N):
  ans += (UF.par[i] == 0)
print(ans - 1)

Submission status: Wrong Answer

Solution code:
# スペース区切りの整数の入力
N, M = map(int, input().split())

for i in range(M):
    #内包表記
    A,B = [int(i) for i in input().split()]
print(N-1-M)

Submission status: Wrong Answer

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

print((n-1) - len(li))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ls = [[i+1] for i in range(n)]
for i in range(m):
    x = 0
    a,b = map(int,input().split())
    for i in range(len(ls)):
        if a in ls[i]:
            ls[i].append(b)
            x = 1
        elif b in ls[i]:
            ls[i].append(a)
            x = 1
    if x == 0:
        ls.append([a,b])

ans = 0
for i in ls:
    if len(i) == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [1]*n
        self.size = [1]*n
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x); y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    def group_size(self, x):
        return self.size[self.find(x)]
uf = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split()); a -= 1; b -= 1
    uf.unite(a, b)
print(len(set(uf.parent))-1)

Submission status: Wrong Answer

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

d = [0]*n
c = 0
for i in range(m):
    a, b = map(int, input().split())
    x = a-1
    y = b-1
    if(d[x] == 0 and d[y] == 0):
        c+=1
        d[x] = c
        d[y] = c
    else:

        m = max(d[x], d[y])
        d[x] = m
        d[y] = m

ans = 0
for i in d:
    if(i==0):ans+=1
#print(d)
print(ans+c-1)

Submission status: Wrong Answer

Solution code:
n,m=[int(x) for x in input().split()]
for i in range(m):
    p,q=[int(x) for x in input().split()]
print((n-1)-m)

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

#Union Find
def root(x):
    while par[x]!=x:
        x=par[x]
    return x

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

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[y]<size[x]: x,y=y,x
    size[y]+=size[x]
    par[x]=y

def getsize(x):
	return size[root(x)]

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)

print N-getsize(1)

Submission status: Wrong Answer

Solution code:
import math

# UnionFind、0-indexであることに注意
#############################################################


class UnionFind:

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

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################

N, M = map(int, input().split())
G = [[] for _ in range(N)]
uf = UnionFind(N)

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

root_list = []
for i in range(N):
    r = uf.find(i)
    root_list.append(r)

root_list = list(set(root_list))
num = len(root_list)

# 普通のcombination
#############################################################


def comb(n, r):  # 普通のcombination計算
    if r < 0 or r > n:
        return 0
    else:
        n1 = math.factorial(n)
        n21 = math.factorial(n - r)
        n22 = math.factorial(r)
        ans = n1 // (n21 * n22)
        return ans
#############################################################


ans = comb(num, 2)
print(ans)

Submission status: Wrong Answer

Solution code:
# AtCoder
n, m = map(int, input().split())
c = []
for _ in range(m):
    a, b = map(int, input().split())
    if a not in c: c.append(a)
    if b not in c: c.append(b)
print(n - len(c))

Submission status: Wrong Answer

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

global fri
fri=[]
global tab
tab=[0]*n
def run(nn):
  #print(tab)
  global cnt
  if tab[nn]:
    return
  tab[nn]=1
  cnt+=1
  for i in fri[nn]:
    que.append(i)
for i in range(n):
  fri.append([])
for i in range(m):
  a,b=map(int,input().split())
  fri[a-1].append(b-1)
  fri[b-1].append(a-1)
i=0
mx=0
cc=0
while i<n:
  if tab[i]:
    i+=1
    continue
  que=[i]
  cnt=0
  while len(que)!=0:
    run(que.pop())
  mx=max(cnt,mx)
  i+=1
  cc+=1
print(cc)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split( ))
loads = []
teams = [i for i in range(N)]
for _ in range(M):
    A,B = map(int,input().split( ))
    team = min(teams[A-1],teams[B-1])
    teams[A-1],teams[B-1] = team,team
ans = len(set(teams)) - 1
print(ans)

Submission status: Wrong Answer

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

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


class UnionFind:
  def __init__(self,N):
    self.parent = [i for i in range(N)]
    self._size = [1] * N
    self.count = 0
  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_same(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._size[ra] < self._size[rb]: ra,rb = rb,ra
    self._size[ra] += self._size[rb]
    self.parent[rb] = ra
    self.count += 1
  def size(self,a):
    return self._size[self.root(a)]

uf = UnionFind(n)

for i in range(m):
  a,b = ab[i][0],ab[i][1]
  a -= 1
  b -= 1
  if uf.is_same(a,b):
    continue
  uf.unite(a,b)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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