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: Runtime Error

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

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



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


uf = UnionFind(N)
for i in range(M):
    uf.union(A[i], B[i])
print(uf.group_count()-1)

Submission status: Runtime Error

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

ab = [map(int, input().split()) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]

can_stay = []
branch_stay = []
can_flag_a = 0
can_flag_b = 0
branch_node = 0
need_road = 0

can_stay.append(a[0])
can_stay.append(b[0])

for road in range(1, m):
    can_flag_a = 0
    can_flag_b = 0
    for cnt_can in range(len(can_stay)):
        if can_stay[cnt_can] == a[road]:
            can_flag_a = 1
    for cnt_can in range(len(can_stay)):
        if can_stay[cnt_can] == b[road]:
            can_flag_b = 1

    if can_flag_a == 1 and can_flag_b == 0:
        can_stay.append(b[road])
    elif can_flag_a == 0 and can_flag_b == 1:
        can_stay.append(a[road])
    elif can_flag_a == 0 and can_flag_b == 0:
        branch_stay.append([a[road], b[road]])

    if len(branch_stay) >= 2:
        for cnt_road in range(len(branch_stay) - 1):
            del_flag = 0
            for cnt_len in range(len(branch_stay[cnt_road])):
                for cnt_sub_len in range(len(branch_stay[cnt_road+1])):
                    if branch_stay[cnt_road][cnt_len] == branch_stay[cnt_road+1][cnt_sub_len]:
                        del branch_stay[cnt_road][cnt_len]
                        for length in range(branch_stay[cnt_road]):
                            branch_stay[cnt_road+1].append(branch_stay[cnt_road][length])
                        break
            if del_flag == 1:
                del branch_stay[cnt_road]
                break


    if len(branch_stay) >= 1:
        for cnt_road in range(len(branch_stay)):
            del_flag = 0
            for cnt_main in range(len(can_stay)):
                for cnt_sub in range(len(branch_stay[cnt_road])):
                    if can_stay[cnt_main] == branch_stay[cnt_road][cnt_sub]:
                        del branch_stay[cnt_road][cnt_sub]
                        for cnt_add in range(len(branch_stay[cnt_road])):
                            can_stay.append(branch_stay[cnt_road][cnt_add])
                        del_flag = 1
            if del_flag == 1:
                del branch_stay[cnt_road]
                break

if len(branch_stay) > 0:
    for cnt in range(len(branch_stay)):
        branch_node += len(branch_stay[cnt])

if len(branch_stay) > 0:
    need_road = n - len(can_stay) - branch_node + len(branch_stay)
else:
    need_road = n - len(can_stay)

print(need_road)

Submission status: Runtime Error

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 != c - 1:
    nr += 1
else:
    nr+=2
print(nr)

Submission status: Runtime Error

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

rootedPoints = set()
points = []

for _ in range(M):
  A, B = map(int, input().split())
  rootedPoints.add(A)
  rootedPoints.add(B)
  Aindex = False
  Bindex = False
  for i, ps in enumerate(points):
    if A in ps: Aindex = i
    if B in ps: Bindex = i
    if Aindex is not False and Bindex is not False: break
  if Aindex is False and Bindex is False:
    points.append({A, B})
  elif Aindex is False:
    points[Bindex].add(A)
  elif Bindex is False:
    points[Aindex].add(B)
  elif Aindex!=Bindex:
    points[Aindex] |= points[Bindex]
    points[Bindex] = False
  #print(points)
print(len(tuple(pp for pp in points if pp!=False))-1+N-len(rootedPoints))

Submission status: Runtime Error

Solution code:
def main():
    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())


    c = [0] * n
    for i in range(m):
        c[a[i]] = 1
        c[b[i]] = 1

        
    count = 0
    for i in range(n):
        if c[i] == 0:
            count += 1

    print(count)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, M = input().split()
N = int(N)
M = int(M)
l = []
l2 = []
for i in range(N):
  l.append(i)
for i in range(M):
  A, B = input().split()
  A = int(A)
  B = int(B)
  if A in l:
    pass
  else:
    l2.append(l.pop(int(A) - 1))
  if B in l:
    pass
  else:
    l2.append(l.pop(int(B) - 1))
print(N - len(l) + 1)

Submission status: Runtime Error

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,b)
  if a != 1 :
    ans += 1
  set(cl_c)

print(n-len(cl_c)+ans)

Submission status: Runtime Error

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

seen = [False] * N

def dfs(G, v):
    global seen
    seen[v] = True
    for n_v in G[v]:
        if seen[n_v]:
            continue
        dfs(G, n_v)

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

count = 0
for v in range(N):
    if seen[v]:
        continue
    dfs(G, v)
    count += 1

print(count-1)

Submission status: Runtime Error

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)

print(c.count(False))

Submission status: Runtime Error

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

par = [i for i in range(n)]
connection = [i for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    cur = connection[b]
    connection[b] = connection[a]
    if par[cur] != a:
        par[cur] = a
for i in range(n):
    num = connection[i]
    connection[i] = par[num]
ans = len(set(connection)) - 1
print(ans)

Submission status: Runtime Error

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

for i in range(M):
  temp=list(map(lambda x: x-1, map(int, input().split(" "))))
  graph[temp[0]].append(temp[1])
  graph[temp[1]].append(temp[0])

seen=[False for i in range(N)]
todo=[]

def seek(graph, current):
  seen[current]=True
  for city in graph[current]:
    if seen[city]:
      continue
    seek(graph, city)

seek(graph, 0)

candidate=[i for i in range(len(seen)) if seen[i]==False]

count=0
for i in candidate:
  graph[0].append(i)
  count=count+1
  seek(graph, 0)
  if seen.count(False)==0:
    break
print(count)

Submission status: Runtime Error

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())
uf = Unionfind(n)


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

print(uf.group_count()-1)

Submission status: Runtime Error

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 != c - 1:
    nr += 1
else:
    nr+=2
print(nr)

Submission status: Runtime Error

Solution code:
from math import factorial


def main():
    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())


    c = [0] * n
    for i in range(m):
        c[a[i]] = 1
        c[b[i]] = 1


    sum = factorial(n) / 2 * factorial(n - 2)
    if sum <= m:
        print(0)
        exit()

    count = 0
    for i in range(n):
        if c[i] == 0:
            count += 1

    print(count)





if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

c = [False] * n

print(c)

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

print(c)

print(c.count(False))

Submission status: Runtime Error

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

for v in range(M):
    for w, c in enumerate(map(lambda x: int(x)-1, input().split())):
        if c != -1:
            G[v].append((w, c))

from heapq import heappush, heappop, heapify
used = [0]*N
que = [(c, w) for w, c in G[0]]
used[0] = 1
heapify(que)

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for w, c in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
print(ans)

Submission status: Runtime Error

Solution code:
def s(way):
    global w
    global wc

    for i in way:
        c[i] = 1
        if wc[i] == 0:
            wc[i] =1
            for j in w[i]:
                c[j]=1
            for j in w[i]:
                s(w[j])


n,m = map(int,input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
w = [[] for i in range(n)]
wc = [0 for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    w[a[i]-1].append(b[i]-1)
    w[b[i]-1].append(a[i]-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        wc[i] = 1
        ans += 1
        s(w[i])

print(ans)

Submission status: Runtime Error

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

rootedPoints = set()
points = []

for _ in range(M):
  A, B = map(int, input().split())
  rootedPoints.add(A)
  rootedPoints.add(B)
  Aindex = False
  Bindex = False
  for i, ps in enumerate(points):
    if A in ps: Aindex = i
    if B in ps: Bindex = i
  if Aindex is False and Bindex is False:
    points.append({A, B})
  elif Aindex is False:
    points[Bindex].add(A)
  elif Bindex is False:
    points[Aindex].add(B)
  elif Aindex!=Bindex:
    points[Aindex] |= points[Bindex]
    points[Bindex] = False
  print(points)
print(len(tuple(pp for pp in points if pp!=False))-1+N-len(rootedPoints))

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))

N = a[0]
M = a[1]

cities = [0] * N
roads = []

lands = {}
for i in range(M):
    a = list(map(int,input().split()))
    roads.append([a[0], a[1]])

for r in roads:
    #print(cities)
    #print(lands)
    if cities[r[0]-1] == 0:
        cities[r[0]-1] = r[0]
        lands[r[0]] = [r[0]]
    
    if cities[r[1]-1] == 0:
        cities[r[1]-1] = r[0]
        lands[r[0]].append(r[1])
    else:
        #print(cities[r[1]-1])
        #print(cities[r[1]-1] in lands)
        if cities[r[1]-1] in lands:
            lands[cities[r[0]-1]].extend(lands[cities[r[1]-1]])
            
            for i in range(len(lands[r[1]-1])):
                cities[lands[r[1]-1][i]-1] = cities[r[0]-1]
            del lands[r[1]-1]
        #else:
        #    cities[r[1]-1] = r[0]
        #    lands[r[0]-1].append()


#print(cities)
#print(cities)
#print(lands)
found = {}
zero_count = 0
for i in range(N):
    if cities[i] != 0:
        found[cities[i]] = 1
    else:
        zero_count += 1

print(len(found) - 1 + zero_count)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
AB=list()
memo=[False]*N
G=defaultdict(set)
def dfs(i):
    memo[i]=True
    for j in G[i]:
        if memo[j]==False:
            dfs(j)
count=0
for i in range(M):
    AB=list(map(int,input().split()))
    G[AB[1]-1].add(AB[0]-1)
    G[AB[0]-1].add(AB[1]-1)
for i in range(N):
    if memo[i]==False:
        dfs(i)
        count+=1
print(count-1)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
cityList = set()
loadList = []
for i in range(M):
    loadList.append(set(list(map(int,input().split()))))
    if(i >= 1):
        if(len(loadList[0] & loadList[i]) != 0):
            loadList[0] = loadList[0] | loadList[i]
            del loadList[i]
for i in range(N):
    cityList.add(i + 1)
#print(loadList[0])
#print(cityList)
j = 0
ans = 0
while(len(loadList) != 1):
    k = 1
    for k in range(len(loadList)):
        set_cap = loadList[0] & loadList[k]
        if(len(set_cap) != 0):
            loadList[0] = loadList[0] | loadList[k]
            del loadList[k]
            ans += 1
gap = cityList - loadList[0]
ans += len(gap)
print(ans)

Submission status: Runtime Error

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!=i-1:
    nr+=1

print(nr)

Submission status: Runtime Error

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] = t
        else:
            self.pairs[t] = 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: Runtime Error

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


print(uf.group_count()-1)

Submission status: Runtime Error

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.
        print("Logical error")
        exit(1)
    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: Runtime Error

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

rootedPoints = set()
points = []

for _ in range(M):
  A, B = map(int, input().split())
  rootedPoints.add(A)
  rootedPoints.add(B)
  Aindex = False
  Bindex = False
  for i, ps in enumerate(points):
    if A in ps: Aindex = i
    if B in ps: Bindex = i
  if Aindex is False and Bindex is False:
    points.append({A, B})
  elif Aindex==False:
    points[Bindex].add(A)
  elif Bindex==False:
    points[Aindex].add(B)
  elif Aindex!=Bindex:
    points[Aindex] |= points[Bindex]
    points[Bindex] = False
  #print(points)
print(len(tuple(pp for pp in points if pp!=False))-1+N-len(rootedPoints))

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
allone = list(range(1,n+1))
paths = []
for l in range(m):
  tempa,tempb = map(int,input().split())
  paths.append([tempa,tempb])
  allone.remove(tempa)
  allone.remove(tempb)
cou = 0
if allone:
  for r in allone:
    su = False
    for o in paths:
      if r == o[0] or r == o[1]:
        continue
      else:
        su = True
    if su == True:
      cou += 1
  print(cou)
else:
  print(0)

Submission status: Runtime Error

Solution code:
def s(way):
    global w
    global wc

    for i in way:
        c[i] = 1
        if wc[i] == 0:
            wc[i] =1
            for j in w[i]:
                c[j]=1
                s(w[j])


n,m = map(int,input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
w = [[] for i in range(n)]
wc = [0 for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    w[a[i]-1].append(b[i]-1)
    w[b[i]-1].append(a[i]-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        wc[i] = 1
        ans += 1
        s(w[i])

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int,input().split())
allone = list(range(1,n+1))
paths = []
for l in range(m):
  tempa,tempb = map(int,input().split())
  paths.append([tempa,tempb])
  allone.remove(tempa)
  allone.remove(tempb)
cou = 0
for r in allone:
  su = False
  for o in paths:
    if r == o[0] or r == o[1]:
      continue
    else:
      su = True
  if su == True:
    cou += 1
print(cou)

Submission status: Runtime Error

Solution code:
# C
[N, M] = [int(k) for k in input().split()]
dic = {}
L = []

for j in range(M):
    [A, B] = [int(i) for i in input().split()]
    if A in dic:
        if B in dic:
            L.pop(dic[B])
            for m in dic:
                if dic[m] == dic[B]:
                    dic[m] = dic[A]
        else:
            L[dic[A]].append(B)
            dic[B] = dic[A]
    else:
        l = [A, B]
        L.append(l)
        dic[A] = len(L)-1
        dic[B] = len(L)-1
    if B in dic:
        L[dic[B]].append(A)
        dic[A] = dic[B]
    else:
        l = [A, B]
        L.append(l)
        dic[A] = len(L)-1
        dic[B] = len(L)-1

t = 0
for i in range(1, N+1):
    if i not in dic:
        t += 1

print(len(L) + t - 1)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
road=[[] for i 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)

d=[-1]*n
d[0]=1
f=[-1]*n
count=1
def dfs(src):
    d[src]=count
    for dst in road[src]:
        if d[dst]==-1:
            dfs(dst)
for root in range(n):
    if d[root]==-1:
        dfs(root)
        count+=1
print(count-2)

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
c = []
for i in range(N):
  A,B = map(int, input().split())
  if A not in c:
    c.append(A)
  if B not in c:
    c.append(B)
print(N - len(c))

Submission status: Runtime Error

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

def dfs(G, v):
    seen[v] = True
    for n_v in G[v]:
        if seen[n_v]:
            continue
        dfs(G, n_v)

seen = [False] * N
G = [[]] * N
for _ in range(M):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

count = 0
for v in range(N):
    if seen[v]:
        continue
    dfs(G, v)
    count += 1

print(count-1)

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))

N = a[0]
M = a[1]

cities = [0] * N
roads = []

lands = {}
for i in range(M):
    a = list(map(int,input().split()))
    roads.append([a[0], a[1]])

for r in roads:
    #print(cities)
    #print(lands)
    if cities[r[0]-1] == 0:
        cities[r[0]-1] = r[0]
        lands[r[0]] = [r[0]]
    
    if cities[r[1]-1] == 0:
        cities[r[1]-1] = r[0]
        lands[r[0]].append(r[1])
    else:
        #print(cities[r[1]-1])
        #print(cities[r[1]-1] in lands)
        if cities[r[1]-1] in lands:
            for i in range(len(lands[r[1]-1])):
                cities[lands[r[1]-1][i]-1] = cities[r[0]-1]
            lands[r[0]-1].extend(lands[r[1]-1])
            del lands[r[1]-1]
        #else:
        #    cities[r[1]-1] = r[0]
        #    lands[r[0]-1].append()


#print(cities)
#print(cities)
#print(lands)
found = {}
zero_count = 0
for i in range(N):
    if cities[i] != 0:
        found[cities[i]] = 1
    else:
        zero_count += 1

print(len(found) - 1 + zero_count)

Submission status: Runtime Error

Solution code:
def s(way):
    global w
    global wc

    for i in way:
        c[i] = 1
        if wc[i] == 0:
            wc[i] =1
            for j in w[i]:
                c[j]=1
                s(w[i])


n,m = map(int,input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
w = [[] for i in range(n)]
wc = [0 for i in range(n)]
c = [0 for i in range(n)]
for i in range(m):
    a[i],b[i] = map(int,input().split())
    w[a[i]-1].append(b[i]-1)
    w[b[i]-1].append(a[i]-1)
ans =-1
for i in range(n):
    if c[i] == 0:
        c[i] = 1
        wc[i] = 1
        ans += 1
        s(w[i])

print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
from collections import defaultdict

def read_int(x):
  return int(x)

def dec(x):
  return x - 1

def inc(x):
  return x + 1

def update_dic(dic,key):
  _ = dic[key]
  return dic

def read_lst(x):
  return list(map(read_int,x.split(' ')))

def read_roads(cnt):
  return reduce(lambda x,_: x + read_lst(input()), range(cnt), [])

def find_roads_to_be_laid(cities,roads):
  if dec(len(roads)) == cities:
    return 0
  else:
    return cities - len(reduce(lambda rods,road: (lambda x,y: update_dic(update_dic(rods,y),x))(road[0],road[1]),
                      roads,
                      defaultdict(lambda : 0)).keys())

def main():
  [n,m] = read_lst(input())
  roads = read_roads(m)
  print(find_roads_to_be_laid(n,roads))
  
main()

Submission status: Runtime Error

Solution code:
def dfs(now_node):
    seen[now_node] = True
    connect_nodes = graph[now_node]
    for node in connect_nodes:
        if seen[node] == True:#探索済みだったらスルー
            continue
        dfs(node)

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

graph = [[] for i in range(N+1)]
#隣接リストの作成
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])
#訪問済みリストの作成
seen = [False for i in range(N+1)]
seen[0] = True
#全ノードが訪問済みになるまで探索
count = 0
for i in range(N+1):
    if seen[i]:#探索済みだったらスルー
        continue
    dfs(i)
    count += 1

print(count-1)

Submission status: Runtime Error

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

rootedPoints = set()
points = []

for _ in range(M):
  A, B = map(int, input().split())
  rootedPoints.add(A)
  rootedPoints.add(B)
  Aindex = False
  Bindex = False
  for i, ps in enumerate(points):
    if A in ps: Aindex = i
    if B in ps: Bindex = i
  if Aindex==False and Bindex==False:
    points.append({A, B})
  elif Aindex==False:
    points[Bindex].add(A)
  elif Bindex==False:
    points[Aindex].add(B)
  elif Aindex!=Bindex:
    points[Aindex] |= points[Bindex]
    points[Bindex] = False
print(len(tuple(pp for pp in points if pp!=False))-1+N-len(rootedPoints))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
AB=list()
memo=[False]*N
G=defaultdict(list)
def dfs(i):
    memo[i]=True
    for j in G[i]:
        if memo[j]==False:
            dfs(j)
count=0
for i in range(M):
    AB=list(map(int,input().split()))
    G[AB[1]-1].append(AB[0]-1)
    G[AB[0]-1].append(AB[1]-1)
for i in range(N):
    if memo[i]==False:
        dfs(i)
        count+=1
print(count-1)

Submission status: Runtime Error

Solution code:
C = []
N, M = map(int,input().split())
for i in range(M):
    a,b=input().split()
    C.append(int(a))
    C.append(int(b))
                


test = sorted(list(set(C)))

cnt = 1
x =len(test)

for i in range(1,x):
  keep = test[i] - test[i-1]
  if keep > 1:
    keep = test[i+1] - test[i]
    if keep > 1:
      cnt +=1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7+1)

N,M = map(int,input().split())
ans = N
V = [i for i in range(N)]
inp = []
E =[[] for i in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
visited = [False for _ in range(N)]
def dfs(v,parent,origin):
    visited[v] = True
    for e in E[v]:
        if e == parent:
            continue
        V[e] = origin
        dfs(e,v,origin)

for i in range(N):
    if visited[i]:
        continue
    dfs(i,-1,i)
count = 0
for i,v in enumerate(V):
    if i==v:
        count+=1

print(count-1)

Submission status: Runtime Error

Solution code:
import copy
def check_root(root,num):

  if(root[num-1]==num):
    return num
  else:
    ans = check_root(root,root[num-1])
    root[ans-1]=ans
    return ans
def reset_root(root):
  new_root = copy.copy(root)
  for i in range(len(root)):
    new_root[i] = check_root(root,i)
  return new_root

def connect_root(root,A,B):
  if root.count(A) < root.count(B):
    root[A] = B
  else:
    root[B] = A
  #reset_root(root)
  return root

def count_root(root):
  root_num = []
  for i in range(len(root)):
    flag = 0
    for j in range(len(root_num)):
      if ( root[i]==root_num[j]):
        flag=1
    if(flag==0):
      root_num.append(root[i])

  return len(root_num)
  

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

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

root =[]
for i in range(N):
  root.append(i+1)
  

for i in range(M):
  root_A =check_root(root,load[i][0])
  root_B =check_root(root,load[i][1])
  if not (root_A==root_B):
    connect_root(root,root_A,root_B)

root = reset_root(root)
print(count_root(root)-1)