A Disjoint Set Union (DSU) tracks which items belong to the same group. Each item points to a parent; following parents leads to a root that represents the whole set.
Start with n singleton sets: parent[i] = i, so every item is its own root.
Implement find(x): walk parent pointers upward until you reach an item that is its own parent, and return that root. This answers the question: who represents x's set?
class DSU:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
"""Return the root representative of the set containing x."""
# TODO: walk parent pointers until you reach an element that is its own parent, then return it.
pass
The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
A Disjoint Set Union (DSU) tracks which items belong to the same group. Each item points to a parent; following parents leads to a root that represents the whole set.
Start with n singleton sets: parent[i] = i, so every item is its own root.
Implement find(x): walk parent pointers upward until you reach an item that is its own parent, and return that root. This answers the question: who represents x's set?
Press Run Tests or ⌘↩ to check your solution.