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:
from scipy.sparse.csgraph import connected_components
import numpy as np


n,m = map(int,input().split())
g = np.zeros((n,n),dtype=np.int)
for i in range(m):
    ai,bi = map(int,input().split())
    g[ai-1][bi-1] = 1
    g[bi-1][ai-1] = 1
r = connected_components(g,return_labels=False)
print(r-1)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    e[A].append(B)
    e[B].append(A)
# print(e)

def dfs(n, k):
    seen[n] = k
    # print(seen)
    for i in e[n]:
        if seen[i] != -1: continue
        dfs(i, k)

seen = [-1] * N
k = -1
for i in range(N):
    if seen[i] == -1:
        k += 1
        dfs(i, k)
# print(seen)
print(k)

Submission status: Runtime Error

Solution code:
import collections

def dfs(visited,v,adj):
    visited[v]=True 
    for i in adj[v]:
        if not visited[i]:
            dfs(visited,i,adj)  
adj=collections.defaultdict(list)
n,m=map(int,input().split()) 
visited=[False]*n  
for i in range(m):
    u,v=map(int,input().split()) 
    adj[u-1].append(v-1)  
    adj[v-1].append(u-1) 
c=0 
for i in range(n):
    if not visited[i]:
        dfs(visited,i,adj) 
        c+=1 
print(c-1)

Submission status: Runtime Error

Solution code:
class UnionFind():
    """
        unionfindtree のクラス
            グループを管理するデータ構造.
            全てのメソッドの計算量が O(log(n)) よりも小さい
        init: 管理対象の個数 n を用いて初期化
        find: ある要素 x の親がどの要素か返す
        union: ある要素 x と y が属しているグループを結合して1つのグループとする
        msize: ある要素 x が属するグループの大きさを返す
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n
        self.rank = [0]*n
        self.size = [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 と y のランク(子の数)の小さい方が結合先の親となる
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def msize(self, x):
        """
            ある要素 x の属するグループの大きさを返すメソッド
        """
        return self.size[self.find(x)]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())


def main():
    N, Q = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(Q):
        u, v = map(int, input().split())
        uf.union(u, v)
    print(uf.group_count()-1)   
if __name__ == "__main__":
    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())
union = UnionFind(N)
for i in range(M):
    A,B = map(int,input().split())
    union.union(A,B)
print(union.group_count()-1)

Submission status: Runtime Error

Solution code:
# H4CKOM
N = 100100
g = [[] for i in range(N)]
vis = [False for i in range(N)]
vis2 = [False for i in range(N)]


def add_edge(u, v):
    g[u].append(v)


def dfs1(v):
    vis2[v] = True
    for to in g[v]:
        if not vis2[to]:
            dfs1(to)


def dfs2(v):
    global ans
    vis[v] = True
    ans += 1
    for to in g[v]:
        if not vis[to] and not vis2[to]:
            dfs2(to)


def get():
    global vis, ans
    dfs1(x)
    val = []
    for i in range(0, n):
        if not vis2[i]:
            ans = 0
            vis = [False for i in range(N)]
            dfs2(i)
            val.append((ans, i))
    val.sort(reverse=True)
    ans = 0
    for it in val:
        if not vis2[it[1]]:
            ans += 1
            dfs1(it[1])
    return ans


if __name__ == "__main__":

    n, x = map(int, input().split())
    for i in range(x):
        u, v = map(int, input().split())
        add_edge(u-1, v-1)
        add_edge(v-1, u-1)

    print(get())

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.d = []
        for _ in range(n):
            self.d.append(-1)
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.d[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x

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

    def size(self, x):
        return -self.d[self.find(x)]


N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    uf.union(a,b)
group = set()
for i in range(N):
    group.add(uf.find(i))

print(len(group)-1)

Submission status: Runtime Error

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
# 1 2 3
# a, b, c = LI()


def I(): return int(sys.stdin.buffer.readline())
# a = I()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
# abc def
# a, b = LS()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
# a = S()


def IR(n): return [I() for i in range(n)]
# 2
# 1
# 2
# [1, 2]


def LIR(n): return [LI() for i in range(n)]
# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def SR(n): return [S() for i in range(n)]
# 2
# abc
# def
# [abc, def]


def LSR(n): return [LS() for i in range(n)]
# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def SRL(n): return [list(S()) for i in range(n)]
# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


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 = LI()
uf = UnionFind(n)
for _ in range(m):
    a, b = LI()
    uf.union(a, b)
print(uf.group_count()-1)

Submission status: Runtime Error

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_dsu_code = """
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

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

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))
"""

atcoder.dsu = types.ModuleType('atcoder.dsu')
exec(_atcoder_dsu_code, atcoder.dsu.__dict__)
DSU = atcoder.dsu.DSU

# from atcoder.dsu import DSU

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

for _ in range(M):
    A, B = map(int, input().split())
    d.merge(A, B)

print(len(d.groups()) - 1)

Submission status: Runtime Error

Solution code:
# H4CKOM
N = 10010
g = [[] for i in range(N)]
vis = [False for i in range(N)]
vis2 = [False for i in range(N)]


def add_edge(u, v):
    g[u].append(v)


def dfs1(v):
    vis2[v] = True
    for to in g[v]:
        if not vis2[to]:
            dfs1(to)


def dfs2(v):
    global ans
    vis[v] = True
    ans += 1
    for to in g[v]:
        if not vis[to] and not vis2[to]:
            dfs2(to)


def get():
    global vis, ans
    dfs1(x)
    val = []
    for i in range(0, n):
        if not vis2[i]:
            ans = 0
            vis = [False for i in range(N)]
            dfs2(i)
            val.append((ans, i))
    val.sort(reverse=True)
    ans = 0
    for it in val:
        if not vis2[it[1]]:
            ans += 1
            dfs1(it[1])
    return ans


if __name__ == "__main__":

    n, x = map(int, input().split())
    for i in range(x):
        u, v = map(int, input().split())
        add_edge(u-1, v-1)
        add_edge(v-1, u-1)

    print(get())

Submission status: Runtime Error

Solution code:
a,b,c,d=map(int,input().split())
if d<a or c>b:
    print("No")
else:
    print("Yes")

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline

class Graph: 
	def __init__(self,V): 
		self.V = V 
		self.adj = [[] for i in range(V)] 
	def DFSUtil(self, temp, v, visited): 
		visited[v] = True
		temp.append(v) 
		for i in self.adj[v]: 
			if visited[i] == False: 
				temp = self.DFSUtil(temp, i, visited) 
		return temp 
	def addEdge(self, v, w): 
		self.adj[v].append(w) 
		self.adj[w].append(v) 
	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 

n, m = map(int, input().split())
g = Graph(n)
for i in range(m):
	x, y = map(int, input().split())
	g.addEdge(x-1, y-1)
print(len(g.connectedComponents())-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
class Tree:
    def __init__(self, N):
        self.N = N
        self.nodes = [ Node(i) for i in range(N) ]

    def get_root(self, node):
        if node.parent is None:
            return node
        root = self.get_root(node.parent)
        node.parent = root
        return root

    def merge(self, n1, n2):
        node1 = self.nodes[n1]
        node2 = self.nodes[n2]

        root1 = self.get_root(node1)
        root2 = self.get_root(node2)

        if root1.ID == root2.ID:
            return

        root1.parent = root2

    def get_root_count(self):
        count = 0
        for n in self.nodes:
            if n.parent is None:
                count += 1
        return count

class Node:
    def __init__(self, ID):
        self.ID = ID
        self.parent = None

def main():
    N, M = map(int, input().split())
    tree = Tree(N)
    for i in range(M):
        A, B = map(int, input().split())
        tree.merge(A, B)
    print(tree.get_root_count() - 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:
N, M = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    e[A].append(B)
    e[B].append(A)
# print(e)

def dfs(n, k):
    seen[n] = k
    # print(seen)
    for i in e[n]:
        if seen[i] != -1: continue
        dfs(i, k)
    return

seen = [-1] * N
k = -1
for i in range(N):
    if seen[i] == -1:
        k += 1
        dfs(i, k)
# print(seen)
print(k)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)
import itertools
import collections
B=list(itertools.chain.from_iterable(A))
C=len(collections.Counter(B))
print(N-C)

Submission status: Runtime Error

Solution code:
n,m = list(map(int,input().split()))
res = [[x] for x in range(1,n+1)]
for _ in range(m):
  i,j = list(map(int,input().split()))
  y,z = None,None
  for x in res:
    if i in x or j in x:
      if y == None:
        y = x
        if j in x:
          break
      else:
        z = x
        res.remove(y)
        res.remove(z)
        res.append(y+z)
print(len(res)-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline

class Graph: 
	def __init__(self,V): 
		self.V = V 
		self.adj = [[] for i in range(V)] 
	def DFSUtil(self, temp, v, visited): 
		visited[v] = True
		temp.append(v) 
		for i in self.adj[v]: 
			if visited[i] == False: 
				temp = self.DFSUtil(temp, i, visited) 
		return temp 
	def addEdge(self, v, w): 
		self.adj[v].append(w) 
		self.adj[w].append(v) 
	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 

n, m = map(int, input().split())
g = Graph(n)
for i in range(m):
	x, y = map(int, input().split())
	g.addEdge(x-1, y-1)
print(len(g.connectedComponents())-1)
print(g.connectedComponents())

Submission status: Runtime Error

Solution code:
# Python3 program to count non-reachable
# nodes from a given source using DFS.

# Graph class represents a directed graph
# using adjacency list representation


class Graph:
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]

    def addEdge(self, v, w):
        self.adj[v].append(w)  # Add w to v’s list.
        self.adj[w].append(v)  # Add v to w's list.

    def DFSUtil(self, v, visited):

        # Mark the current node as
        # visited and print it
        visited[v] = True

        # Recur for all the vertices
        # adjacent to this vertex
        i = self.adj[v][0]
        for i in self.adj[v]:
            if (not visited[i]):
                self.DFSUtil(i, visited)

    # Returns count of not reachable
    # nodes from vertex v.
    # It uses recursive DFSUtil()
    def countNotReach(self, v):

        # Mark all the vertices as not visited
        visited = [False] * self.V

        # Call the recursive helper
        # function to prDFS traversal
        self.DFSUtil(v, visited)

        # Return count of not visited nodes
        count = 0
        for i in range(self.V):
            if (visited[i] == False):
                count += 1
        return count


# Driver Code
if __name__ == '__main__':

    # Create a graph given in the
    # above diagram
    n, m = map(int, input().split())
    g = Graph(n)
    for _ in range(m):
        a, b = map(int, input().split())

        g.addEdge(a, b)
        # g.addEdge(0, 2)
        # g.addEdge(1, 2)
        # g.addEdge(3, 4)
        # g.addEdge(4, 5)
        # g.addEdge(6, 7)

        print(g.countNotReach(2))

# This code is contributed by PranchalK

Submission status: Runtime Error

Solution code:
l = input().split()
N = int(l[0])
M = int(l[1])
arr = [0]*N
retval = 0
for i in range(M):
  l = input().split()
  #A[i] = l[0]
  #B[i] = l[1]
  arr[int(l[0])] = 1
  arr[int(l[1])] = 1

for i in range(N):
  retval += arr[i]

print(N-retval)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-09-26 20:52:24 +0900
# LastModified: 2020-09-26 21:18:10 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def BFS(cnt, color, path, u):
    color[u] = cnt
    for v in path[u]:
        if color[v] == -1:
            BFS(cnt, color, path, v)


def main():
    N, M = map(int, input().split())
    path = [[] for _ in range(N+1)]
    for _ in range(M):
        A, B = map(int, input().split())
        path[A].append(B)
        path[B].append(A)
    color = [-1] * (N+1)
    cnt = 0
    for i in range(1, N+1):
        if color[i] == -1:
            BFS(cnt, color, path, i)
            cnt += 1
    print(max(color))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

c = a + b
c = set(c)

print(m-len(c)+1)

Submission status: Runtime Error

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

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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)
    if x != y:
        par[x] = y

for _ in range(m):
    a, b = map(int, input().split())
    unite(a-1, b-1)

groups= 0
for i in range(n):
    if i == par[i]:
        groups +=1
print(groups-1)

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

def resolve():
    import sys

    input = sys.stdin.readline

    n, m = [int(x) for x in input().rstrip().split(" ")]

    uf = UnionFind(n)

    for i in range(m):
        a, b = [int(x) for x in input().rstrip().split(" ")]
        uf.union(a, b)

    print(len(uf.roots()) - 1)



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
edges = [[] for i in range(n)]
visit = [False for i in range(n)]
def dfs(v):
    visit[v] = True
    for i in edges[v]:
        if not visit[i]:
            dfs(i)
for i in range(m):
    a, b = map(int, input().split())
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)
cnt = 0
for i in range(n):
    if not visit[i]:
        dfs(i)
        cnt += 1
print(cnt - 1)

Submission status: Runtime Error

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

c = a + b
c = set(c)

print(m-len(c)+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 26 17:37:27 2020

@author: divyarth
"""

import sys
import heapq
import math

sys.setrecursionlimit(10000)
#input=sys.stdin.readline
#print=sys.stdout.write

from collections import deque
from collections import defaultdict
from collections import Counter

modH=int(10**9)+7

I=lambda : list(map(int,input().split(' ')))
def PRINT(lst,sep=' '): print(sep.join(map(str,lst)))

n,m=I()
edges=[I() for i in range(m)]
graph=[[] for i in range(n)]

for src,des in edges:
    graph[src-1].append(des-1)
    graph[des-1].append(src-1)

def dfs(node):
    visited[node]=1
    for w in graph[node]:
        if visited[w]==None:
            dfs(w)

visited=[None]*n
cmp=0
for i in range(n):
    if visited[i]==None:
        dfs(i)
        cmp+=1

print(cmp-1)

Submission status: Runtime Error

Solution code:
class path_compressed_quick_union:
    def __init__(self, n):
        self.n = n
        self.data = [i for i in range(n)]
        self.size = [1 for i in range(n)]

    def root(self, p):
        while p != self.data[p]:
            self.data[p] = self.data[self.data[p]]
            p = self.data[p]
        return p

    def connected(self, p, q):
        return self.root(p) == self.root(q)

    def union(self, p, q):
        proot = self.root(p)
        qroot = self.root(q)
        if self.size[proot] < self.size[qroot]:
            self.data[qroot] = proot
            self.size[qroot] += self.size[proot]
        else:
            self.data[proot] = qroot
            self.size[proot] += self.size[qroot]



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

print(len(set(uf.data))-1)

Submission status: Runtime Error

Solution code:
# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd, log10
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement, chain
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
from copy import copy, deepcopy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
# 1 2 3
# a, b, c = LI()


def I(): return int(sys.stdin.buffer.readline())
# a = I()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
# abc def
# a, b = LS()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
# a = S()


def IR(n): return [I() for i in range(n)]
# 2
# 1
# 2
# [1, 2]


def LIR(n): return [LI() for i in range(n)]
# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def SR(n): return [S() for i in range(n)]
# 2
# abc
# def
# [abc, def]


def LSR(n): return [LS() for i in range(n)]
# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def SRL(n): return [list(S()) for i in range(n)]
# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


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 = LI()
city = [[] for _ in range(n)]
uf = UnionFind(n)
for i in range(m):
    a, b = LI()
    uf.union(a, b)
print(uf.group_count()-1)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
from sys import stdin


def makeConnected(n, connections):
    l = list(zip(*connections))
    d = [1] * len(connections)
    a = csr_matrix((d, (l[0], l[1])), (n, n))
    return connected_components(a, return_labels=0)


def main():
    input = lambda: stdin.readline()[:-1]
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]

    ans = makeConnected(N, AB) - 1
    print(ans)


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())
        
a = input().split()
N = int(a[0])
M = int(a[1])
tm = int(0)
tmp = int(0)


k = [input().split() for i in range(M)]

uf = UnionFind(N)

for i in range(M):
    tm = int(k[i][0])
    tmp = int(k[i][1])
    uf.union(tm, tmp)
    tm = 0
    tmp = 0

print(int(uf.group_count()) - 1)