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:
# -*- coding: utf-8 -*
N, M = map(int,input().split())
AB = [0]*N
group = [N]
g = [0]
c = 1
for i in range(M):
  nyu = list(map(int,input().split()))
  if AB[nyu[0]-1] == 0 and AB[nyu[1]-1] == 0:
    AB[nyu[0]-1], AB[nyu[1]-1] = c, c
    group.append(2)
    g.append(c)
    group[0] -= 2
    c += 1
  elif AB[nyu[0]-1] != 0 and AB[nyu[1]-1] == 0:
    AB[nyu[1]-1] = AB[nyu[0]-1]
    group[g[AB[nyu[0]-1]]] += 1
    group[0] -= 1
  elif AB[nyu[0]-1] == 0 and AB[nyu[1]-1] != 0:
    AB[nyu[0]-1] = AB[nyu[1]-1]
    group[g[AB[nyu[1]-1]]] += 1
    group[0] -= 1
  else:
    group[g[AB[nyu[0]-1]]] += group[g[AB[nyu[1]-1]]]
    group[g[AB[nyu[1]-1]]] = 0
    g[AB[nyu[1]-1]] = g[AB[nyu[0]-1]]

print(group[0] + max(g) - 1)

Submission status: Wrong Answer

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

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

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

        if x == y:
            return

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

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


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

uf=UnionFind(N+1)
for i in range(M):
    uf.union(A[i],B[i])
a=[0]*(N+1)
con=0

for i in uf.parents:
    if(0<i):
        a[i]=1
        con=con+1

print(N-(sum(a)+con))

Submission status: Wrong Answer

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

maps = [1] * n
countMakeRoads = 0
roads = []

for i in range(m):
    aiBi = list(map(int, input().strip().split()))
    if aiBi[0] == 1:
        maps[aiBi[1]-1] = aiBi[1]
    else:
        roads.append(aiBi)

for i in range(len(roads)):
    ai = roads[i][0]
    bi = roads[i][1]
    if  maps[ai-1] == ai:
        maps[bi-1] = bi
    elif maps[bi-1] == bi:
        maps[ai - 1] = ai
    else:
        countMakeRoads += 1
        maps[ai - 1] = ai
        maps[bi - 1] = bi

for i in range(n):
    if maps[i] != i+1:
        countMakeRoads += 1
        maps[i] = i+1
print(countMakeRoads)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
# su=[]
# for _ in range(n):
#     su.append(input())
# print(su)
# tasu=0
# start=0
# for _ in range(len(su)):
#     tasu+=1
#     if abs(su[start]-su[start+tasu])<=
toshi=[]
kazu=n-1
print(kazu-m)

Submission status: Wrong Answer

Solution code:
c, r = input("").split(" ")

cityOne, cityTwo = input("").split(" ")
c, r, cityOne, cityTwo = int(c), int(r), int(cityOne), int(cityTwo)
nr = 0
if r % 2 == 0 and r != c - 1:
    nr += 1
else:
    nr += 2
print(nr)

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)
flag = [0 for i in range(N)]
ans = 0
i = sl[0][0]
for s in sl:
    if s[0] == i:
        flag[i - 1] = 1
        flag[s[1] - 1] = 1
    else:
        if 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 = map(int, input().split())
root = []
ans = [0] * (N+1)
for _ in range(M):
    a,b= map(int,input().split())
    if a in root:
        ans[b] = 1
    elif b in root:
        ans[a] = 1
    else:
        root += [a,b]
        ans[a] = 1
        ans[b] = 1
print(ans.count(0)-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ans = {}
cnt = 0
for i in range(m):
    a,b = map(int,input().split())
    if int(a) in ans:
        cnt += 1
    if int(b) in ans:
        cnt += 1
    if int(a) not in ans:
        ans[a] = 1
    if int(b) not in ans:
        ans[b] = 1

r = (n-4)+cnt
if r < 0 or r >= n -2:
    r = 0

print(n-len(ans)+r)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
if n - 1 -m < 0:
  print(0)
else:
  print(n-1-m)

Submission status: Wrong Answer

Solution code:
n,m = (int(x) for x in input().split()) 
alist =[]
blist =[]
for i in range(m):
    a,b = (int(x) for x in input().split()) 
    alist = alist + [a]
    blist = blist + [b]
for i in range(m):
    for j in range(m):
        if alist[j-1] == i:
            blist[j-1] = i
        if blist[j-1] == i:
            alist[j-1] = i
world1 = set(alist)
world2 = set(blist)
world  = world1|world2
print(len(world)-1)

Submission status: Wrong Answer

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

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()))
uf = UnionFind(N)
count = 0
for i in range(M):
    A,B = list(map(int,input().split()))
    A,B = A-1,B-1
    if uf.find(A)!=uf.find(B):
        uf.union(A,B)
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
arr = set()
ans = 0
for i in range(m):
    a, b = list(map(int, input().split()))
    t = tuple([a,b])
    if t not in arr:
        arr.add(t)
        ans += 1
print(n-1-ans)

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]:
            if not j in visited:
                #count += 1
                visited.add(j)
                #print(i,j,visited)
        


    return count-1

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

Submission status: Wrong Answer

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

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

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

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

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

    pairs.sort()
    for pair in pairs:
        uf.set(pair[0], pair[1])
    #
    # for pair in pairs:
    #     uf.set(pair[0], pair[1])

    root = []
    for i in range(n):
        root.append(uf.root(i))
 #       print(i, uf.root(i))
    single_root = set(root)

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

Submission status: Wrong Answer

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

dup = [tuple(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 = map(int,input().split())
L = [list(map(int,input().split())) for _ in range(M)]

# print(L)

city = [1]*(N+1)

#print(cities)

for l in L:
    city[l[0]] = 0
    city[l[1]] = 0

#print(cities)

ans = sum(city) - 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N,M = list(map(int,input().split()))
town = set()
towns = []

for i in range(M):
    a,b = list(map(int,input().split()))
    town.add(a)
    town.add(b)
    towns.append([a,b])
        
sorted(town)
town = list(town)    

connected = [towns[0]]

for i in range(1,len(towns)):
    f = False
    for c in connected:
        if towns[i][0] in c:
            c.append(towns[i][1])
            f = False
        elif towns[i][1] in c:
            c.append(towns[i][0])
            f = False
        else:
            f = True
    if f:
        connected.append(towns[i])
            

#print(connected)

if N == 2:
    print(0)


else:
    p = N-len(town)+len(connected)-1
    print(int(p*(p-1)/2)+1)

Submission status: Wrong Answer

Solution code:
def solve(city_arr, road_arr):
    # points = [road_arr[0][0],road_arr[0][1]]
    starts = [road[0] for road in road_arr]
    ends = [road[1] for road in road_arr]
    points = starts
    points.extend(ends)
    set_cities = set(points)
    used = [False for road in road_arr]
    is_end = True
    counta = 0
    idx = 0
    current = ends[0]
    used[0] = True
    while all(used):
        try:
            idx = starts.index(current)
            used[idx] = True
            current = ends[idx] if is_end else starts[idx]
        except:
            counta +=1
            try:
                idx = used.index(False)
                current = ends[idx] if is_end else starts[idx]
            except:
                counta += len(city_arr) - len(points) - 1
                return counta
    return counta

    
if __name__ == '__main__':
    num_cities, num_roads = [int(i) for i in input().split()]
    roads = [[int(i) for i in input().split()] for j in range(num_roads)]
    cities = range(1, num_cities + 1)
    ans = solve(cities, roads)
    print(ans)

Submission status: Wrong Answer

Solution code:
a, b = input().split()
#L = [input() for i in range(int(b))]
print(str(int(a)-int(b)))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A=[[]]*N
for i in range(N):
  A[i]=set([i])

for i in range(M):
  a, b = map(int, input().split())
  
  A[a-1] = A[a-1]|A[b-1]
  A[b-1] = A[a-1]
  
mlen = 0
for i in range(N):
  mlen = max(mlen, len(A[i]))
  
print(N-mlen)

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
            else:
                counter += 1
        return counter
 
 
def main():
    # 頂点および辺の最大値
    max_v, max_e = map(int, input().split())
    # 隣接リスト
    adj_vertices = collections.defaultdict(list)
    for _ in range(max_e):
        # 入力は1始まりであるので、これを0始まりに変換する
        u, v = map(lambda x: int(x) - 1, input().split())
        adj_vertices[u].append(v)
        adj_vertices[v].append(u)
    bfs = BreadthFirstSearch(max_v, max_e, adj_vertices)
    print(bfs.count_trees()-1)
 
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# cook your dish here
s=[int(i) for i in input().strip().split()]
n=s[0]
m=s[1]
l=[]
for i in range(0,m):
    s=[int(i) for i in input().strip().split()]
    l.append(s[0])
    l.append(s[1])
p=set(l)
print(n-len(p))

Submission status: Wrong Answer

Solution code:
#ACLBC
n,m = map(int,input().split())
t = [-1]*n
cnt = 0
stc = []
#for i in range(n):
#    t.append([])
for i in range(m):
    a,b = map(int,input().split())
    if(t[a-1] == -1):
        if(t[b-1] == -1):
            t[a-1] = cnt
            t[b-1] = cnt
            cnt += 1
        else:
            t[a-1] = t[b-1]
            cnt += 1
    else:
        if(t[b-1] == -1):
            t[b-1] = t[a-1]
            cnt += 1
        elif(t[a-1] != t[b-1]):
            if(not [t[a-1],t[b-1]] in stc):
                stc.append([t[a-1],t[b-1]])
                cnt += 1
print(n-1-cnt)

Submission status: Wrong Answer

Solution code:
line= input().split(" ")
a=int(line[0])
b=int(line[1])
listnum=[]
for i in range(a):
    listnum.append(i)

for i in range(b):
    line= input().split(" ")
    c=int(line[0])-1
    d=int(line[1])-1
    listnum[d]=listnum[c]

listnum.sort()
#print(listnum)
lis2=[]
lis2.append(listnum[0])
for i in range(1,a):
    if listnum[i]!=listnum[i-1]:
        lis2.append(listnum[i])

print(len(lis2)-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
c, r = input("").split(" ")

cityOne, cityTwo = input("").split(" ")
c, r, cityOne, cityTwo = int(c), int(r), int(cityOne), int(cityTwo)
nr = 0
if r %2!=0 and r != c - 1:
    nr += 1
else:
    nr+=2
print(nr)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,m=map(int,input().split())
ab=[]
data=[[] for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  ab.append([a,b])
  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:
N, M = map(int, input().split())
l = [list(map(int, input().split())) for l in range(M)]
sl = sorted(l)
flag = [0 for i in range(N)]
ans = 0
i = sl[0][0]
for s in sl:
    if s[0] == i:
        flag[i - 1] = 1
        flag[s[1] - 1] = 1
    else:
        if 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(str(ans + flag.count(0)))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
C=[0]*N
team=0
count=N-1
for i in range(M):
  A,B=map(int,input().split())
  if C[A-1]==0 and C[B-1]==0:
    team+=1
    count-=1
    C[B-1]=team
    C[A-1]=team
  elif C[A-1]==0:
    C[A-1]=C[B-1]
    count-=1
  elif C[B-1]==0:
    C[B-1]==C[A-1]
    count-=1
  elif C[B-1]==C[A-1]:
    count=count
  else:
    C[B-1]=min(C[A-1],C[B-1])
    C[A-1]=min(C[A-1],C[B-1])
    count-=1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
number=input().rstrip().split(' ')
N=int(number[0])
M=int(number[1])
judge=np.zeros([N-1])


for i in range(M):
    cities=input().rstrip().split(' ')
    A=int(cities[0])
    judge[A-1]=1

print(np.count_nonzero(judge==0))

Submission status: Wrong Answer

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

emp=[[] for i in range(n)]
lis=[False for i in range(n)]

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

def ser(x):
    global ans
    while len(emp[x])>0:
        y=emp[x].pop()
        if lis[y]==False:
            lis[y]=True
            ans-=1
            ser(y)
        

for i in range(n):
    ser(i)

print(ans)

Submission status: Wrong Answer

Solution code:
NM=list(map(int,input().split()))
ans=NM[0]-1-NM[1]
print(ans)

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] += (second,)
        d[second]+=(first,)
    # print(d)
    temp = []
    for city in d:
        t = (city, )
        t += d[city]
        temp.append(t)
    for i in range(len(temp)):
        temp[i] = sorted(temp[i])
    # 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]=[int(_) for _ in input().split()]
C=set([i for i in range(1,N+1)])
R=[]
for m in range(M):
  [A,B]=[int(_) for _ in input().split()]
  C.discard(A)
  C.discard(B)
  f=False
  for r in R:
    if A in r:
      r.append(B)
      f=True
      break
  if not f:
    R.append([A,B])
#print(*R)
#print(*C)

S=[set(R[0]),]
for i in range(1,len(R)):
  f = False
  #print(R[i], *S)
  for r in R[i]:
    for j, s in enumerate(S):
      S[j] = s.union(set(R[i]))
      f = True
      break
  if not f:
    S.append(set(R[i]))
#  print(*S)

print(len(S)+len(C)-1)

Submission status: Wrong Answer

Solution code:
c, r = input("").split(" ")

cityOne, cityTwo = input("").split(" ")
c, r, cityOne, cityTwo = int(c), int(r), int(cityOne), int(cityTwo)
nr=0
if r!=c-1:
    nr+=1

print(nr)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = []
cnt = 0
for i in range (m):
    a, b = map(int, input().split()) 
    if (a in l) or (b in l):
        l.append(a)
        l.append(b)
        
    else:
        l.append(a)
        l.append(b)
        cnt += 1
        
    l = set(l)
    l = list(l)
    
x = n - len(l) 

print(cnt+x)

Submission status: Wrong Answer

Solution code:

def main():
    N, M = map(int, input().split())

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


main()

Submission status: Wrong Answer

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

num = list(range(1, N+1))

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

print(N - M - 1)

Submission status: Wrong Answer

Solution code:
n,m = list(map(int, input().split()))
edges = []
for _ in range(m):
    a,b = list(map(int, input().split()))
    edges.append((a-1,b-1))


group = [-1] * n
merges = [set()] * n
nmerges = 0
gid = -1
for e in edges:
    if e[0] == e[1]: continue
    if group[e[0]] == -1 and group[e[1]] == -1:
        gid += 1
        group[e[0]] = group[e[1]] = gid
    elif group[e[0]] == -1 and group[e[1]] != -1:
        g = group[e[1]]
        group[e[0]] = g
    elif group[e[0]] != -1 and group[e[1]] == -1:
        g = group[e[0]]
        group[e[1]] = g
    else:
        if group[e[0]] != group[e[1]]:
            # Merge
            g0,g1 = group[e[0]],group[e[1]]
            if g0 > g1:
                g0,g1 = g1,g0
            if g1 not in merges[g0]:
                nmerges += 1
                merges[g0].add(g1)

cnt = gid - nmerges
cnt += sum(map(lambda gid: gid == -1, group))
print(cnt)

Submission status: Wrong Answer

Solution code:
# 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?

# Solution:
#   The road data needs to be completely sorted so we don't get two disparate groups
#   suddenly being joined.
#   Each road either creates a new group or extends an existing one.
#   Use array GROUP for this purpose, all initialized to None.
#   After processing all roads, do a linear scan to count the Nones. We will already
#   know how many groups there are.
#   If there are 6 groups, then 5 roads will ensure they are all connected.
#   If there are 4 Nones, then 4 roads are needed to connect them to groups.
#   Answer = (#groups - 1) + #Nones

# Read N (number of cities) and M (number of roads).
N, M = [int(x) for x in input().split()]
# Read A (details of roads) and sort the list.
A = []
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    A.append((a,b))
A.sort()
# Initialise GROUP (the group to which each ciy belongs). We use indices 1..N.
GROUP = [None for _ in range(N+1)]
# G is the most recent group number. Increment before assigning a new group.
G = 0

# Process each road.
for a,b in A:
    #print((a,b), GROUP[1:])
    if GROUP[a] and GROUP[b]:
        # I believe this should not logically happen.
        break
    elif GROUP[a]:
        GROUP[b] = GROUP[a]
    elif GROUP[b]:
        GROUP[a] = GROUP[b]
    else:
        # Neither has a group; we start a new one.
        G += 1
        GROUP[a] = G
        GROUP[b] = G

# Linear scan to count what we have. Ignore index 1.
num_nones = 0
for i in range(1,N+1):
    if GROUP[i] == None:
        num_nones += 1

# Get the answer.
answer = (G-1) + num_nones

print(answer)

Submission status: Wrong Answer

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

emp=[[] for i in range(n)]
lis=[[False] for i in range(n)]

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

def ser(x):
    while len(emp[x])>0:
        y=emp[x].pop()
        if lis[y]==False:
            lis[y]=True
            ans-=1
            ser(y)
        

for i in range(n):
    ser(i)

print(ans)

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

maps = [1] * n
countMakeRoads = 0

for i in range(m):
    ai, bi = list(map(int, input().strip().split()))
    if  maps[ai-1] == ai:
        maps[bi-1] = bi
    elif maps[bi-1] == bi:
        maps[ai - 1] = ai
    else:
        countMakeRoads += 1
        maps[ai - 1] = ai
        maps[bi - 1] = bi

for i in range(n):
    if maps[i] != i+1:
        countMakeRoads += 1
        maps[i] = i+1
print(countMakeRoads)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(' '))
AB = [map(int, input().split(' ')) for _ in range(M)]
A, B = [set(i) for i in zip(*AB)]
 
print(len(set(range(1, N + 1)).difference(A) & set(range(1, N + 1)).difference(B)))

Submission status: Wrong Answer

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

List = [0] * N
for i in range(M):
    town_now = town[i]
    List[town_now[0] - 1] += 1
    List[town_now[1] - 1] += 1

print(List.count(0))

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

graph, seen = [], []
for _ in range(N):
  graph.append([])
  seen.append(0)

for i in range(M):
  graph[x[i]-1].append(y[i]-1)

def dfs(i):
  stack = []
  stack.append(i)
  while stack:
    tmp = stack.pop()
    seen[tmp] = 1
    stack.extend(graph[tmp])

count = -1
for i in range(N):
  if not seen[i]:
    dfs(i)
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
r = [list(map(int,input().split())) for i in range(m)]
g = [-1]*(n+1)


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

group_num = 1;

for i, x in enumerate(r):
  x1 = x[0]
  x2 = x[1]
  if g[x1] == -1 and g[x2] == -1:
    g[x1] = group_num
    g[x2] = group_num
    group_num += 1
  elif g[x1] == -1 or g[x2] == -1:
    if g[x1] > g[x2]:
      g[x2] = g[x1]
    else:
      g[x1] = g[x2]
  else:
    if g[x1] > g[x2]:
      g[x1] = g[x2]
    else:
      g[x2] = g[x1]
del g[0]
print(group_num-1+g.count(-1)-1)

Submission status: Wrong Answer

Solution code:
places = []
N,M = map(int, input().split())
for i in range(M):
  start, end = map(int,input().split())
  places.append(start)
  places.append(end)
  
places = set(places)
print(N - len(places))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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")
    if len(set_connect_str) != 1:
        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())
ls = []
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
            break
        elif b in ls[i]:
            ls[i].append(a)
            x = 1
            break
    if x == 0:
        ls.append([a,b])
ans = 0
print(len(ls)-1)

Submission status: Wrong Answer

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

cl_c=[]
ans = 0

for i in range(m) :
  a,b = map(int,input().split())
  cl_c.append(a)
  cl_c.append(b)
  if a != 1 :
    ans += 1
  set(cl_c)

print(n-len(cl_c))

Submission status: Wrong Answer

Solution code:
# cook your dish here
s=[int(i) for i in input().strip().split()]
n=s[0]
m=s[1]
l=[]
for i in range(0,m):
    s=[int(i) for i in input().strip().split()]
    l.append(s[0])
    l.append(s[1])

print(n-max(l))

Submission status: Wrong Answer

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

f = [0] * N
t = [0] * N
#print(l)
l = [0] * N

for i in range(M):
    x, y = map(int, input().split())
    f[x-1] = f[x-1] + 1
    t[y-1] = t[y-1] + 1
    l[x -1] = 1
    l[y -1] = 1

ans = N-1-M

print(ans)

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
    res = n - len(connected[0])
    print(res, n , connected[0])
    return len(connected) + res - 1

Submission status: Wrong Answer

Solution code:
c, r = input("").split(" ")

cityOne, cityTwo = input("").split(" ")
c, r, cityOne, cityTwo = int(c), int(r), int(cityOne), int(cityTwo)
nr = c - 1 - r
print(nr)

Submission status: Wrong Answer

Solution code:
if __name__=="__main__":
  N,M=map(int,input().split())
  for _ in range(M):
    a,b=[int(i) for i in input().split()]
  print(N-M-1)