C - Connect Cities.py

import sys
sys.setrecursionlimit(100000)

n,m = input().split()
n = int(n)
m = int(m)

g = [[] for _ in range(n)]

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

vis = [False] * n

def dfs(u):
  if vis[u]:
    return
  vis[u] = True
  for v in g[u]:
    dfs(v)

numComp = 0

for i in range(n):
  if not vis[i]:
    numComp += 1
    dfs(i)

print(numComp - 1)