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 sys
sys.setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self, x):#親となる要素を探索
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#再帰
            return self.root[x]

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

        elif self.rank[x] > self.rank[y]:#深い木に連結
            self.root[x] += self.root[y]
            self.root[y] = x#yの親をxとする

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def issame(self, x, y):#x, yが同じ集合か判定
            return self.find(x) == self.find(y)


    def count(self, x):#要素の個数
        return (-1)*self.root[self.find(x)]

n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)
x=[]
for i in range(n):
    if uf.find(i):
        x.append(i)
print(len(set(x))-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(lambda x: int(x) - 1, s.split())
    edge[a].append(b)
    edge[b].append(a)

path = [-1] * N
cnt = 0
for i in range(N):
    if path[i] < 0:
        cnt += 1
        q = deque()
        path[i] = i
        q.append(i)
        while q:
            p = q.popleft()
            for np in edge[p]:
                if path[np] < 0:
                    path[np] = i
                    q.append(np)

print(cnt)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [[] for _ in range(n+1)]
flags = [0 for _ in range(n+1)]
for i in range(m):
    _a, _b = map(int, input().split())
    l[_a].append(_b)


def check(_a):
    if not flags[_a] == 0:
        pass
    else:
        max_b = 0
        flags[_a] = 1
        for _b in l[_a]:
            check(_a=_b)


j = 1
ans = -1
while  not j > n:
    if not flags[j] == 0:
        j += 1
    else:
        ans += 1
        check(j)
        j += 1
print(ans)

Submission status: Wrong Answer

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


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

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

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

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

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

        return self.p[x]


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

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

print(len(list(set(ds.p))) - 2)

Submission status: Wrong Answer

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


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

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

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

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

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

        return self.p[x]


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

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

print(list(set(ds.p)))
print(len(list(set(ds.p))) - 2)

Submission status: Wrong Answer

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

g=-1
me=n
for i in range(m):
  a,b=map(int,input().split())
  if (tojo[a-1]==0) and (tojo[b-1]==0):
    tojo[a-1]=1
    tojo[b-1]=1
    g=g+1
    me=me-2
  elif (tojo[a-1]==0) and (tojo[b-1]!=0):
    tojo[a-1]=1
    me=me-1
  elif (tojo[a-1]!=0) and (tojo[b-1]==0):
    tojo[b-1]=1
    me=me-1
  else:
    g=g-1

print(g+me)

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())
#島の数引く1
ns = [0]*n
sima = n
for i in range(m):
    if ns[a[i]-1] == 0 or ns[b[i]-1] == 0:#島の数が減るのは
        ns[a[i]-1] = 1
        ns[b[i]-1] = 1
        sima -= 1

if sima-1 >= 0:
    print(sima-1)
else:
    print(0)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

#ルートチェック
  if city[A]!=A:
    root=city[A]
    while city[root]!=root:
      root=city[root]
    city[A]=root
  
  if city[B]!=B:
    root=city[B]
    while city[root]!=root:
      root=city[root]
    city[B]=root

#結合
  if city[A]!=city[B]:
    wk=min(city[A],city[B])
    city[A]=wk
    city[B]=wk
#    print(city[max(A,B)])
#    print(city[min(A,B)])
    
#print(city)
    
  
#木が何種類あるかチェック
ck=[0]*(N+10)
for i in range(1,N+1):
  if 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())

s = []
r = []
for i in range(m):
    s += map(int, input().split())


f = True
for i in range(n):
    for l in range(m*2):
        if s[l] == i+1:
            f = False
            break
    if f:
        r += str(i)
    else:
        f = True

print(len(r))

Submission status: Wrong Answer

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
    # ノードxのrootノードを見つける
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
    # 木の併合、入力は併合したい各ノード⇒(a,b)
        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):
    # ノードxが属する木のサイズを返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
    # 入力ノード(x,y)が同じグループに属するかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
    #ノード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())

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline



import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n,m=map(int,input().split())
u=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    u.unite(a,b)
ans=0
for i in range(n):
    ans=max(ans,u.size(i))
print(ans-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class union_find():

    def __init__(self, n):
        # self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

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

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

        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y

            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def cnt(self, x):
        return -self.root[self.find_root(x)]


n, m = map(int, input().split())
g = union_find(n)
ans = 0
for _ in range(m):
    a, b = map(int, input().split())
    g.unite(a, b)

for i in range(1, n+1):
    ans = max(ans, g.cnt(i))
print(ans-1)

Submission status: Wrong Answer

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


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

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

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

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

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

        return self.p[x]


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

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

print(len(list(set(ds.p))) - 1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

#ルートチェック
  if city[A]!=A:
    root=city[A]
    while city[root]!=root:
      root=city[root]
    city[A]=root
  
  if city[B]!=B:
    root=city[B]
    while city[root]!=root:
      root=city[root]
    city[B]=root

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

print(Ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l_Ai = []
l_Bi = []

for i in range(M):
    Ai, Bi = map(int, input().split())
    l_Ai.append(Ai)
    l_Bi.append(Bi)

road_need = N - 1 - M
print(road_need)

Submission status: Wrong Answer

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


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

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

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

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

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

        return self.p[x]


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

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

print(list(set(ds.p)))
print(len(list(set(ds.p))) - 1)

Submission status: Wrong Answer

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

c = [False] * n

for i in range(m):
    node = input().split(' ')
    for j in range(2):
        c[int(node[j]) - 1] = True

print(c.count(False))

Submission status: Wrong Answer

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

n0=0
m0=0
for i in range(m):
  a,b=map(int,input().split())
  if (tojo[a-1]==0) and (tojo[b-1]==0):
    tojo[a-1]=1
    tojo[b-1]=1
    n0=n0+1
    m0=m0+2
  elif (tojo[a-1]==0) and (tojo[b-1]!=0):
    tojo[a-1]=1
    m0=m0+1
  elif (tojo[a-1]!=0) and (tojo[b-1]==0):
    tojo[b-1]=1
    m0=m0+1
  else:
    n0=n0-1

print(n0-1+n-m0)

Submission status: Wrong Answer

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

count = 0
myset = set([])
for i in range(M):
	if x[i] in myset and y[i] in myset:
		count +=1
	myset.add(x[i])
	myset.add(y[i])
#N-1本が最小本数
ans = N - 1 - M + count
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
cityList = []
for i in range(m):
  load = list(map(int,input().split()))
  if load[0] in cityList:
    cityList.append(load[0])
  if load[1] in cityList:
    cityList.append(load[1])

print(n-1-len(cityList))

Submission status: Wrong Answer

Solution code:
NM = list(map(int, input().split()))
N = NM[0]
M = NM[1]

xy = [map(int, input().split()) for _ in range(M)]
x, y = [list(i) for i in zip(*xy)]

def my_index(l, x):
    if x in l:
        return l.index(x)
    else:
        return -1

group = []
# for i in range(M):
#     index = -1
#     bo = True
#     for j in range(len(group)):
#         if x[i] in group[j] or y[i] in group[j]:
#             group[j].append(x[i])
#             group[j].append(y[i])
#             # if my_index(group[j], x[i]) != -1:
#             #     index = group.index(x[i])
#             # else:
#             #     index = group.index(y[i])
#             bo = False
#             break
#     if bo:
#         group.append([x[i], y[i]])

for i in range(N):
    index = -1
    for j in range(len(group)):
        if i in group[j]:
            index = j
    if index == -1:
        group.append([i])
    else:
        for j in range(M):
            if i == x[j]-1 or i == y[j]-1:
                group[index].append(x[j])
                group[index].append(y[j])


print(len(group)-1)

Submission status: Wrong Answer

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

print(ans + flag.count(0))

Submission status: Wrong Answer

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

c = [False] * n

for i in range(m):
    node = input().split(' ')
    for j in range(2):
        c[int(node[j]) - 1] = True

print(c.count(False)-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


    return count-1

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

Submission status: Wrong Answer

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

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

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

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

    print(answer + N)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

dup = [tuple(sorted(d)) for d in ab]
unique = set(dup)
unique = [list(d) for d in unique]
print((n - 1) - len(unique))

Submission status: Wrong Answer

Solution code:
N,M = list(map(int, input().split()))
par = [i for i 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 x==y :
        return
    par[y] = x
    
for i in range(M):
    A, B = list(map(int, input().split()))
    unite(A, B)


print(len(set(par))-2)

Submission status: Wrong Answer

Solution code:
def main():
    n,m = map(int, input().split())
    d = dict()
    cnt = 0
    for i in range(1,n+1):
        d[i] = []
    for _ in range(m):
        first, second = map(int, input().split())
        d[first].append(second)
        d[second].append(first)
    # print(d)
    temp = []
    for city in d:
        t = [city]
        t += d[city]
        t = sorted(t)
        temp.append(t)
    # print("temp: ",temp)
    ans = []
    for i in range(len(temp)):
        if temp[i] not in ans:
            ans.append(temp[i])
    # print("ans: ",ans)
    return len(ans)-1



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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((min(a, b), max(a, b)))
AB = sorted(AB, key = lambda x: x[0])

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

Submission status: Wrong Answer

Solution code:

def main():
    N, M = map(int, input().split())
    for i in range(M):
        A, B = map(int, input().split())

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


main()

Submission status: Wrong Answer

Solution code:
def solve():
    n, m = map(int, input().split())
    connected = {}
    if m:
        a, b = map(int, input().split())
        connected[0] = {a, b}
    for _ in range(m - 1):
        a, b = map(int, input().split())
        for x in range(len(connected)):
            if a or b in connected[x]:
                connected[x] = connected[x].union({a, b})
                break
            elif x == connected:
                connected[x + 1] = {a, b}
                break
    if connected:
        return n - len(connected[0]) + len(connected) - 1
    else:
        return n - 1



print(solve())