Problem:


Score : 300 points

Problem Statement

There are N cities numbered 1 through N, and M bidirectional roads numbered 1 through M.
Road i connects City A_i and City B_i.

Snuke can perform the following operation zero or more times:

Choose two distinct cities that are not directly connected by a road, and build a new road between the two cities.

After he finishes the operations, it must be possible to travel from any city to any other cities by following roads (possibly multiple times).

What is the minimum number of roads he must build to achieve the goal?

Constraints

2 \leq N \leq 100,000

1 \leq M \leq 100,000

1 \leq A_i < B_i \leq N

No two roads connect the same pair of cities.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
:
A_M B_M

Output

Print the answer.

Sample Input 1

3 1
1 2

Sample Output 1

1

Initially, there are three cities, and there is a road between City 1 and City 2.

Snuke can achieve the goal by building one new road, for example, between City 1 and City 3.
After that,

We can travel between 1 and 2 directly.

We can travel between 1 and 3 directly.

We can travel between 2 and 3 by following both roads (2 - 1 - 3).



Sample input:
3 1
1 2


Sample output:
1

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import Counter
import math
import statistics
import itertools
# a,b=map(int,input().split())
# b=int(input())
# c=[]
# for i in a:
#     c.append(int(i))
N,M= map(int,input().split())
# f = list(map(int,input().split()))
#g = [list(map(lambda x: '{}'.format(x), list(input()))) for _ in range(a)]
# h = []
# for i in range(a):
#     h.append(list(map(int,input().split())))
# a = [[0] for _ in range(H)]#nizigen
lis=[list(map(int,input().split())) for i in range(M)]

print(N-len(lis)-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
cities = [i for i in range(N + 1)]
cities.remove(0)

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

amari = len(set(cities) - set(paths))


ans = 0
if amari == 0:
    pass
elif amari == 1:
    ans = 1
elif amari % 2 == 0:
    ans = (amari // 2 + 1)
else:
    ans = (amari // 2 + 2)

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
class uft():
    def __init__(self,n):
        #pは代表元か-1
        self.p=[ -1 for i in range(n)]
        #ランク　木の深さ
        self.r=[ 1 for i in range(n)]
        #要素数
        self.e=[ 1 for i in range(n)]
        
    def find(self,x):
        if(self.p[x]==-1):
            return x
        else:
            self.p[x]=self.find(self.p[x])
            return self.find(self.p[x])
        
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):
            return
        
        if(self.r[x]>self.r[y]):
            tmp=x
            x=y
            y=tmp
        
        if(self.r[x]==self.r[y]):
            self.r[y]+=1
        
        self.e[y]+=self.e[x]
            
        if(x!=y):
            self.p[x]=y
        return
    
    def tsize(self,x):
        return self.e[self.find(x)]
n,m=map(int,input().split())

uf=uft(n)
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    uf.unite(x,y)
ans=0
xx=collections.Counter(uf.p)
tmp=len(xx)
tmp-=1
for i in range(n):
    if(uf.p[i]==-1):
        ans+=1
print(ans-tmp)

Submission status: Wrong Answer

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


print(n-m-1)

Submission status: Wrong Answer

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

  def get_root(self, i):
    if self.parent[i] < 0:
      return i
    else:
      self.parent[i] = self.get_root(self.parent[i])
      return self.parent[i]

  def is_same_tree(self, i, j):
    return self.get_root(i) == self.get_root(j)

  def merge(self, i, j):
    i = self.get_root(i)
    j = self.get_root(j)
    if i == j:
      return

    if self.rank[i] > self.rank[j]:
      self.parent[j] = i
      self.rank[i] = max(self.rank[i], self.rank[j] + 1)
      self.count[i] += self.count[j]
    else:
      self.parent[i] = j
      self.rank[j] = max(self.rank[j], self.rank[i] + 1)
      self.count[j] += self.count[i]
      
N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
  a, b = [int(i) - 1 for i in input().split()]
  uf.merge(a, b)
print(max(uf.count) - 1)

Submission status: Wrong Answer

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

t = set(t)
print(n-len(t))

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

S  = set()
for i in range(M):
    A, B = map(int, input().split())
    S.add(A)
    S.add(B)
print(N-len(S))

Submission status: Wrong Answer

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

count = [0]+[1]*(n)
for a,b in ab:
  count[a] = 0
  count[b] = 0
print(sum(count))

Submission status: Wrong Answer

Solution code:
class UnionFind:
  par = None
  
  def __init__(self, n):
    self.par = [0] * n
    
  def root(self, x):
    if(self.par[x] == 0):
      return x
    else:
      self.par[x] = self.root(self.par[x])
      return self.root(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:
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())
u = UnionFind(n)

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

a = u.roots()
print(len(a))

Submission status: Wrong Answer

Solution code:
import sys, os, io
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math,datetime,functools,itertools,operator,bisect,fractions
from collections import deque,defaultdict,OrderedDict,Counter
from fractions import Fraction
from decimal import Decimal
N = 300005
 
# array to store inverse of 1 to N 
factorialNumInverse = [None] * (N + 1) 
 
# array to precompute inverse of 1! to N! 
naturalNumInverse = factorialNumInverse.copy() 
 
# array to store factorial of  
# first N numbers 
fact = factorialNumInverse.copy() 
 
# Function to precompute inverse of numbers 
def InverseofNumber(p): 
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1): 
        naturalNumInverse[i] = (naturalNumInverse[p % i] * 
                                (p - int(p / i)) % p) 
# Function to precompute inverse  
# of factorials 
def InverseofFactorial(p): 
    factorialNumInverse[0] = factorialNumInverse[1] = 1
  
    # precompute inverse of natural numbers 
    for i in range(2, N + 1, 1): 
        factorialNumInverse[i] = (naturalNumInverse[i] * 
                                  factorialNumInverse[i - 1]) % p 
  
# Function to calculate factorial of 1 to N 
def factorial(p): 
    fact[0] = 1
  
    # precompute factorials 
    for i in range(1, N + 1): 
        fact[i] = (fact[i - 1] * i) % p 
  
# Function to return nCr % p in O(1) time 
def Binomial(N, R, p): 
    
      
    # n C r = n!*inverse(r!)*inverse((n-r)!) 
    ans = ((fact[N] * factorialNumInverse[R])% p * 
                      factorialNumInverse[N - R])% p 
    return ans 


def main():
    starttime=datetime.datetime.now()
    if(os.path.exists('input.txt')):
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    
    
    for _ in range(1):
        n,m=ria()
        for i in range(m):
            a,b=ria()
        print(max(0,n-1-m))
        
        
        
        
        
        
                    
        
    #<--Solving Area Ends
    endtime=datetime.datetime.now()
    time=(endtime-starttime).total_seconds()*1000
    if(os.path.exists('input.txt')):
        print("Time:",time,"ms")  
    
                
class FastReader(io.IOBase):
    newlines = 0

    def __init__(self, fd, chunk_size=1024 * 8):
        self._fd = fd
        self._chunk_size = chunk_size
        self.buffer = io.BytesIO()

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, size=-1):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()


class FastWriter(io.IOBase):

    def __init__(self, fd):
        self._fd = fd
        self.buffer = io.BytesIO()
        self.write = self.buffer.write

    def flush(self):
        os.write(self._fd, self.buffer.getvalue())
        self.buffer.truncate(0), self.buffer.seek(0)


class FastStdin(io.IOBase):
    def __init__(self, fd=0):
        self.buffer = FastReader(fd)
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


class FastStdout(io.IOBase):
    def __init__(self, fd=1):
        self.buffer = FastWriter(fd)
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.flush = self.buffer.flush


if __name__ == '__main__':
    sys.stdin = FastStdin()
    sys.stdout = FastStdout()
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]

par = [i for i in range(n + 1)]
rank = [1 for _ in range(n + 1)]

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

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

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

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

print(len(set(par[1:])) - 1)

Submission status: Wrong Answer

Solution code:
import sys
#sys.exit()
#sorted( ,reverse=True)
#N = int(input())
N,M = map(int, input().split())
A = list([(int, input().split()) for _ in range(M)])
#A = [int(input()) for _ in range(N)]

#cnt = 0
#cnt += 1

print((N-1)-M)
#print(N,M)


#print(A)
#print(S,T)
#print(A)
#print('Yes')
#print('No')
#print(cnt)

Submission status: Wrong Answer

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

res = n-m-1
if(res <= 0):
  print(0)
else:
  print(res)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
road=[[] for _ in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)
ischecked=[0]*(N)
ans=0
for i in range(N):
    if ischecked[i]==1:
        continue
    q=[i]
    while q:
        now=q.pop()
        nex=road[now]
        for j in nex:
            if ischecked[j]!=0:
                continue
            q.append(i)
            ischecked[j]=1
    ans+=1
print(ans-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:
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
city = [0]*n
for _ in range(m):
    n1,n2 = map(int,input().split())
    city[n1-1] = 1
    city[n2-1] = 1

cnt = 0
for i in range(n):
    if city[i] == 0:
        cnt+=1
        city[i] = 1
print(cnt)

Submission status: Wrong Answer

Solution code:
class UF:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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

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

n,m = map(int, input().split(" "))
ab = [list(map(int, input().split(" "))) for i in range(m)]

tr = UF(n)
for a,b in ab:
  tr.union(a, b)
count = [0]*(n+1)
for i in tr.par:
  count[i]=1
print(sum(count)-2)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
lst = [-1 for i in range(n + 1)]
lst[0] = 0
def find (x):
    if (lst[x] < 0):
        return(x)
    else:
        return (find(lst[x]))
def unit(x, y):
    xp = find(x)
    yp = find(y)
    if (xp == yp):
        pass
    else:
        lst[y] = x
for i in range(m):
    a, b = map(int,input().split())
    unit(a, b)
ans = -1
for i in range(n + 1):
    if (lst[i] == -1):
        ans = ans + 1

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.member_num = [1 for _ in range(size)]

    #representative
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        m1=self.member_num[s1]
        m2=self.member_num[s2]
        if s1 != s2:
            if m1 != m2:
                if m1 < m2:
                    self.table[s1] = s2
                    self.member_num[s2]=m1+m2
                    return [m1,m2]
                else:
                    self.table[s2] = s1
                    self.member_num[s1]=m1+m2
                    return [m1,m2]
            else:
                self.table[s1] = -1
                self.table[s2] = s1
                self.member_num[s1] = m1+m2
                return [m1,m2]
        return [0,0]

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

edge = [list(map(int,input().split())) for i in range(M)]

dsu = UnionFind(N)
count = 0
for e in edge:
    a,b = e
    a,b = a-1,b-1
    if dsu.find(a)==-1 or dsu.find(b)==-1:
        dsu.union(a,b)
        count+=1
    elif dsu.find(a)!=dsu.find(b):
        dsu.union(a,b)
        count+=1

print(count)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return False
        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.root(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.unite(a, b)

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

print(n- (ans))

Submission status: Wrong Answer

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

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

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

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

        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

    def show(self):
        return self.par


N, M = [int(x) for x in input().split()]
tree = UnionFind(N-1)

for _ in range(M):
    a, b = [int(x) - 1 for x in input().split()]
    tree.union(a, b)

value = len(set(tree.show()))
print(value - 1)

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())
for i in range(m):
    a,b  =map(int,input().split())
print(n-1-m)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
for i in range(M):
    a,b = map(int,input().split())
    unite(a, b)

cnt = -1
num = {0}

for i in par:
  if i not in num:
    num.add(i)
    cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2*10**5)#必要に応じて

class UnionFind:#再帰上限に引っかかることがあるので
    def __init__(self,n):
        self.l=list(range(n))
        self.n=n
        self.rank=[0 for i in range(n)]
    def find(self,x):
        if self.l[x]==x:
            return x
        self.l[x]=self.find(self.l[x])
        return self.l[x]
    def union(self,x,y):
        if x==y:return
        if self.rank[x]>self.rank[y]:
            return self.union(y,x)
        a,b=self.find(x),self.find(y)
        self.l[a]=b
        self.rank[a]=max(self.rank[b]+1,self.rank[a])
    def isSame(self,x,y):
        return self.find(x)==self.find(y)
n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    u.union(a-1,b-1)
d=set()
for i in range(n):
    d.add(u.find(i))
print(n-len(d))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l = []
for i in range(M):
  l.append(list(map(int, input().split())))
  
par = [i for i in range(N+1)]
def find(x):
  if par[x] == x:
    return x
  else:
    par[x] = find(par[x])
    return par[x]
def same(x,y):
  return find(x) == find(y)
def unite(x,y):
  x = find(x)
  y = find(y)
  if x == y:
    return 0
  par[x] = y
  
for i in range(M):
  a, b = l[i][0], l[i][1]
  unite(a, b)
  
print(len(set(par))-2)

Submission status: Wrong Answer

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

for i in range(m):
  _a, _b = map(int, input().split())
  cnt[_a - 1] += 1
  cnt[_b - 1] += 1

ans = 0
for i in range(n):
  if cnt[i] == 0:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
par = [i for i in range(n+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def 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 _ in range(m):
    a, b = map(int, input().split())
    unite(a, b)
print(len(set(par[1:]))-1)

Submission status: Wrong Answer

Solution code:
s = set()
n,m = [int(x) for x in input().split()]
for i in range(m):
  a,b =[int(x) for x in input().split()]
  s.add(a)
  s.add(b)
print(n-len(s))

Submission status: Wrong Answer

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

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)

a = max(uf._size)
ans = n-a
print (ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class UnionFindTree:
    def __init__(self, n):
        self._tree = [i for i in range(n)]
        self._rank = [1] * n
    def root(self, a):
        if self._tree[a] == a:return a
        self._tree[a] = self.root(self._tree[a])
        return self._tree[a]
    def is_same_set(self, a, b):
        return self.root(a) == self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._rank[ra] < self._rank[rb]:
            self._tree[ra] = rb
        else:
            self._tree[rb] = ra
            if self._rank[ra] == self._rank[rb]:
                self._rank[ra] += 1

def solve(n, m, x):
    uft = UnionFindTree(n)
    for a,b in x:
        uft.unite(a-1, b-1)
    return len(set(uft._tree))-1

if __name__ == "__main__":
    n,m = map(int, input().split())
    *edges, = [list(map(int, input().split())) for _ in range(m)]
    print(solve(n,m,edges))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
data=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  data[a-1].append(b-1)
  data[b-1].append(a-1)
ans=float('inf')
for i in data:
  res=n-1-len(i)
  ans=min(ans,res)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.siz=[1]*n

    def root(self,x):
        while self.par[x]!=x:
            self.par[x]=self.par[self.par[x]]
            x=self.par[x]
        return x

    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.siz[x]<self.siz[y]:
            x,y=y,x
        self.siz[x]+=self.siz[y]
        self.par[y]=x
        return True

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

    def size(self,x):
        return self.siz[self.root(x)]

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

cnt = [0]*(n)
for aa in uni.par:
    cnt[aa] = 1

print(sum(cnt)-1)

Submission status: Wrong Answer

Solution code:
import sys
z=sys.stdin.readline
y=lambda:map(int,z().split())
n,m=y()
s=set()
k=0
e=0
for i in range(m):
  a,b=y();s.add(a);s.add(b)
  if len(s)>k:e+=1
  k=len(s)
print(n-1-e)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
k=[-1for i in range(n)]
l=0
for i in range(m):
    a,b=map(int,input().split())
    if 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
print(l-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
n, m = map(int, input().split())
l = list()
for i in range(m):
	l.extend(map(int, input().split()))
size = len(set(l))
print(n-size)