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: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    class UnionFind:
        def __init__(self, N: int):
            """
            N:要素数
            root:各要素の親要素の番号を格納するリスト.
                 ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
            rank:ランク
            """
            self.N = N
            self.root = [-1] * N
            self.rank = [0] * N

        def __repr__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

        def find(self, x: int):
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                while self.root[x] >= 0:
                    x = self.root[x]
                return x

        def union(self, x: int, y: int):
            """x,yが属する木をunion"""
            # 根を比較する
            # すでに同じ木に属していた場合は何もしない.
            # 違う木に属していた場合はrankを見てくっつける方を決める.
            # rankが同じ時はrankを1増やす
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return
            elif self.rank[x] > self.rank[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rank[x] == self.rank[y]:
                    self.rank[y] += 1

        def same(self, x: int, y: int):
            """xとyが同じグループに属するかどうか"""
            return self.find(x) == self.find(y)

        def count(self, x):
            """頂点xが属する木のサイズを返す"""
            return - self.root[self.find(x)]

        def members(self, x):
            """xが属する木の要素を列挙"""
            _root = self.find(x)
            return [i for i in range(self.N) if self.find == _root]

        def roots(self):
            """森の根を列挙"""
            return [i for i, x in enumerate(self.root) 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()}
        
    N,M=MI()
    uf=UnionFind(N)
    for _ in range(M):
        a,b=MI()
        a-=1
        b-=1
        uf.union(a,b)
        
    cnt=uf.group_count()
    print(cnt-1)

main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
par = [0]+[-1 for i in range(N)]

def find(x):
    if par[x] == -1:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]

def same(x,y):
    return find(x) == find(y)
  
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    
for i in range(M):
    a,b = map(int,input().split())
    unite(a,b)
print(len([i for i in par if i == -1])-1)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)

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

UF = UnionFind(N)

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

UF.updatePars()

cnt = Counter(UF.pars)

ans = len(cnt.keys()) - 1
print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,m=map(int,input().split())
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,x):
        if self.par[x] <0: #負なら親、要素数
            return x
        else: #正なら親の番号
            self.par[x]=self.find(self.par[x]) #一回調べたら根を繋ぎ変える、経路圧縮
            return self.par[x]
    def union(self,x,y):
        x=self.find(x) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(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.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)

tree=UnionFind(n)
for i in range(m):
    a,b=map(int,input().split())
    tree.union(a-1,b-1)
print(tree.group_count()-1)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
l = [[] for _ in range(N+1)]
 
for _ in range(M):
  a,b = map(int,input().split())
  l[a].append(b)
  l[b].append(a)

check = [0]*(N+1)
cnt = 0
for i in range(1,N+1):
  if check[i] == 1:
    continue
  st = deque([i])
  check[i] = 1
  while st:
    s = st.popleft()
    for t in l[s]:
      if check[t] == 0:
        check[t] = 1
        st.append(t)
      continue
  cnt += 1

print(cnt-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

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

class UnionFind():
    def __init__(self, n): 
        self.n = n 
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def root(self, x): 
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 圧縮経路
            return self.par[x]
            # return root(par[x]) # 圧縮しない場合

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

    def unite(self, x, y): 
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: 
            return

        # par[rx] = ry # naiveな連結

        # 低い木を高い方にくっつける。
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.sizes[ry] += self.sizes[rx]
        else:
            self.par[ry] = rx
            self.sizes[rx] += self.sizes[ry]

        # rx木とry木の高さが同じならば、rx木を深くする。
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def size(self, x): 
        '''
        xが属するグループのサイズを返す
        (連結成分の大きさ)
        '''
        return self.sizes[self.root(x)]

    def roots(self):
        '''
        全ての頂点の根のlistを返す   
        '''
        return [self.root(i) for i in range(self.n)]

    def connected(self):
        ''' 
        連結成分の数を返す
        '''
        #return len(set(self.par))
        return len(set(self.roots()))

uf = UnionFind(n)
for i in range(m):
    uf.unite(a[i], b[i])

ans = uf.connected()-1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

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

class UnionFind():
    def __init__(self, n): 
        self.n = n 
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.sizes = [1 for _ in range(n)]

    def root(self, x): 
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 圧縮経路
            return self.par[x]
            # return root(par[x]) # 圧縮しない場合

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

    def unite(self, x, y): 
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: 
            return

        # par[rx] = ry # naiveな連結

        # 低い木を高い方にくっつける。
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.sizes[ry] += self.sizes[rx]
        else:
            self.par[ry] = rx
            self.sizes[rx] += self.sizes[ry]

        # rx木とry木の高さが同じならば、rx木を深くする。
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1

    def size(self, x): 
        '''
        xが属するグループのサイズを返す
        (連結成分の大きさ)
        '''
        return self.sizes[self.root(x)]

    def connected(self):
        '''
        連結成分の数
        '''
        return len(set(self.par))

uf = UnionFind(n)
for i in range(m):
    uf.unite(a[i], b[i])
for i in range(n):
    _ = uf.root(i)

ans = uf.connected()-1
print(ans)

Submission status: Accepted

Solution code:
# queueのライブラリをインポート
import queue
 
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)
ans = 0
# まだ訪れていない都市を記録
city = set(i for i in range(n))
# まだ訪れていない都市がある間繰り返す
while len(city):
  # queueを用意する
  q = queue.Queue()
  # 初期値としてまだ訪れていない都市を入れる
  q.put(city.pop())
  # 1つのグループを全て辿る
  while not q.empty():
    x = q.get()
    for i in road[x]:
      # 既に訪れたか調べる
      if i in city:
        # 訪れていなければqueueに追加する
        q.put(i)
        # 未訪問の都市のリストから除外する
        city.discard(i)
  # まだ訪れていない都市があれば答えを増やす
  if len(city):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import deque
pl=1
#from math import *
from copy import *
#sys.setrecursionlimit(10**6)
if pl:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('outpt.txt','w')

def li():
	return [int(xxx) for xxx in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	

def find(i):
	if i==a[i]:
		return i
	a[i]=find(a[i])
	return a[i]
def union(x,y):
	xs=find(x)
	ys=find(y)
	if xs!=ys:
		if rank[xs]<rank[ys]:
			xs,ys=ys,xs
		rank[xs]+=1
		a[ys]=xs		
t=1
while t>0:
	t-=1
	n,m=mi()
	a=[i for i in range(n+1)]	
	rank=[0 for i in range(n+1)]			
	for i in range(m):
		x,y=mi()
		union(x,y) 
	s=set()	
	for i in range(1,n+1):
		a[i]=find(i)
		s.add(a[i])
	print(len(s)-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.nodes = n
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n

    def find(self, i): # どの集合に属しているか（根ノードの番号）
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i]) # 経路圧縮
            return self.parents[i]

    def unite(self, i, j): # 二つの集合を併合
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj
            else:
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
    def same(self, i, j): # 同じ集合に属するかを判定
        return self.find(i)==self.find(j)

    def get_parents(self): # 根ノードの一覧を取得
        for n in range(self.nodes): # findで経路圧縮する
            self.find(n)
        return self.parents

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

uf = UnionFind(N)
for i in range(M): # 取り除く辺番号
    uf.unite(*adj[i])
    
ans=len(set(uf.get_parents())) # 複数の集合にわかれているか確認
    
print (ans-1)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.rank = [0] * (n+1)
    
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if self.rank[x] < self.rank[y]:
      self.par[x] = y
    else:
      self.par[y] = x
      
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1

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

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

for i in range(M):
  A,B=map(int,input().split())
  city.unite(A,B)

ck=[0]*(N+10)
for i in range(1,N+1):
  root=city.find(i)
  if ck[root]==0:
    ck[root]=1
    
#print(city.par)
#print(ck)
    
Ans=sum(ck)-1
print(Ans)

Submission status: Accepted

Solution code:
"""
Union Find 木クラス
参考URL：https://note.nkmk.me/python-union-find/

parents
各要素の親要素の番号を格納するリスト
要素が根（ルート）の場合は-(そのグループの要素数)を格納する
例：
    parents[2] = 0 → 要素2の親は0
    parents[0] = -3 → 要素0は根であり、そのグループの要素数は3個
"""
class UnionFind():
    # 初期化（初期状態は全要素が根）
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # xの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            # 経路圧縮も同時に行う
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        # 根が同じならx,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

    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    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()}

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

n, m = map(int, input().split())
u = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    u.union(a-1, b-1)

print(u.group_count() - 1)

Submission status: Accepted

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

U = UnionFind(N)

for i in range(M):
    A,B = map(int,input().split())
    A -= 1
    B -= 1
    U.union(A,B)

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

Submission status: Accepted

Solution code:
# Connect Cities
# Union Findデータ構造（素集合データ構造）

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n

	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)

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

#		self.parents[x]+=self.parents[y]
		self.parents[y]=x
		# print(self.parents)
n,m=input2()
AB=[input_array() for _ in range(m)]


uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1
print(ans-1)

Submission status: Accepted

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(lambda x:int(x)-1,input().split())
    uf.union(a , b)
    
print(uf.group_count()-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
nextcity = [[] for _ in range(N)]
sgn = [0 for _ in range(N)]
while M:
	M -= 1
	A, B = map(int, input().split())
	A -= 1
	B -= 1
	nextcity[A].append(B)
	nextcity[B].append(A)

def bfs(cnt, lis):
	nextvisit = []
	for j in lis:
		for item in nextcity[j]:
			if sgn[item] == 0:
				nextvisit.append(item)
				sgn[item] = cnt
	if nextvisit:
		bfs(cnt, nextvisit)
		return None
	else:
		return None
cnt = 0
for k in range(N):
	if sgn[k] == 0:
		cnt += 1
		sgn[k] = cnt
		bfs(cnt, [k])
print(cnt -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
nextcity = [[] for _ in range(N)]
sgn = [0 for _ in range(N)]
while M:
	M -= 1
	A, B = map(int, input().split())
	A -= 1
	B -= 1
	nextcity[A].append(B)
	nextcity[B].append(A)

def dfs(cnt, city):
	for item in nextcity[city]:
		if sgn[item] == 0:
			sgn[item] = cnt
			dfs(cnt, item)
	return None

cnt = 0
for k in range(N):
	if sgn[k] == 0:
		cnt += 1
		sgn[k] = cnt
		dfs(cnt, k)
print(cnt -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
nextcity = [[] for _ in range(N)]
sgn = [0 for _ in range(N)]
while M:
	M -= 1
	A, B = map(int, input().split())
	A -= 1
	B -= 1
	nextcity[A].append(B)
	nextcity[B].append(A)

def bfs(cnt, lis):
	nextvisit = []
	for j in lis:
		for item in nextcity[j]:
			if sgn[item] == 0:
				nextvisit.append(item)
				sgn[item] = cnt
	if nextvisit:
		bfs(cnt, nextvisit)
		return None
	else:
		return None
cnt = 0
for k in range(N):
	if sgn[k] == 0:
		cnt += 1
		sgn[k] = cnt
		bfs(cnt, [k])
print(cnt -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
nextcity = [[] for _ in range(N)]
sgn = [0 for _ in range(N)]
while M:
	M -= 1
	A, B = map(int, input().split())
	A -= 1
	B -= 1
	nextcity[A].append(B)
	nextcity[B].append(A)

def dfs(cnt, city):
	for item in nextcity[city]:
		if sgn[item] == 0:
			sgn[item] = cnt
			dfs(cnt, item)
	return None

cnt = 0
for k in range(N):
	if sgn[k] == 0:
		cnt += 1
		sgn[k] = cnt
		dfs(cnt, k)
print(cnt -1)

Submission status: Accepted

Solution code:
import collections
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    road[A].append(B)
    road[B].append(A)

no_visit =set(range(1,N+1))
q = collections.deque([])
cnt = 0
while no_visit:
    q.append(no_visit.pop())
    cnt +=1
    while q:
        now = q.popleft()
        for nxt in road[now]:
            if nxt in no_visit:
                q.append(nxt)
                no_visit.discard(nxt)
print(cnt-1)