Start with components. Each successful union reduces the count by 1:
class UnionFind:
function init(n):
this.parent = array of [0, 1, ..., n-1]
this.rank = array of n zeros
this.count = n
function find(x):
if this.parent[x] != x:
this.parent[x] = this.find(this.parent[x])
return this.parent[x]
function union(x, y):
rootX = this.find(x)
rootY = this.find(y)
if rootX == rootY:
return false // already connected
if this.rank[rootX] < this.rank[rootY]:
this.parent[rootX] = rootY
else if this.rank[rootX] > this.rank[rootY]:
this.parent[rootY] = rootX
else:
this.parent[rootY] = rootX
this.rank[rootX] += 1
this.count -= 1
return true
function countComponents(n, edges):
uf = new UnionFind(n)
for each (a, b) in edges:
uf.union(a, b)
return uf.count