A Minimum Spanning Tree (MST) connects every node in a network at the least total cost. Both classic MST algorithms lean on a Union-Find (Disjoint Set Union, or DSU) structure to track which nodes are already linked, so we build it first.
Implement two methods on the provided DSU class:
The connected(a, b) helper is already written for you in terms of find.
Real use: when laying fiber between towns, DSU instantly answers "are these two already on the same network?" so you never add a redundant, money-wasting cable.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
"""Return the representative (root) of x, using path compression."""
# TODO: follow parent pointers up to the root, compressing the path
pass
def union(self, a, b):
"""Merge the sets of a and b by rank. Return True if merged, False if already joined."""
# TODO: find both roots; if equal return False; else attach shorter under taller
pass
def connected(self, a, b):
return self.find(a) == self.find(b)
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
A Minimum Spanning Tree (MST) connects every node in a network at the least total cost. Both classic MST algorithms lean on a Union-Find (Disjoint Set Union, or DSU) structure to track which nodes are already linked, so we build it first.
Implement two methods on the provided DSU class:
The connected(a, b) helper is already written for you in terms of find.
Real use: when laying fiber between towns, DSU instantly answers "are these two already on the same network?" so you never add a redundant, money-wasting cable.
Press Run Tests or ⌘↩ to check your solution.