#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/minimum-spanning-trees/building-roads-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/minimum-spanning-trees/building-roads-implementation

Repovive

Building Roads - Implementation - Minimum Spanning Trees | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Building Roads - Implementation

(DSU and component list)

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.