Here is the Union-Find implementation:
function roadConstruction(n, edges):
parent = array [0, 1, 2, ..., n]
size = array of n + 1, all 1
componentCount = n
maxSize = 1
for (u, v) in edges:
pu = find(u)
pv = find(v)
if pu == pv:
print componentCount, maxSize
continue
// Union by size
if size[pu] < size[pv]:
swap(pu, pv)
parent[pv] = pu
size[pu] = size[pu] + size[pv]
componentCount = componentCount - 1
maxSize = max(maxSize, size[pu])
print componentCount, maxSize
Time: . Space: .