Building Roads - Implementation

Here is the implementation using Union-Find:

parent = array [1, 2, 3, ..., n]
components = n

for (a, b) in edges:
    if find(a) != find(b):
        union(a, b)
        components = components - 1

print components - 1

representatives = empty list
for i from 1 to n:
    if find(i) == i:
        representatives.append(i)

for i from 0 to representatives.size - 2:
    print representatives[i], representatives[i + 1]

Connect component representatives sequentially.