Implementation - Road Construction

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: $O(m \cdot \alpha(n))$ where $m$ is the number of edges. Space: $O(n)$.