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

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):
    a,b = map(int,input().split())
    uf.union(a,b)

print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split(' ')]
city_s=set(range(1,N+1))

for j in range(0, M):
    A, B = [int(x) for x in input().split(' ')]
    if j == 0:
        dic={}
        dic[0]=[A,B]
    if j != 0:
        for i in range(len(dic)):
            print(i)
            if x in dic[i]:
                dic[i].append(y)
                break
            elif y in dic[i]:
                dic[i].append(x)
                break
            else:
                if i == len(dic)-1:
                    dic[len(dic)]=[x,y]
for i in range(len(dic)):
    city_s=city_s-set(dic[i])
print(len(city_s)+len(dic)-1)

Submission status: Runtime Error

Solution code:
3 1
1 2

Submission status: Runtime Error

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

city = list(str(n) for n in range(1, N+1))
for ab in AB:
    city.remove(ab[0])
    city.remove(ab[1])
    if(len(city) == 0):
        break;
print(len(city))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a = list(range(N))
for i in range(M) :
    A,B = map(int,input().split())
    a.remove(A)
    a.remove(B)
print(int(len(a)+M/2))

Submission status: Runtime Error

Solution code:
def inclusive_index(lst, purpose):
    for i, e in enumerate(lst):
        if purpose in e: return i

    raise IndexError

N, M = map(int,input().split())
lst = [str(i+1) for i in range(N)]

for _ in range(M):
    A, B =  input().split()
    a = inclusive_index(lst, A)
    b = inclusive_index(lst, B)
    lst[a] = lst[a] + lst.pop(b)

print(len(lst)-1)

Submission status: Runtime Error

Solution code:
def dfs(now, prev):
    global flag
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]:
                # 過去に訪れていれば閉路
                flag = False
            else:
                memo[next] = True
                dfs(next, now)


n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

# 訪れたことがあるか
memo = [False for i in range(n)]

ans = 0
# 頂点をループ
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        ans += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
from scipy.special import comb

N, M = [int(i) for i in input().split()]
AB = []

for i in range(M):
  AB[''.join(input().split())] = True

c = 0
for i in range(1, N):
  d = False
  if str(i)+str(i+1) not in AB:
    c += 1
print(c)

Submission status: Runtime Error

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

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

  if a not in tree:
    for t in tree:
      if a in tree[t]:
        tree[t].append(b)
      else:
        tree[a] = [a,b]
    if len(tree) == 0:
      tree[a] = [a,b]
  else:
      tree[a].append(b)
#print(tree)

sum_ = 0
for t in tree:
  sum_ += len(tree[t])

print(N -sum_)

Submission status: Runtime Error

Solution code:
import numpy as np
number=input().rstrip().split(' ')

N=int(number[0])
M=int(number[1])
judge=np.zeros([N-1,N],dtype=np.int16)

for i in range(M):
    cities=input().rstrip().split(' ')
    A=int(cities[0])
    B=int(cities[1])
    judge[A-1][B-1]=1
    
print(np.count_nonzero(np.all(judge==0,axis=1)))

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a = list(range())
for i in range(N) :
    A,B = map(int,input().split())
    a.remove(A)
    a.remove(B)
print(int(len(a)+M/2))

Submission status: Runtime Error

Solution code:
#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
#sort = sorted(a)[::-1] 降順
#if l[i] == l[j]: continue
n, m = map(int, input().split())
req = [list(map(int, input().split())) for _ in range(m)]

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(req[i][0], req[i][1])

print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
def dfs(now, prev):
    global flag
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]:
                # 過去に訪れていれば閉路
                flag = False
            else:
                memo[next] = True
                dfs(next, now)


n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
print(g)

# 訪れたことがあるか
memo = [False for i in range(n)]

ans = 0
# 頂点をループ
for i in range(n):
    if not memo[i]:
        flag = True
        dfs(i, -1)
        ans += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
class AlgUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  #各要素の親要素の番号を格納するリスト 要素が根（ルート）の場合は-(そのグループの要素数)を格納する

    def find(self, x): #要素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が属するグループと要素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): #要素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())

    def all_group_members(self): #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self): #print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for i in range(M)]
    #newA = [n+1 for n in A]
    uf = AlgUnionFind(N)
    for i in range(M):
        uf.union(A[i][0], A[i][1])
    count = uf.group_count() - 1
    print(count)

Submission status: Runtime Error

Solution code:
from collections import deque
N, M = map(int, input().split())
pair={}

for _ in range(M):
    a, b = map(int, input().split())
    if a not in pair:
        pair[a-1]=[b-1]
    else:
        pair[a-1].append(b-1)
    if b not in pair:
        pair[b-1]=[a-1]
    else:
        pair[b-1].append(a-1)
# print(pair)

did=[]
ans=-1
queue=deque()
for i in range(N):
    if i not in did:
        queue.append(i)
    else:
        continue
    while(queue):
        now=queue.pop()
        did.append(now)
        # print(now)
        if now in pair:
            for j in pair[now]:
                if j not in queue and j not in did:
                    queue.append(j)
    ans+=1
print(ans)

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:
def main():
    N, M = map(int, input().split())
    connect_list = [0] * N

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

        if A_road_num == 0 and B_road_num == 0:
            max_road_num = max(connect_list)
            connect_list[A] = max_road_num
            connect_list[B] = max_road_num
        elif A_road_num != 0 and B_road_num == 0:
            connect_list[B] = connect_list[A]
        elif A_road_num == 0 and B_road_num != 0:
            connect_list[A] = connect_list[B]
        else:
            connect_list = [A_road_num if B_road_num == road_num else road_num for road_num in connect_list]

    answer = 0
    set_connect_list = set([i for i in connect_list if i > 0])
    if len(set_connect_list) != 1:
        answer = len(set_connect_list) - 1

    print(answer + connect_list.count(0))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N,M= [int(x) for x in input().split()]

root = list(range(N))

for i in range(M):
    print(root)
    A,B = [int(x)-1 for x in input().split()]
    a = root[A]
    b = root[B]
    if a<b:
        root = [a if i == b else i for i in root]
    if b<a:
        root = [b if i == a else i for i in root]

print(len(set(root))-1)

Submission status: Runtime Error

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# a_list = [0] * a
sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    n, m = get_int_multi()

    aa = [0] * (n+1)
    ans = n-1

    for i in range(0,m):
        a, b = get_int_multi()
        if aa[a] == 0 and aa[b] == 0:  # 独立してたらつなげる
            aa[a] = a
            aa[b] = a
            ans -= 1
        elif aa[a] != 0 and aa[b] == 0:
            aa[b] == aa[a]
            ans -= 1
        elif aa[a] == 0 and aa[b] != 0:
            aa[a] == aa[b]
            ans -= 1
        elif aa[a] != aa[b]:
            ans -= 1
            wk = aa[b]
            for ii in range(m):
                if aa[ii] == wk:
                    aa[ii] = aa[a]


    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
class UnionFind:
    """Union-Find(素集合データ構造)"""
    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node
        
        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int):
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return
    
    def unite(self, x: int, y: int):
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def same(self, x: int, y: int):
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)
    
    def size(self, x: int) -> bool:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1


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

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

    ans = -1
    for i in lst.root:
        if i < 0:
            ans += 1
    print(ans)
    # print(lst.root)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
adj=[[] for k in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    x-=1;y-=1
    adj[x].append(y)
    adj[y].append(x)
numCon=0
visited=[False]*n
def dfs(x):
    visited[x]=True
    for a in adj[x]:
        if visited[a]: continue
        dfs(a)
for i in range(n):
    if not visited[i]:
        dfs(i)
        numCon+=1
print(numCon-1)

Submission status: Runtime Error

Solution code:
class Graph: 
      
    # init function to declare class variables 
    def __init__(self,V): 
        self.V = V 
        self.adj = [[] for i in range(V)] 
  
    def DFSUtil(self, temp, v, visited): 
  
        # Mark the current vertex as visited 
        visited[v] = True
  
        # Store the vertex to list 
        temp.append(v) 
  
        # Repeat for all vertices adjacent 
        # to this vertex v 
        for i in self.adj[v]: 
            if visited[i] == False: 
                  
                # Update the list 
                temp = self.DFSUtil(temp, i, visited) 
        return temp 
  
    # method to add an undirected edge 
    def addEdge(self, v, w): 
        self.adj[v].append(w) 
        self.adj[w].append(v) 
  
    # Method to retrieve connected components 
    # in an undirected graph 
    def connectedComponents(self): 
        visited = [] 
        cc = [] 
        for i in range(self.V): 
            visited.append(False) 
        for v in range(self.V): 
            if visited[v] == False: 
                temp = [] 
                cc.append(self.DFSUtil(temp, v, visited)) 
        return cc 
  
# Driver Code 
if __name__=="__main__": 
      
    # Create a graph given in the above diagram 
    # 5 vertices numbered from 0 to 4 
    N,M = map(int,input().split())
    g = Graph(N)
    for i in range(M):
      a,b = map(int,input().split())
      g.addEdge(a,b)
    
      
   
    cc = g.connectedComponents() 
    
    print(len(cc)-1)

Submission status: Runtime Error

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

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

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

for i in range(n):
    if par[i] < i:
        cur_p = par[i]
        par[i] = par[cur_p]

ans = len(set(par)) - 1
print(ans)

Submission status: Runtime Error

Solution code:
from typing import List, Dict

MAX_N = 10 ** 5

visited = [False] * MAX_N
cluster = [0] * MAX_N
edges: Dict[int, List[int]] = {}


def dfs(node: int, cluster_num: int) -> None:
    cluster[node] = cluster_num
    visited[node] = True

    if node not in edges:
        return

    for v in edges[node]:
        if visited[v]:
            continue
        dfs(v, cluster_num)


def connect_cities(node_num: int, edge_num: int) -> int:
    i = 0
    for s in range(node_num):
        if visited[s]:
            continue
        dfs(s, i)
        i += 1
    return i - 1


if __name__ == "__main__":
    N, M = map(int, input().split())
    for _ in range(M):
        a, b = map(int, input().split())
        a, b = a - 1, b - 1
        edges.setdefault(a, [])
        edges[a].append(b)

        edges.setdefault(b, [])
        edges[b].append(a)

    ans = connect_cities(N, M)
    print(ans)

Submission status: Runtime Error

Solution code:
def main(dic, lst):
    seen = set()
    res = 0

    def bfs(i):
        if i in seen:
            return
        seen.add(i)
        for j in dic[i]:
            bfs(j)
    for i in lst:
        if i in seen:
            continue
        bfs(i)
        res += 1
    return res - 1


n, m = tuple(map(int, input().split()))
lst = [i for i in range(1, n + 1)]
from collections import defaultdict

dic = defaultdict(list)
for i in range(m):
    o, p = tuple(map(int, input().split()))
    dic[o].append(p)
    dic[p].append(o)
print(main(dic, lst))

Submission status: Runtime Error

Solution code:
import collections
n, m = map(int, input().split())
linked = collections.defaultdict(set)
for i in range(1, n + 1):
  linked[i].add(i)

for i in range(m):
  a, b = map(int, input().split())
  if len(linked[a]) > len(linked[b]):
     tmp = a
     a = b
     b = tmp
  linked[a].add(linked[b])
  tmp =linked[a]

  for t in linked[b]:
    linked[t] = tmp

n_connected = 0
n_group = 0
for s in linked.values():
  if s:
    n_group += 1
    n_connected += len(s)
    s.clear()
print((n - n_connected) + (n_group - 1))

Submission status: Runtime Error

Solution code:
import networkx as nx
import matplotlib.pyplot as plt
N,M = list(map(int,input().split()))
AB=[list(map(int, input().split())) for i in range(M)]

G=nx.Graph()
for i in range(1,N+1):
    G.add_node(i)
for ab in AB:
    G.add_edge(ab[0],ab[1])

count=0

nodes=list(range(1,N+1))
p_ori=nodes[0]
reachable=nx.shortest_path(G,p_ori).keys()
nodes=[a for a in nodes if a not in reachable]
while nodes!=[]:
    p=nodes[0]
    reachable=nx.shortest_path(G,p).keys()
    nodes=[a for a in nodes if a not in reachable]
    G.add_edge(p,p_ori)
    count+=1
    
print(count)
# nx.draw_networkx(G)

# plt.show()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
def dfs(f):
    if vis[f] == 1: return
    vis[f] = 1
    for t in V[f]:
        dfs(t)
          
          
n, m = map(int, input().split())
E = [[*map(lambda x: int(x)-1, input().split())] for _ in range(m)]
V = [[] for _ in range(n)]
for a, b in E: V[a].append(b); V[b].append(a)
ans = 0
vis = [0]*n

for a in range(n):
    if vis[a]==1:
      continue
    ans+=1
    dfs(a)
print(ans-1)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#include <atcoder/all>

#include <cstdio>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int n, m;
  cin >> n >> m;
  int cnt = 0;

  dsu d(n);

  rep(i, m){
    int a, b;
    cin >> a >> b;
    d.merge(a, b);
  }
  for (int i=0; i<n -1 ; i++){
      if (!(d.same(d.leader(i), d.leader(i +1)))){
        cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

Submission status: Runtime Error

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

print(N-(M+1))

Submission status: Runtime Error

Solution code:
from typing import List, Dict

MAX_N = 10 ** 5

visited = [False] * MAX_N
cluster = [0] * MAX_N
edges: Dict[int, List[int]] = {}


def dfs(node: int, cluster_num: int) -> None:
    cluster[node] = cluster_num
    visited[node] = True

    if node not in edges:
        return

    for v in edges[node]:
        if visited[v]:
            continue
        dfs(v, cluster_num)


def connect_cities(node_num: int, edge_num: int) -> int:
    i = 0
    for s in range(1, node_num + 1):
        if visited[s]:
            continue
        dfs(s, i)
        i += 1
    return i - 1


if __name__ == "__main__":
    N, M = map(int, input().split())
    for _ in range(M):
        a, b = map(int, input().split())
        edges.setdefault(a, [])
        edges[a].append(b)

        edges.setdefault(b, [])
        edges[b].append(a)

    ans = connect_cities(N, M)
    print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
class UnionFind:
    """Union-Find(素集合データ構造)"""
    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node
        
        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int):
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return
    
    def unite(self, x: int, y: int):
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def same(self, x: int, y: int):
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)
    
    def size(self, x: int) -> bool:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1


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

    lst = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        lst.unite(a, b)

    A = set()
    ans = 0
    for n in range(1, N):
        a = lst.find(n)
        if a not in A:
            A.add(lst.find(n))
            ans += 1
    print(ans - 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
c = []
cn = []
for _ in range(m):
  i,j = list(map(int,input().split()))
  if (not i in c) and (not j in c):
    c+=[i,j]
    cn.append([i,j])
  elif (not i in c):
    c.append(i)
    for a,x in enumerate(cn):
      if j in x:
        cn[a].append(i)
  elif (not j in c):
    c.append(j)
    for a,x in enumerate(cn):
      if i in x:
        cn[a].append(j)
  else:
    p = None
    idx = None
    for a,x in enumerate(cn):
      if i in x:
        if j in x:
          break
      if p == None:
        idx = a
        p = x
      else:
        cn.pop(idx)
        cn.pop(a)
        cn.append(x+p)
        break
print(n-1-len(c)+len(cn))

Submission status: Runtime Error

Solution code:
d = input().split()
N = int(d[0])
M = int(d[1])
c = []
for i in range(M):
  l = input.split()
  if l[0] not in c:
    c.append(l[0])
  if l[1] not in c:
    c.append(l[1])
print(N - len(c))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h> 
using namespace std; 
  
// Graph class represents a undirected graph 
// using adjacency list representation 
class Graph { 
    // No. of vertices 
    int V; 
  
    // Pointer to an array containing adjacency lists 
    list<int>* adj; 
  
    // A function used by DFS 
    void DFSUtil(int v, bool visited[]); 
  
public: 
    // Constructor 
    Graph(int V); 
  
    void addEdge(int v, int w); 
    int NumberOfconnectedComponents(); 
}; 
  
// Function to return the number of 
// connected components in an undirected graph 
int Graph::NumberOfconnectedComponents() 
{ 
  
    // Mark all the vertices as not visited 
    bool* visited = new bool[V]; 
  
    // To store the number of connected components 
    int count = 0; 
    for (int v = 0; v < V; v++) 
        visited[v] = false; 
  
    for (int v = 0; v < V; v++) { 
        if (visited[v] == false) { 
            DFSUtil(v, visited); 
            count += 1; 
        } 
    } 
  
    return count; 
} 
  
void Graph::DFSUtil(int v, bool visited[]) 
{ 
  
    // Mark the current node as visited 
    visited[v] = true; 
  
    // Recur for all the vertices 
    // adjacent to this vertex 
    list<int>::iterator i; 
  
    for (i = adj[v].begin(); i != adj[v].end(); ++i) 
        if (!visited[*i]) 
            DFSUtil(*i, visited); 
} 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
// Add an undirected edge 
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); 
    adj[w].push_back(v); 
} 
  
// Driver code 
int main() 
{ 	int N,M;
 	cin>>N>>M;
 	
    Graph g(N); 
 	for (int i = 0;i<M;i++)
 		{ int x,y;
         cin>>x>>y;
         g.addEdge(x,y);        
         
        }
    
    cout << g.NumberOfconnectedComponents()-1; 
  
    return 0; 
}

Submission status: Runtime Error

Solution code:
import numpy as np

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

a = [ 0 ] * m
b = [ 0 ] * m

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

#print( a, b )


xmat = np.zeros( ( n, n ), dtype=int) 
#print( xmat )


for i in range( m ):
    xmat[ a[ i ]-1 ][ b[ i ]-1 ] = 1
    xmat[ b[ i ]-1 ][ a[ i ]-1 ] = 1

#print( xmat )


cnt = 0
for i in range( 1, n ):
    #print( i )
    if xmat[ 0 ][ i ] == 0:
        cnt = cnt + 1
        xmat[ 0 ][ i ] = 1
        for j in range( i, n ):
            if xmat[ i ][ j ] == 1:
                xmat[ 0 ][ j ] = 1
        #print( "cnt = ", cnt )
        #print( xmat )

print( cnt )

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
n = list(i+1 for i in range(N))
count = 0

for _ in range(M):
    A, B = map(int, input().split())
    if A in n or B in n:
        n.remove(A)
        n.remove(B)

print(len(n))

Submission status: Runtime Error

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

# 都市分のリストを作成
res = [0] * N

# 道路の数だけ入力する
for i in range(M):
    x, y = map(int, input().split())
    res[x] += 1
    res[y] += 1
    
print(N - sum(res))