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

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq


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) 
        y=self.find(y)

        if x==y: 
            return 
        if self.par[x]>self.par[y]: 
            x,y=y,x
        self.par[x]+=self.par[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)

Solution (Python):
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)

Solution (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]
            

    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

        

        
        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]

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

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

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

Solution (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]
            

    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

        

        
        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]

        
        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)

Solution (Python):

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):
  
  q = queue.Queue()
  
  q.put(city.pop())
  
  while not q.empty():
    x = q.get()
    for i in road[x]:
      
      if i in city:
        
        q.put(i)
        
        city.discard(i)
  
  if len(city):
    ans += 1
print(ans)

Solution (Python):
import sys
from bisect import *
from collections import deque
pl=1

from copy import *

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)

Solution (Python):
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)

Solution (Python):
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): 
            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)

Solution (Python):
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
    


    
Ans=sum(ck)-1
print(Ans)

Solution (Python):
"""
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

    
    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())
    u.union(a-1, b-1)

print(u.group_count() - 1)

Solution (Python):
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)

Solution (Python):




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


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[y]=x
		
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):



"""






















using namespace std;

using int64 = long long;




class UnionFind {
 public:
  UnionFind(int n) : n_(n) { init(); }

  int root(int x) {
    assert(0 <= x && x < n_);
    if (par_[x] == -1)
      return x;
    else
      return par_[x] = root(par_[x]);
  }

  bool same(int x, int y) {
    assert(0 <= x && x < n_ && 0 <= y && y < n_);
    return root(x) == root(y);
  }

  void unite(int x, int y) {
    assert(0 <= x && x < n_ && 0 <= y && y < n_);
    x = root(x);
    y = root(y);
    if (x == y) return;
    if (rank_[x] < rank_[y]) std::swap(x, y);
    if (rank_[x] == rank_[y]) ++rank_[x];
    par_[y] = x;
    return;
  }

 private:
  const int n_;
  std::vector<int> par_;
  std::vector<int> rank_;

  void init() {
    par_.assign(n_, -1);
    rank_.assign(n_, 0);
  }
};


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  UnionFind uf(n);
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b;
    --a;
    --b;
    uf.unite(a, b);
  } 

  set<int> st;
  for (int i = 0; i < n; ++i) {
    st.emplace(uf.root(i));
  }

  cout << (int)st.size() - 1 << endl;

  return 0;
}

"""

import base64
import subprocess
import zlib


exe_bin = "c%0>1eRxw<n!oud4YVXd3l;^5ZeR;YY@lERGB

open("./kyomu", 'wb').write(zlib.decompress(base64.b85decode(exe_bin)))
subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.co = n

  def find(self, x):
    if self.n[x] < 0:
      return x
    else:
      self.n[x] = self.find(self.n[x])
      return self.n[x]

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.r[x] > self.r[y]:
      x, y = y, x
    self.n[y] += self.n[x]
    self.n[x] = y
    if self.r[x] == self.r[y]:
      self.r[y] += 1
    self.co -= 1

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

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

  def set_count(self):
    return self.co

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

Solution (Python):
class UnionFind:
    from typing import List, Set

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def merge(self, x, y) -> int:
        x = self.leader(x)
        y = self.leader(y)

        if x == y:
            return 0

        if self.parent[x] > self.parent[y]:
            x, y = y, x

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

        return self.parent[x]

    def same(self, x, y) -> bool:
        return self.leader(x) == self.leader(y)

    def leader(self, x) -> int:
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.leader(self.parent[x])
            return self.parent[x]

    def size(self, x) -> int:
        return -self.parent[self.leader(x)]

    def groups(self) -> List[Set[int]]:
        groups = dict()

        for i in range(self.n):
            p = self.leader(i)
            if not groups.get(p):
                groups[p] = set()
            groups[p].add(i)

        return list(groups.values())

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

    uf = UnionFind(N)

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

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


if __name__ == '__main__':
    main()

Solution (Python):





def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

def str_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(input()))
    return np.array(x)

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

def int_list():
    return list(map(int,input().split()))

def print_space(l):
    return print(" ".join([str(x) for x in l]))


import numpy as np
import collections as col
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix


N,M =int_map()
AB = int_mtx(M)

n, _ = connected_components(csr_matrix(([1]*M, (AB[:,0]-1, AB[:,1]-1)),(N,N)))

print(n-1)

Solution (Python):
N,M = map(int,input().split())
L = [list(map(int,input().split())) for _ in range(M)]

par = [0]*(N+1)

for i in range (N+1): 
    par[i] = i


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


def find(x,y):
    return root(x)==root(y)


def union(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    par[x] = y

for l in L:
    union(l[0],l[1])

R = [0]
R[0] = root(par[1])
for i in range(2,N+1):
    if R[0] != root(par[i]):
        R.append(root(par[i]))

print(len(set(R))-1)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(self.n))
        self.rank = [1] * n
        self.cnt = n
    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):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.rank[p] += self.rank[q]
        self.par[q] = p
        self.cnt -= 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return self.rank[x]
    def count(self):
        return self.cnt
n, m = map(int, input().split())
UF = UnionFind(n)
for _ in range(m):
    a, b = map(int, input().split())
    UF.unite(a - 1, b - 1)
print(UF.count() - 1)

Solution (Python):
N,M=map(int,input().split())
city=[0]*(N+10)


for i in range(1,N+1):
  city[i]=i
  

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



  if city[A]!=A:
    root=city[A]
    while city[root]!=root:
      root=city[root]
    city[A]=root
  
  if city[B]!=B:
    root=city[B]
    while city[root]!=root:
      root=city[root]
    city[B]=root


  if city[A]!=city[B]:
    city[city[B]]=city[A]
    

  

ck=[0]*(N+10)
for i in range(1,N+1):
  if city[i]!=i:
    root=city[i]
    while city[root]!=root:
      root=city[root]
    city[i]=root
    
  if ck[city[i]]==0:
    ck[city[i]]=1
    


Ans=sum(ck)-1 

print(Ans)

Solution (Python):
from collections import deque

n, m = map(int, input().split())
nodes = range(1,n+1)
edges = {v: set() for v in nodes}
for _ in range(m):
  a, b = map(int, input().split())
  edges[a].add(b)
  edges[b].add(a)

visited = {v: False for v in nodes}
cnt = -1
for v in nodes:
  if not visited[v]:
    visited[v] = True
    que = deque([v])
    while que:
      p = que.popleft()
      for q in edges[p]:
        if not visited[q]:
          visited[q] = True
          que.append(q)
    cnt += 1
print(cnt)

Solution (Python):
def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

import sys
input = sys.stdin.readline

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

par = [-1]* n
rank = [0]*n

for i in range(m):
    a,b = map(int, input().split())
    a, b =a-1, b-1
    Unite(a,b,par,rank)

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

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.co = n

  def find(self, x):
    if self.n[x] < 0:
      return x
    else:
      self.n[x] = self.find(self.n[x])
      return self.n[x]

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.co -= 1

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

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

  def set_count(self):
    return self.co

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

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.co = n

  def find_root(self, x):
    if self.n[x] < 0:
      return x
    else:
      self.n[x] = self.find_root(self.n[x])
      return self.n[x]

  def unite(self, x, y):
    x = self.find_root(x)
    y = self.find_root(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.co -= 1

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

  def size(self, x):
    return -self.n[self.find_root(x)]

  def set_count(self):
    return self.co

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

Solution (Python):
class UnionFind:
  def __init__(self, n):
    self.n = [-1]*n
    self.r = [0]*n
    self.co = n

  def find_root(self, x):
    if self.n[x] < 0:
      return x
    else:
      self.n[x] = self.find_root(self.n[x])
      return self.n[x]

  def unite(self, x, y):
    x = self.find_root(x)
    y = self.find_root(y)
    if x == y:
      return
    elif self.r[x] > self.r[y]:
      self.n[x] += self.n[y]
      self.n[y] = x
    else:
      self.n[y] += self.n[x]
      self.n[x] = y
      if self.r[x] == self.r[y]:
        self.r[y] += 1
    self.co -= 1

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

  def size(self, x):
    return -self.n[self.find_root(x)]

  def set_count(self):
    return self.co

import sys
input = lambda:sys.stdin.readline().rstrip()

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

Solution (Python):
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-1, b-1)
print(len(uf.roots())-1)

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush


sys.setrecursionlimit(10 ** 7)





from collections import deque



INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def dfs(c, to, seen, g = None):
    if g == None:g = set()
    g.add(c)
    seen.add(c)
    for n in to[c]:
        if not n in seen:
            dfs(n, to, seen, g)
    return g, seen


def run():
    N, M = mapline()
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = mapline()
        to[a].append(b)
        to[b].append(a)

    seen = set()
    G = []
    for i in range(1, N+1):
        if not i in seen:
            g, seen = dfs(i, to, seen)
            
            G.append(g)
    
    print(len(G) -1)



if __name__ == "__main__":
    run()

Solution (Python):

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


par=[0]

rank=[0]


for i in range(1,N+1):
    par.append(i)
    rank.append(0)


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


def unite(x,y):
    
    root_x=find(x)
    root_y=find(y)

    
    if root_x == root_y:
        return

    
    if rank[root_x] < rank[root_y]:
        par[root_x] = root_y

    else:
        par[root_y] = root_x

    
    if rank[root_x]==rank[root_y]:
        rank[root_x]+=1


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


for i in range(Q):
    a,b=map(int,input().split())
    unite(a, b)
res = []
for i in range(1, N+1):
    res.append(find(i))
ans = len(set(res))-1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)

n,m=map(int,input().split())
g=[[] for i in range(10**5+10)]
for i in range(m):
  a,b=map(lambda x:int(x)-1, input().split())
  g[a].append(b)
  g[b].append(a)
chk=[-1]*n

def dfs(s,cnt):
  for u in g[s]:
    if chk[u]>-1: continue;
    chk[u]=cnt
    dfs(u,cnt)

cnt=0
for i in range(n):
  if chk[i]==-1:
    chk[i]=cnt
    dfs(i,cnt)
    cnt+=1
    
print(max(chk))